{"id":{"repo_id":"ubc","oai_identifier":"oai:circle.library.ubc.ca:2429/209"},"canonical_url":"https://search.dev.ndltd.org/etd/ubc/oai:circle.library.ubc.ca:2429/209","repository":{"repo_id":"ubc","name":"University of British Columbia","base_url":"http://circle.library.ubc.ca/oai/request"},"display":{"title":"A combined clustering and placement algorithm for FPGAs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Yamashita, Mark"],"institution":"University of British Columbia","degree_name":"Master of Applied Science - MASc","degree_level":"master's","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-24T05:07:06Z","subjects":[],"languages":["eng"],"rights":["Attribution-NonCommercial-NoDerivatives 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2429/209","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Yamashita, Mark"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["University of British Columbia"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["master's"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Applied Science - MASc"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of British Columbia"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["http://creativecommons.org/licenses/by-nc-nd/4.0/","Attribution-NonCommercial-NoDerivatives 4.0 International"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2429/209","http://circle.library.ubc.ca/bitstream/2429/209/1/ubc_2008_spring_yamashita_mark.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["727914","application/pdf"]},{"key":"dc:title","label":"Title","values":["A combined clustering and placement algorithm for FPGAs"]}]}],"canonical_facts":{"dc:creator":["Yamashita, Mark"],"dc:date":["2007"],"dc:description":["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."],"dc:format":["727914","application/pdf"],"dc:identifier":["http://hdl.handle.net/2429/209","http://circle.library.ubc.ca/bitstream/2429/209/1/ubc_2008_spring_yamashita_mark.pdf"],"dc:language":["eng"],"dc:publisher":["University of British Columbia"],"dc:rights":["http://creativecommons.org/licenses/by-nc-nd/4.0/","Attribution-NonCommercial-NoDerivatives 4.0 International"],"dc:title":["A combined clustering and placement algorithm for FPGAs"],"dc:type":["Text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["master's"],"thesis:degree_name":["Master of Applied Science - MASc"],"thesis:institution_name":["University of British Columbia"]},"updated_at":"2026-07-24T05:07:06Z"}