Academic Commons

Articles

Optimizing Sequential Cycles Through Shannon Decomposition and Retiming

Soviani, Cristian; Tardieu, Olivier; Edwards, Stephen A.

Optimizing sequential cycles is essential for many types of high-performance circuits, such as pipelines for packet processing. Retiming is a powerful technique for speeding pipelines, but it is stymied by tight sequential cycles. Designers usually attack such cycles by manually combining Shannon decomposition with retiming-effectively a form of speculation-but such manual decomposition is error prone. We propose an efficient algorithm that simultaneously applies Shannon decomposition and retiming to optimize circuits with tight sequential cycles. While the algorithm is only able to improve certain circuits (roughly half of the benchmarks we tried), the performance increase can be dramatic (7%-61%) with only a modest increase in area (1%-12%). The algorithm is also fast, making it a practical addition to a synthesis flow.

Subjects

Files

Also Published In

Title
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
DOI
https://doi.org/10.1109/TCAD.2006.890583

More About This Work

Academic Units
Computer Science
Published Here
September 22, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.