A Fast Heuristic Technique for FPGA Placement based on Multilevel Clustering
By Du Peng, December 2003
Abstract:
Field-Programmable Gate Arrays (FPGAs) are semiconductor chips that can realize most
digital circuits on site by specifying programmable logic and their interconnections.
The use of FPGAs has grown almost exponentially because they dramatically reduce
design turn-around time and start-up cost for electronic products compared with
traditional Application-Specific Integrated Circuits (ASICs).
A set of Computer-Aided Design (CAD) tools is required to $compile$ hardware
description into bitstream files that are used to configure the target FPGA to
implement the desired circuits. Currently, the compile time, which is dominated by
$placement$ and $routing$ time can easily take hours or even days to complete for
large (8-million gate) FPGAs. With 40-million gate FPGAs on the horizon, these
prohibitively long compile times may nullify the time-to-market advantage of FPGAs.
This research presents two novel placement heuristics that significantly reduce the
amount of computation time required to achieve high-quality placements, compared
with VPR, which is considered to be a state-of-the-art
FPGA placement and routing tool.
