Criticality history guided FPGA placement algorithm for timing optimization

ABSTRACT

We present an efficient timing-driven placement algorithm for FPGAs. Our major contribution is a criticality history guided (CHG) approach that can simultaneously reduce the critical path delay and computation time. The proposed approach keeps track of the timing criticality history of each edge and utilizes this information to effectively guide the placer. We also present a cooling schedule that optimizes both timing and run time when combined with the CHG method. The proposed algorithm is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR, our algorithm yields an average of 21.7% reduction (maximum 45.8%) in the critical path delay and it runs 2.2X fasterthan VPR. In addition, our approach outperforms other algorithms discussed in the literature in both delay and run time.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: Yao-Wen Chang , Yu-Tsang Chang, An architecture-driven metric for simultaneous placement and global routing for FPGAs, Proceedings of the 37th conference on Design automation, p.567-572, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337582]
• 4: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 5: Padmini Gopalakrishnan , Xin Li , Lawrence Pileggi, Architecture-aware FPGA placement using metric embedding, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147033]
• 6: Takeo Hamada , Chung-Kuan Cheng , Paul M. Chau, Prime: a timing-driven placement tool using a piecewise linear resistive network approach, Proceedings of the 30th international conference on Design automation, p.531-536, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165015]
• 7: Michael Hutton , Khosrow Adibsamii , Andrew Leaver, Timing-driven placement for hierarchical programmable logic devices, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.3-11, February 2001, Monterey, California, United States [doi>10.1145/360276.360286]
• 8: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• 9: A. Kennings and K. P. Vorwerk. Force-directed methods for generic placement. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 25(10):2076--2087, October 2006.
• 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: Yongqiang Lu , Xianlong Hong , Qiang Zhou , Yici Cai , Jun Gu, An efficient quadratic placement based on search space traversing technology, Integration, the VLSI Journal, v.40 n.3, p.253-260, April, 2007 [doi>10.1016/j.vlsi.2005.10.002]
• 12: Pongstorn Maidee , Cristinel Ababei , Kia Bazargan, Fast timing-driven partitioning-based placement for island style FPGAs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775984]
• 13: 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]
• 14: U. of Toronto. The FPGA place-and-route challenge. http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html.
• 15: Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981070]
• 16: A. Srinivasan, K. Chaudhary, and E.S. Kuh. Ritual: A performance driven placement algorithm for small cell ICs. In Int'l Conf. on Computer-Aided Design, pages 45--51, November 1991.
• 17: Russell Tessier, Fast placement approaches for FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.2, p.284-305, April 2002 [doi>10.1145/544536.544540]
• 18: Qingzhou (Ben) Wang , John Lillis , Shubhankar Sanyal, An LP-based methodology for improved timing-driven placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120925]
• 19: Michael G. Wrighton , André M. DeHon, Hardware-assisted simulated annealing with application for fast FPGA placement, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611824]
• 20: Yue Zhuo , Hao Li , Qiang Zhou , Yici Cai , Xianlong Hong, New timing and routability driven placement algorithms for FPGA synthesis, Proceedings of the 17th ACM Great Lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy [doi>10.1145/1228784.1228918]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

General Terms:
Algorithms, Design, Performance

Keywords:
fpga, placement, timing optimization