Return to search

A combined clustering and placement algorithm for FPGAs

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. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Date05 1900
CreatorsYamashita, Mark
PublisherUniversity of British Columbia
Source SetsUniversity of British Columbia
Detected LanguageEnglish
TypeText, Thesis/Dissertation
Format727914 bytes, application/pdf
RightsAttribution-NonCommercial-NoDerivatives 4.0 International,

Page generated in 0.0023 seconds