Architecture-aware FPGA placement using metric embedding

Conference Paper

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. Copyright 2006 ACM.

Full Text

Duke Authors

Cited Authors

  • Gopalakrishnan, P; Li, X; Pileggi, L

Published Date

  • December 1, 2006

Published In

Start / End Page

  • 460 - 465

International Standard Serial Number (ISSN)

  • 0738-100X

International Standard Book Number 10 (ISBN-10)

  • 1595933816

International Standard Book Number 13 (ISBN-13)

  • 9781595933812

Digital Object Identifier (DOI)

  • 10.1145/1146909.1147033

Citation Source

  • Scopus