Optimal joint module-selection and retiming with carry-save representation

This paper is the first to combine the joint module-selection and retiming problem with the use of carry-save representation in the optimization of a synchronous circuit. To solve this problem efficiently, we first create a mixed-representation data-flow graph (MFG) by inserting signal representatio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2003-07, Vol.22 (7), p.836-846
Main Authors: Zhan Yu, Kei-Yong Khoo, Willson, A.N.
Format: Article
Language:English
Subjects:
Adders
Arithmetic
Circuits
Conversion
Cost function
Delay
Graphs
Hardware
High level synthesis
Linear programming
Mathematical models
Optimization
Registers
Representations
Signal representations
Studies
Synchronous
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is the first to combine the joint module-selection and retiming problem with the use of carry-save representation in the optimization of a synchronous circuit. To solve this problem efficiently, we first create a mixed-representation data-flow graph (MFG) by inserting signal representation conversion vertices into the data-flow graph, thus allowing carry-save representation to be freely selected for use. We then identify key properties of an optimal implementation of the MFG that consider the different signal representations as well as the sharing of registers and adders. These properties enable us to formulate the problem as a mixed-integer linear programming problem with cost functions that accurately reflect the true implementation costs of the circuit. Our algorithm, by allowing carry-save representation, can produce a wider range of solutions. In our experiments, our fastest implementation is 27% faster and our smallest implementation is 27% smaller, in comparison with solutions obtained using the previously known joint module-selection and retiming technique.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2003.814251