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.

  1. http://hdl.handle.net/2429/209
Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:BVAU./209
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
LanguageEnglish
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Format727914 bytes, application/pdf

Page generated in 0.0021 seconds