Optimizing sequential cycles through Shannon decomposition and retiming

ABSTRACT

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 (3%--12%). The algorithm is also fast, making it a practical addition to a synthesis flow.

REFERENCES

• 1: C. L. Berman, D. J. Hathaway, A. S. LaPaugh, and L. Trevillyan. Efficient techniques for timing correction. In Proc. ISCAS, pages 415--419, 1990.
• 2: Robert K. Brayton , Gary D. Hachtel , Alberto L. Sangiovanni-Vincentelli , Fabio Somenzi , Adnan Aziz , Szu-Tsung Cheng , Stephen A. Edwards , Sunil P. Khatri , Yuji Kukimoto , Abelardo Pardo , Shaz Qadeer , Rajeev K. Ranjan , Shaker Sarwary , Thomas R. Shiple , Gitanjali Swamy , Tiziano Villa, VIS: A System for Verification and Synthesis, Proceedings of the 8th International Conference on Computer Aided Verification, p.428-432, August 03, 1996
• 3: Soha Hassoun , Carl Ebeling, Architectural retiming: pipelining latency-constrained circuits, Proceedings of the 33rd annual conference on Design automation, p.708-713, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240652]
• 4: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 5: S. Malik, E. M. Sentovich, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Retiming and resynthesis: Optimizing sequential networks with combinational techniques. IEEE Transactions on CAD, 10(1):74--84, 1991.
• 6: Maria-Cristina V. Marinescu , Martin Rinard, High-level automatic pipelining for sequential circuits, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500053]
• 7: P. C. McGeer, R. K. Brayton, A. L. Sangiovanni-Vincentelli, and S. K. Sahni. Performance enhancement through the generalized bypass transform. In ICCAD, pages 184--187, 1991.
• 8: Peichen Pan, Performance-driven integration of retiming and resynthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.243-246, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309921]
• 9: Alexander Saldanha , Heather Harkness , Patrick C. McGeer , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Performance optimization using exact sensitization, Proceedings of the 31st annual conference on Design automation, p.425-429, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196448]
• 10: E. M. Sentovich et al. SIS: A system for sequential circuit synthesis. Technical report, UCB/ERL M92/41, 1992.
• 11: Kanwar Jit Singh, Performance optimization of digital circuits, University of California at Berkeley, Berkeley, CA, 1992
• 12: K. J. Singh, A. R. Wang, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Timing optimization of combinational logic. In Proceedings of ICCAD, pages 282--285, 1988.
• 13: H. Touati, H. Savoj, and R. K. Brayton. Delay optimization of combinational logic circuits by clustering and partial collapsing. In Proceedings of ICCAD, pages 188--191, 1991.
• 14: H. Touati, N. Shenoy, and A. L. Sangiovanni-Vincentelli. Retiming for table-lookup field-programmable gate arrays. In Proc. Intl. Workshop FPGAs, pages 89--93, 1992.