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.



Also Published In

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

More About This Work

Academic Units
Computer Science
Published Here
September 22, 2011