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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yuen-Hong Alvin HO, Chi-Un LEI, Hing-Kit KWAN, Ngai WONG, "Optimal Common Sub-Expression Elimination Algorithm of Multiple Constant Multiplications with a Logic Depth Constraint" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 12, pp. 3568-3575, December 2008, doi: 10.1093/ietfec/e91-a.12.3568.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.12.3568/_p
Copy
@ARTICLE{e91-a_12_3568,
author={Yuen-Hong Alvin HO, Chi-Un LEI, Hing-Kit KWAN, Ngai WONG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Common Sub-Expression Elimination Algorithm of Multiple Constant Multiplications with a Logic Depth Constraint},
year={2008},
volume={E91-A},
number={12},
pages={3568-3575},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e91-a.12.3568},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Optimal Common Sub-Expression Elimination Algorithm of Multiple Constant Multiplications with a Logic Depth Constraint
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3568
EP - 3575
AU - Yuen-Hong Alvin HO
AU - Chi-Un LEI
AU - Hing-Kit KWAN
AU - Ngai WONG
PY - 2008
DO - 10.1093/ietfec/e91-a.12.3568
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2008
AB - 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.
ER -