Hardware accelerated local search for FPGA placement

Fobel, Christian
Journal Title
Journal ISSN
Volume Title
University of Guelph

FPGAs provide a versatile digital design platform, which is very suitable for applications such as rapid prototyping of hardware designs, or acceleration of critical sections of software programs. However, the lengthy compile times associated with current FPGA design tools are reducing the development-time advantage FPGAs offer over other technologies, such as ASICs. This problem is continually becoming worse as FPGAs increase in complexity and capacity at a faster rate than the available computational power used to perform compilation. This thesis presents two novel 'wire-length-driven' hardware FPGA placement heuristics, which attempt to reduce the time required to achieve quality placements. The first heuristic performs iterative movements of logic blocks to unoccupied positions within a system to reduce the estimated wire-length of the system. The second heuristic performs moves in a similar fashion to the first algorithm, but also allows for logic blocks to swap positions with another block if a target position is occupied. The heuristics are implemented in software, using ANSI-C, and in hardware using VHDL and Handel-C. The goal of the hardware implementations is to provide a performance increase for the algorithms over the corresponding software versions.

FPGA, wire-length-driven hardware, FPGA placement heuristics, logic blocks, performance