Article

Architecture-aware FPGA placement using metric embedding

Authors:

Padmini Gopalakrishnan,

Lawrence PileggiAuthors Info & Claims

DAC '06: Proceedings of the 43rd annual Design Automation Conference

Pages 460 - 465

https://doi.org/10.1145/1146909.1147033

Published: 24 July 2006 Publication History

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]

J. P. Blanks. Near-optimal placement using a quadratic objective function. In DAC, 1985.

Digital Library

[3]

H. Eisenmann and F. M. Johannes. Generic global placement and oorplanning. In DAC, 1998.

Digital Library

[4]

J. Frankle and R. M. Karp. Circuit placements and cost bounds by eigenvector decomposition. In ICCAD, 1986.

[5]

G. Parthasarathy, et al. Interconnect complexity-aware FPGA placement using Rent's rule. In SLIP, 2001.

Digital Library

[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]

D. Harel and Y. Koren. Graph Drawing by High Dimensional Embedding. In Graph Drawing, 2002.

Digital Library

[10]

M. Khellah, S.Brown, and Z.Vranesic. Modeling routing delays in SRAM-based FPGAs. In Canadian Conf. on VLSI, 1993.

[11]

A. Marquardt, V. Betz, and J. Rose. Timing-Driven Placement for FPGAs. In FPGA, 2000.

Digital Library

[12]

J. Matousek. Lectures in Discrete Geometry. Springer, 2002.

Digital Library

[13]

M.Hutton, et al. Timing Driven Placement for Hierarchical Programmable Logic Devices. In FPGA, 2001.

Digital Library

[14]

N.Selvakkumaran, et al. Partitioning Algorithms for FPGAs with Heterogeneous Resources. In FPGA, 2004.

Digital Library

[15]

P.Maidee, et al. Fast Timing-driven Partitioning-based Placement for Island-style FPGAs. In DAC, 2003.

Digital Library

[16]

R.A.Finkel and J.L.Bentley. Quad Trees: A Data Structure for Retrieval of Composite Keys. Acta Informatica, 4(1), 1974.

[17]

R.Jayaraman. Physical Design for FPGAs. In ISPD, 2001.

Digital Library

[18]

S.K.Nag and R.Rutenbar. Performance-driven Simultaneous Placement and Routing for FPGAs. IEEE TCAD, 17(6), 1998.

Digital Library

[19]

S.Sahni and T.Gonzalez. P-complete approximation problems. Journal of ACM, 23, 1976.

Digital Library

[20]

T.H.Cormen, C.E.Leiserson, and R.L.Rivest. Introduction to Algorithms. MIT Press, 1995.

Digital Library

[21]

T.Karnik and S-M.Kang. An Empirical Model for Estimation of Routing Delays in FPGAs. In ICCAD, 1995.

Digital Library

[22]

T.Taghavi, S.Ghiasi, A.Ranjan, S.Raje, and M.Sarrafzadeh. Innovate or Perish: FPGA Physical Design. In ISPD, 2004.

Digital Library

[23]

www.altera.com.

[24]

www.eecg.toronto.edu/evaughn/challenge/challenge.html.

[25]

www.xilinx.com.

[26]

Y.Chang, et al. An architecture-driven metric for simultaneous placement and global routing for FPGAs. In DAC, 2000.

Digital Library

Cited By

Nikolić SIenne P(2024)Exploring FPGA Switch-Blocks without Explicitly Listing Connectivity PatternsACM Transactions on Reconfigurable Technology and Systems10.1145/359741717:1(1-39)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3597417
Liu MWang YLi S(2023)A Field Programmable Gate Array Placement Methodology for Netlist-Level Circuits with GPU AccelerationElectronics10.3390/electronics1301003713:1(37)Online publication date: 20-Dec-2023
https://doi.org/10.3390/electronics13010037
Meng YLi WLin YPan D(2022)elfPlace: Electrostatics-Based Placement for Large-Scale Heterogeneous FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.305319141:1(155-168)Online publication date: Jan-2022
https://doi.org/10.1109/TCAD.2021.3053191
Show More Cited By

Index Terms

Architecture-aware FPGA placement using metric embedding
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Routing-architecture-aware analytical placement for heterogeneous FPGAs
DAC '15: Proceedings of the 52nd Annual Design Automation Conference

Placement is a crucial stage for FPGA implementation. Most FPGA placers optimize their placement results by minimizing half-perimeter wirelength (HPWL). Due to the segmented routing architecture in FPGAs, however, the HPWL function cannot model routed ...
Clock-Aware FPGA Placement Contest
ISPD '17: Proceedings of the 2017 ACM on International Symposium on Physical Design

Modern FPGA device contains complex clocking architecture on top of FPGA logic fabric. To best utilize FPGA clocking architecture, both FPGA designers and EDA tool developers need to understand the clocking architecture and design best methodology/...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '06: Proceedings of the 43rd annual Design Automation Conference

July 2006

1166 pages

ISBN:1595933816

DOI:10.1145/1146909

General Chair:
Ellen M. Sentovich
Cadence Berkeley Labs, Berkeley, CA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC06

Sponsor:

DAC06: The 43rd Annual Design Automation Conference 2006

July 24 - 28, 2006

CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
538
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikolić SIenne P(2024)Exploring FPGA Switch-Blocks without Explicitly Listing Connectivity PatternsACM Transactions on Reconfigurable Technology and Systems10.1145/359741717:1(1-39)Online publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1145/3597417
Liu MWang YLi S(2023)A Field Programmable Gate Array Placement Methodology for Netlist-Level Circuits with GPU AccelerationElectronics10.3390/electronics1301003713:1(37)Online publication date: 20-Dec-2023
https://doi.org/10.3390/electronics13010037
Meng YLi WLin YPan D(2022)elfPlace: Electrostatics-Based Placement for Large-Scale Heterogeneous FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.305319141:1(155-168)Online publication date: Jan-2022
https://doi.org/10.1109/TCAD.2021.3053191
Nikolic SIenne P(2021)Turning PathFinder Upside-Down: Exploring FPGA Switch-Blocks by Negotiating Switch Presence2021 31st International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL53798.2021.00044(225-233)Online publication date: Aug-2021
https://doi.org/10.1109/FPL53798.2021.00044
Abuowaimer ZMaarouf DMartin TFoxcroft JGréwal GAreibi SVannelli A(2018)GPlace3.0ACM Transactions on Design Automation of Electronic Systems10.1145/323324423:5(1-33)Online publication date: 12-Oct-2018
https://dl.acm.org/doi/10.1145/3233244
Chen GPui CChow WLam KKuang JYoung EYu B(2018)RippleFPGAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277805837:10(2022-2035)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2778058
Li WDhar SPan D(2018)UTPlaceFIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.272934937:4(869-882)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2729349
Kumar A(2018)Placement Solution for Homogeneous FPGA Using Tree-Based Algorithm2018 Fourth International Conference on Computing Communication Control and Automation (ICCUBEA)10.1109/ICCUBEA.2018.8697645(1-6)Online publication date: Aug-2018
https://doi.org/10.1109/ICCUBEA.2018.8697645
Mukherjee SNainwal ADas CPurkayastha S(2018)An Alternate Algorithmic Approach to FPGA Placement2018 9th International Conference on Computing, Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT.2018.8493947(1-6)Online publication date: Jul-2018
https://doi.org/10.1109/ICCCNT.2018.8493947
Veredas FCarmona E(2018)FPGA Placement Improvement Using a Genetic Algorithm and the Routing Algorithm as a Cost Function2018 21st Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2018.00026(70-76)Online publication date: Aug-2018
https://doi.org/10.1109/DSD.2018.00026
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents