Padmini Gopalakrishnan Carnegie Mellon University

Timing-Driven Initial Placement for FPGAs via Graph-Matching

Performance in Field Programmable Gate Arrays (FPGAs) is greatly influenced by the routing architecture, and in particular, by the number of programmable switches required to make a connection. It is therefore critical to model the FPGA routing architecture during optimization, especially during placement. Currently, this dependence of delay on FGPA routing architectures is captured by means of look-up tables or empirical models from routing statistics, in move-based algorithms such as simulated annealing and partitioning. While analytical placement techniques have proved to be powerful for ASICs, these techniques cannot be easily extended to FPGAs because of the poor correlation between the 'geometric length' of a connection and its delay on the FPGA routing grid.

To address this difficulty, we present CAPRI, an analytical framework to model global routing architectures during placement. We formulate FPGA placement as a binary quadratic assignment problem and present an efficient heuristic to find a good assignment. Our goal is to produce a good initial placement from a global timing perspective. At the heart of our framework is (a) the idea that any placement algorithm can be viewed as an embedding of a graph into a chosen metric space, and (b) an analytical metric of 'distance' in terms of delays on the FPGA routing grid. Experimental comparisons with the popular FPGA tool, VPR, demonstrate that when CAPRI is used to produce an initial solution, the resulting placements show a median improvement of close to 10% in critical path delays for the larger MCNC benchmarks. Total placement runtime is also reduced by an average of approximately 50%.

This is joint workwith Xin Li and Larry Pileggi.

Bio:

Padmini Gopalakrishnan is a Ph.D. student in Electrical and Computer Engineering at Carnegie Mellon University, working with Prof. Larry Pileggi. She obtained a B.Tech. in Electrical Engineering from the Indian Institute of Technology, Madras, and an M.S. in Electrical and Computer Engineering from the University of Texas at Austin. She also spent three years at Monterey Design Systems, CA, working on physical synthesis and prototyping tools for ASICs. Her research interests span various aspects of VLSI design methodologies and CAD algorithms, including applications of graph theory and optimization theory.