Fast timing-driven partitioning-based placement for island style FPGAs

ABSTRACT

In this paper we propose a partitioning-based placement algorithm for FPGAs. The method incorporates simple, but effective heuristics that target delay minimization. The placement engine incorporates delay estimations obtained from previously placed and routed circuits using VPR [6]. As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is employed to further optimize the delay of the circuit in the routing phase. Simulation results show that the proposed technique can achieve comparable circuit delays (after routing) to those obtained with VPR while achieving a 7-fold speedup in placement runtime.

REFERENCES

• 1: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 2: Xilinx Inc., The Programmable Logic Data Book, 2002.
• 3: Pak K. Chan , Martine D. F. Schlag, Parallel placement for field-programmable gate arrays, 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.611825]
• 4: 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]
• 5: Yao-Wen Chang , Kai Zhu , D. F. Wong, Timing-driven routing for symmetrical array-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.433-450, July 2000 [doi>10.1145/348019.348101]
• 6: 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
• 7: 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]
• 8: Chandra Mulpuri , Scott Hauck, Runtime and quality tradeoffs in FPGA placement and routing, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.29-36, February 2001, Monterey, California, United States [doi>10.1145/360276.360294]
• 9: 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]
• 10: 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]
• 11: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 12: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 13: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 14: 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]
• 15: M. Khellah, S. Brown and Z. Vranesic , "Minimizing Interconnection Delays in Arrays-based FPGAs", CICC 1994.
• 16: Vaughn Betz , Jonathan Rose, FPGA routing architecture: segmentation and buffering to optimize speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.59-68, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296428]
• 17: 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]
• 18: N. Togawa, M. Sato and T. Ohtsuki , "A Simultaneous Placement and Global Routing Algorithm with Path Length Constraints for Transport-Processing FPGAs", 1997.
• 19: S. K. Nag and R. A. Rutenbar, "Pertbrmance-driven simultaneous placement and routing for FPGAs", IEEE Trans. on Computer-Aided Design, Vol. 17, No. 6, pp. 499--518, June 1998.

INDEX TERMS

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

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

General Terms:
Experimentation, Performance

Keywords:
FPGA placement, FPGAs, partitioning based placement, timing-driven placement