Timing-driven partitioning-based placement for island style FPGAs

Pongstorn Maidee, Cristinel Ababei, Kia Bazargan

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but at the expense of significant runtime penalties (Nag and Rutenbar, 1998). We propose a routing-aware partitioning-based placement algorithm for FPGAs in which a looser but effective coupling between the placement and routing stages is used. The placement engine incorporates a more accurate FPGA delay model and employs effective heuristics that minimize circuit delay. Delay estimations are obtained from routing profiles of selected circuits that are placed and routed using the timing-driven versatile place and route (TVPR) (Betz and Rose, 1997), (Marquardt et al., 2000). 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 applied during placement to further optimize the delay of the circuit. These two techniques help maintain harmony between placement and routing-delay optimization stages. Simulation results show that the proposed partitioning-based placement combined with more accurate delay models and the alignment heuristic can achieve postrouting circuit delays comparable to those obtained from TVPR, while achieving a fourfold speedup in total placement runtime. In another experiment, we augmented the original TVPR algorithm with the terminal alignment heuristic, and achieved, on average, a 5% improvement in circuit delay with negligible runtime penalty.

Original languageEnglish (US)
Pages (from-to)395-406
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
StatePublished - Mar 2005

Bibliographical note

Funding Information:
Manuscript received October 18, 2003; revised February 16, 2004. This work was supported in part by the Office of the Vice President for Research and Dean of the Graduate School, University of Minnesota, under Grant 1546-522-5980. This paper was recommended by Associate Editor M. Sarrafzadeh.


  • Delay estimation
  • FPGA placement
  • Field programmable gate arrays (FPGA)
  • Partitioning-based placement
  • Timing-driven placement


Dive into the research topics of 'Timing-driven partitioning-based placement for island style FPGAs'. Together they form a unique fingerprint.

Cite this