Timing-driven placement for hierarchical programmable logic devices

ABSTRACT

In this paper we discuss new techniques for timing-driven placement and adaptive delay computation for hierarchical PLD architectures.Our algorithm follows the natural recursive k-way partitioning-based approach to placement on such devices. Our contributions include a specification of the overall TDC (timing-driven compilation) algorithm, an analysis of heuristics such as a variant of multi-start partitioning, a new method for adaptive delay computation, and a discussion of the structure of critical paths and sub-graphs on modern PLD designs.This algorithm has been implemented in a production quality commercial tool, and we report on the results with and without the implementation of the new techniques. The basic result is a substantial 38.5% average (36.3% median) improvement in register-to-register performance across a range of real designs in modern density ranges, at a cost of approximately 3.65X average (2.88X median) place-and-route CPU time. (These improvements and costs are relative to the same tool prior to the efforts described in this paper.) A partial implementation of the new algorithm shows approximately half the performance gain, with approximately half the compile time cost.

REFERENCES

• 1: Altera Corp. Device Data Book, 1999.
• 2: D.W. Bennett, E.F. Dellinger, W.A. Manaker, Jr, C.M. Stern, W.R.Troxel and J.T. Young, Frequency-Driven Layout and Method for Field-Programmable Gate Arrays, US Patent #5,659,484, Aug. 19, 1997.
• 3: V. Betz, Architecture and CAD for Speed and Area Optimization of FPGAs, Ph.D. Dissertation, University of Toronto, 1998.
• 4: Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
• 5: Wilm E. Donath , Reini J. Norman , Bhuwan K. Agrawal , Stephen E. Bello , Sang Yong Han , Jerome M. Kurtzberg , Paul Lowy , Roger I. McMillan, Timing driven placement using complete path delays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.84-89, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123232]
• 6: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 7: J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
• 8: M. Hutton, A Method for Adaptive Critical Path Delay Estimation During Timing-Driven Placement for Hierarchical Programmable Logic Devices, US Patent Pending.
• 9: P. Leventis, Placement algorithms and routing architecture for long-line based FPGAs, Bachelor thesis, University of Toronto, 1999.
• 10: 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]
• 11: S.K. Nag and R.A. Rutenbar, Performance-Driven Simultaneous Placement and Routing for FPGAs. IEEE Trans. On CAD for Integrated Circuits and Systems, Vol. 17, No. 6, pp. 499-518, June 1998.
• 12: Shih-Lian Ou , Massoud Pedram, Timing-driven placement based on partitioning with dynamic cut-net control, Proceedings of the 37th conference on Design automation, p.472-476, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337548]
• 13: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
• 14: Prashant Sawkar , Donald Thomas, Multi-way partitioning for minimum delay for look-up table based FPGAs, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.201-210, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217530]
• 15: S. A. Senouci , A. Amoura , H. Krupnova , G. Saucier, Timing driven floorplanning on programmable hierarchical targets, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.85-92, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275123]
• 16: Suphachai Sutanthavibul , Eugene Shragowitz, Dynamic prediction of critical paths and nets for constructive timing-driven placement, Proceedings of the 28th conference on ACM/IEEE design automation, p.632-635, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127165]
• 17: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Algorithms, Design

Keywords:
CPLD, FPGA, algorithm, heuristic algorithm, partitioning, placement, programmable logic, timing-driven placement