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.

Date05 1900
CreatorsYamashita, Mark
PublisherUniversity of British Columbia
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation

Page generated in 0.1302 seconds