Fast placement approaches for FPGAs

ABSTRACT

Recent trends in FPGA development indicate a strong shift toward design reuse through the use of intellectual property (IP). This design shift has motivated the development of Frontier, a timing-driven FPGA placement system that uses design macroblocks in conjunction with a series of placement algorithms to achieve highly routable and high-performance layouts quickly. In the first stage of design placement, a macro-based floorplanner is used to quickly identify an initial layout based on intermacro connectivity. Next, FPGA routability and performance metrics are used to evaluate the quality of the initial placement. Finally, if the floorplan is determined to be insufficient from a routability or performance standpoint, a feedback-driven placement perturbation step is employed to achieve a lower cost placement. For a collection of large reconfigurable computing benchmark circuits our timing-driven placement system exhibits a 2.6× speedup in combined place and route time versus commercial FPGA CAD software with improved design performance for most designs. It is shown that floorplanning, placement evaluation, and backend optimization are all necessary to achieve high-performance placement solutions.

REFERENCES

• 1: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• 2: 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
• 3: Timothy J. Callahan , Philip Chong , André DeHon , John Wawrzynek, Fast module mapping and placement for datapaths in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.123-132, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275132]
• 4: John M. Emmert , Dinesh Bhatia, A methodology for fast FPGA floorplanning, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.47-56, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296427]
• 5: John M. Emmert , Akash Randhar , Dinesh Bhatia, Fast Floorplanning for FPGAs, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.129-138, August 31-September 03, 1998
• 6: Stephan W. Gehring , Stefan H.-M. Ludwig, Fast integrated tools for circuit design with FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.133-139, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275133]
• 7: Andreas Koch, Structured design implementation: a strategy for implementing regular datapaths on FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.151-157, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228392]
• 8: Landman, B. and Russo, R. 1971. On a pin versus block relationship for partitions of logic graphs. IEEE Trans. Comput. C-20, 12 (Dec.), 1469--1479.
• 9: Lucent Technologies. 1996. Field-Programmable Gate Arrays Data Book. Lucent Technologies.
• 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: Yaska Sankar , Jonathan Rose, Trading quality for compile time: ultra-fast placement for FPGAs, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.157-166, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296449]
• 12: Sechen, C. 1988. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, Boston.
• 13: K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
• 14: Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
• 15: Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
• 16: Russell G. Tessier , Stephen A. Ward, Fast place and route approaches for fpgas, 1999
• 17: Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
• 18: Xilinx Corporation. 1998. The Programmable Logic Data Book. Xilinx Corporation.
• 19: Xilinx Corporation. 2001. Virtex II Data Sheet. Xilinx Corporation.
• 20: Takayuki Yamanouchi , Kazuo Tamakashi , Takashi Kambe, Hybrid floorplanning based on partial clustering and module restructuring, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.478-483, November 10-14, 1996, San Jose, California, United States

INDEX TERMS

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

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

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
Computer-aided design of VLSI, field-programmable gate arrays, layout, synthesis