Architecture-aware FPGA placement using metric embedding

ABSTRACT

Since performance on FPGAs is dominated by the routing architecture rather than wirelength, we propose a new ar-chitecture-aware approach to initial FPGA placement that models the relationship between performance and the routing grid, using concepts from graph embedding and metric geometry. Our approach, CAPRI, can be viewed as an embedding of a graph representing the netlist into a metric space that is representative of the FPGA. First, we develop an analytic metric of distance that models delays along the FPGA routing grid. We then embed a netlist into the defined metric space using matrix projections and online bipartite matching. Experimental comparisons with the popular FPGA tool, VPR, show that with CAPRI's initial solution, the resulting placements show median improvements of 10% in critical path delays for the larger MCNC benchmarks. Total placement runtime is also improved by 2x on average.

REFERENCES

• 1: D. P. Bertsekas. Nonlinear Programming. Athena, 1999.
• 2: John P. Blanks, Near-optimal placement using a quadratic objective function, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.609-615, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317953]
• 3: 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]
• 4: J. Frankle and R. M. Karp. Circuit placements and cost bounds by eigenvector decomposition. In ICCAD, 1986.
• 5: G. Parthasarathy , M. Marek-Sadowska , Arindam Mukherjee , Amit Singh, Interconnect complexity-aware FPGA placement using Rent's rule, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.115-121, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368806]
• 6: G.Chen and J.Cong. Simultaneous Timing Driven Clustering and Placement for FPGAs. In FPL, 2004.
• 7: G.H.Golub and C. Loan. Matrix Computations. JHU, 1983.
• 8: T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Comp. Sci., 38, 1985.
• 9: David Harel , Yehuda Koren, Graph Drawing by High-Dimensional Embedding, Revised Papers from the 10th International Symposium on Graph Drawing, p.207-219, August 26-28, 2002
• 10: M. Khellah, S.Brown, and Z.Vranesic. Modeling routing delays in SRAM-based FPGAs. In Canadian Conf. on VLSI, 1993.
• 11: 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]
• 12: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 13: 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]
• 14: Navaratnasothie Selvakkumaran , Abhishek Ranjan , Salil Raje , George Karypis, Multi-resource aware partitioning algorithms for FPGAs with heterogeneous resources, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968339]
• 15: 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]
• 16: R.A.Finkel and J.L.Bentley. Quad Trees: A Data Structure for Retrieval of Composite Keys. Acta Informatica, 4(1), 1974.
• 17: Rajeev Jayaraman, Physical design for FPGAs, Proceedings of the 2001 international symposium on Physical design, p.214-221, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369776]
• 18: S.K.Nag and R.Rutenbar. Performance-driven Simultaneous Placement and Routing for FPGAs. IEEE TCAD, 17(6), 1998.
• 19: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 20: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 21: Tanay Karnik , Sung-Mo Kang, An empirical model for accurate estimation of routing delay in FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.328-331, November 05-09, 1995, San Jose, California, United States
• 22: Taraneh Taghavi , Soheil Ghiasi , Abhishek Ranjan , Salil Raje , Majid Sarrafzadeh, Innovate or perish: FPGA physical design, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981099]
• 23: www.altera.com.
• 24: www.eecg.toronto.edu/evaughn/challenge/challenge.html.
• 25: www.xilinx.com.
• 26: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
FPGAs, metric embedding, placement