New timing and routability driven placement algorithms for FPGA synthesis

ABSTRACT

We present new timing and congestion driven FPGA placement algorithms with minimal runtime overhead. By predicting the post-routing critical edges and estimating congestion accurately, our algorithms simultaneously reduce the critical path delay and the minimum number of routing tracks. The core of our algorithm consists of a criticality history record of connection edges and a congestion map. This approach is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR [1], our algorithms yield an average of 8.1% reduction (maximum 30.5%) in the critical path delay and 5% reduction in channel width. Meanwhile, the average runtime of our algorithms is only 2.3X as of VPR's.

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: E. Bozorgzadeh, S. Ogrenci-Memik, X. Yang, and M. Sarrafzadeh. Routability-driven packing: Metrics and algorithms for cluster-based FPGAs. Journal of Circuits Systems and Computers, 13(1):77--100, 2004.
• 4: D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382677]
• 5: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 6: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 7: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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]
• 12: Joey Y. Lin , Deming Chen , Jason Cong, Optimal simultaneous mapping and clustering for FPGA delay optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147035]
• 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: A. Srinivasan, K. Chaudhary, and E. S. Kuh. Ritual: A performance driven placement algorithm for small cell ic's. In IEEE/ACM International Conference on Computer-Aided Design, pages 45--51, 1991.
• 16: 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]
• 17: 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]
• 18: 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]
• 19: Y. Zhuo, H. Li, and S. P. Mohanty. A congestion driven placement algorithm for FPGA synthesis. In Proceedings of the 16th IEEE International Conference on Field Programmable Logic and Applications, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
congestion driven placement, net weight, physical synthesis, timing driven placement