Optimal Common Sub-Expression Elimination Algorithm of Multiple Constant Multiplications with a Logic Depth Constraint

Yuen-Hong Alvin HO  Chi-Un LEI  Hing-Kit KWAN  Ngai WONG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.12   pp.3568-3575
Publication Date: 2008/12/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.12.3568
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: High-Level Synthesis and System-Level Design
Keyword: 
common sub-expression sharing,  multiple constant multiplications,  mixed-integer linear programming,  

Full Text: PDF(308.8KB)>>
Buy this Article




Summary: 
In the context of multiple constant multiplication (MCM) design, we propose a novel common sub-expression elimination (CSE) algorithm that models the optimal synthesis of coefficients into a 0-1 mixed-integer linear programming (MILP) problem with a user-defined generic logic depth constraint. We also propose an efficient solution space, which combines all minimal signed digit (MSD) representations and the shifted sum (difference) of coefficients. In the examples we demonstrate, the combination of the proposed algorithm and solution space gives a better solution comparing to existing algorithms.