In
traditional 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. One of
the disconnects between placement and routing for FPGAs is the
inaccurate routing delay models used at placement level. Traditionally,
wire length minimization is used at placement, but as the following
figure shows, wire length is not a good estimation of delay for FPGAs:
net "A" is slower than "B" even though they have the same wire length
(switch delay is the dominating factor in FPGA routing). Net "C" has
the same wire length but with potentially the smallest delay because
nets "A" and "B" need at least one switch to connect their horizontal
and vertical routes. Terminals of net "C" are "aligned", and alignment
is a crucial heuristic that we use is this work. We propose a routing-aware partitioning-based placement algorithm for FPGAs in which an effective coupling between the placement and routing stages is used. The figure below shows where our work stands in comparison to previous work (reference numbers match those of our journal paper. See below):  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 TVPR. As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. The following figures show example routing profiles that we use to analyze routing resource usage.   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 post-routing circuit delays comparable to those obtained from TVPR while achieving a 4-fold speedup in total placement runtime. In another experiment, we augmented the original TVPR algorithm with the terminal alignment heuristic, and achieved on average 5% improvement in circuit delay with negligible runtime penalty.
Related Published Papers
DownloadTo download PPFF, go to the Downloads page and search PPFF.
Back to Research Page. |
