Timing-driven partitioning-based placement for island style FPGAs

Pongstorn Maidee, Cristinel Ababei, Kia Bazargan

Research output: Contribution to journalArticle

41 Scopus citations

Abstract

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
Volume24
Issue number3
DOIs
StatePublished - Mar 1 2005

Keywords

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

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

  • Cite this