Multilevel global placement with retiming

ABSTRACT

Multiple clock cycles are needed to cross the global interconnects for multi-gigahertz designs in nanometer technologies. For synchronous designs, this requires retiming and pipelining on global interconnects. In this paper, we present a practical solution for simultaneous retiming and multilevel global placement for performance optimization, based on the theory and algorithms of sequential timing analysis (Seq-TA). We extend the Seq-TA to handle gates/clusters with multiple outputs and integrate it into a multilevel optimization framework for simultaneous retiming and placement. We also develop two speed-up techniques which enable the Seq-TA to be efficiently integrated into a simulated annealing-based multilevel coarse placement for large-scale designs. Experimental results show that (i) retiming can improve the performance (delay) by 14% on average when it is applied after placement; (ii) our approach for simultaneous retiming and placement can outperform the two-step approach (placement followed by retiming) by 10% on average in terms of delay minimization.

REFERENCES

• 1: Chin-Chih Chang , Jason Cong , Zhigang (David) Pan, Physical hierarchy generation with routing congestion control, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505399]
• 2: P. Chong and R. K. Brayton. Characterization of feasible retimings. In Proc. Int. Workshop on Logic and Synthesis, pages 1--6, 2001.
• 3: J. Cong. An interconnect-centric design flow for nanometer technologies. In Proceedings of the IEEE, pages 505--527, April 2001.
• 4: Jason Cong , Honching Li , Chang Wu, Simultaneous circuit partitioning/clustering with retiming for performance optimization, Proceedings of the 36th ACM/IEEE conference on Design automation, p.460-465, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309980]
• 5: Jason Cong , Sung Kyu Lim, Physical planning with retiming, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 7: J. Cong and C. Wu. An efficient algorithm for performance-optimal FPGA technology mapping with retiming. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 17(9):738--748, 1998.
• 8: J. Cong and X. Yuan. Multilevel global placement with retiming. Technical Report 03-0023, Computer Science Department, University of California, Los Angeles, 2003.
• 9: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 10: Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774597]
• 11: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, pages 5--35, 1991.
• 12: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 13: Ingmar Neumann , Wolfgang Kunz, Placement driven retiming with a coupled edge timing model, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 14: I. Neumann and W. Kunz. Tight coupling of timing-driven placement and retiming. In Proc. IEEE Int. Symp. on Circuits and Systems, pages 351--354, 2001.
• 15: Continuous retiming: algorithms and applications, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.116, October 12-15, 1997
• 16: P. Pan, A. K. Karandikar, and C. L. Liu. Optimal clock period clustering for sequential circuits with retiming. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 17(6):489--498, 1998.
• 17: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 18: Semiconductor Industry Association. International Technology Roadmap for Semiconductors, 2002 update.
• 19: M. Senn, U. Seidl, and F. Johannes. High quality deterministic timing driven FPGA placement. In Proc. ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, 2002.
• 20: Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503059]
• 21: Tzu-Chieh Tien , Hsiao-Pin Su , Yu-Wen Tsay , Yih-Chih Chou , Youn-Long Lin, Integrating logic retiming and register placement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.136-139, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288591]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
deep sub-micron, physical hierarchy, placement, retiming