Open Collections

A combined clustering and placement algorithm for FPGAs

University of British Columbia

One of the major drawbacks of reprogrammable microchips, such as field-programmable gate arrays (FPGAs), is an inherent speed disadvantage over ASIC technologies. To mitigate this speed disadvantage, this thesis presents a novel algorithm to improve timing performance at the possible expense of area and runtime. The algorithm presented leverages node duplication and a depth-optimal initial clustering to provide a starting point for a non-greedy, iterative optimization technique using detailed placement and timing information to develop the final clustering and placement solutions. For a set of benchmarks commonly used in FPGA research, the proposed algorithm achieves an 11\% critical-path delay improvement compared to the VPR academic tool flow. This performance improvement is obtained at the expense of a 44\% increase in area usage and a 26x increase in maximum runtime. Techniques have also been implemented to sacrifice performance to moderate the area or runtime increases. For a 1\% critical-path delay penalty, the runtime can be improved by a factor of 4. The algorithm also provides facilities to impose area restrictions, in which case timing degradation is proportional to the area saved.

Thesis/Dissertation

application/pdf

2007-12-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/209

Electrical and Computer Engineering

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/