Retiming-based factorization for sequential logic optimization

ABSTRACT

Current sequential optimization techniques apply a variety of logic transformations that mainly target the combinational logic component of the circuit. Retiming is typically applied as a postprocessing step to the gate-level implementation obtained after technology mapping. This paper introduces a new sequential logic transformation which integrates retiming with logic transformations at the technology-independent level. This transformation is based on implicit retiming across logic blocks and fanout stems during logic optimization. Its application to sequential network synthesis results in the optimization of logic across register boundaries. It can be used in conjunction with any measure of circuit quality for which a fast and reliable gain estimation method can be obtained. We immplemented our new technique within the SIS framework and demonstrated its effectiveness in terms of cycle-time minimization on a set sequential benchmark circuits.

REFERENCES

• 1: Srimat T. Chakradhar , Sujit Dey , Miodrag Potkonjak , Steven G. Rothweiler, Sequential circuit delay optimization using global path delays, Proceedings of the 30th international conference on Design automation, p.483-489, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164991]
• 2: CHANDRAKASAN, A. P., POTKONJAK, M., MEHRA, R., RABEY, J., AND BRODERSON, R. W. 1995. Optimizing power using transformations. IEEE Trans. Comput.-Aided Des. Integr. Circuits 14, 1 (Jan. 1995), 12-31.
• 3: DE MICHELI, G. 1991. Synchronous logic synthesis: Algorithms for cycle-time optimization. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 10, 1 (Jan. 1991), 63-73.
• 4: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 5: Sujit Dey , Miodrag Potkonjak , Steven G. Rothweiler, Performance optimization of sequential circuits by eliminating retiming bottlenecks, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.504-509, November 1992, Santa Clara, California, United States
• 6: Paul T. Gutwin , Patrick C. McGeer , Robert K. Brayton, Delay Prediction for Technology-Independent Logic Equations, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.468-471, October 11-14, 1992
• 7: Gary D. Hachtel , Mariano Hermida , Abelardo Pardo , Massimo Poncino , Fabio Somenzi, Re-encoding sequential circuits to reduce power dissipation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.70-73, November 06-10, 1994, San Jose, California, United States
• 8: 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]
• 9: Sasan Iman , Massoud Pedram, Logic extraction and factorization for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.248-253, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217537]
• 10: Zia Iqbal , Miodrag Potkonjak , Sujit Dey , Alice Parker, Critical path minimization using retiming and algebraic speed-up, Proceedings of the 30th international conference on Design automation, p.573-577, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165046]
• 11: Kumar N. Lalgudi , Marios C. Papaefthymiou, DELAY: an efficient tool for retiming with realistic delay modeling, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.304-309, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217546]
• 12: LEISERSON, C., ROSE, F., AND SAXE, g. 1983. Optimizing synchronous circuitry by retiming. In Proceedings of the Third Caltech Conference on VLSI, 87-116.
• 13: LIN, B. 1993. Restructuring of synchronous logic circuits. In Proceedings of the 1993 European Conference on Design Automation (EDAC '93 EURO-ASIC, Feb.), 205-209.
• 14: MALIK, S., SENTOVICH, E., BRAYTON, R., AND SANGIOVANNI-VINCENTELLI, A. 1991. Retiming and resynthesis: Optimizing sequential networks with combinational techniques. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 10, 1 (Jan. 1991), 74-84.
• 15: José Monteiro , Srinivas Devadas , Abhijit Ghosh, Retiming sequential circuits for low power, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.398-402, November 07-11, 1993, Santa Clara, California, United States
• 16: O'NEILL, N. 1997. Sequential logic synthesis based on retiming-based factorization. Master's Thesis. University of Massachusetts Press, Amherst, MA.
• 17: POTKONJAK, M., DEY, S., IQBAL, Z., AND PARKER, A. 1993. High performance embedded system optimization using algebraic and generalized retiming techniques. In Proceedings of the IEEE International Conference on Computer Design, IEEE Computer Society Press, Los Alamitos, CA, 498-504.
• 18: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 19: Vigyan Singhal , Carl Pixley , Richard L. Rudell , Robert K. Brayton, The validity of retiming sequential circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.316-321, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217548]
• 20: TOUATI, H. J. AND BRAYTON, R. K. 1993. Computing the initial states of retimed circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 12, 1 (Jan. 1993), 157-162.
• 21: WALLACE, D. AND CHANDRASEKHAR, M. 1990. High level delay estimation for technologyindependent logic equations. In Proceedings of the IEEE International Conference on Computer Aided Design, IEEE Computer Society Press, Los Alamitos, CA.
• 22: N. Wehn , J. Biesenack , Peter Duzy , T. Langmaier , M. Münch , Michael Pilsl , S. Rumler, Scheduling of behavioral VHDL by retiming techniques, Proceedings of the conference on European design automation, p.546-551, September 19-23, 1994, Grenoble, France

INDEX TERMS

Primary Classification:
  B. Hardware

Additional Classification:
  B. Hardware

General Terms:
Algorithms, Design

Keywords:
finite stat machines, retiming, sequential synthesis