{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/26016"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/26016","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Incremental Design Techniques with Non-Preemptive Refinement for Million-Gate FPGAs","abstract":"This dissertation presents a Field Programmable Gate Array (FPGA) design methodology that can be used to shorten the FPGA design-and-debug cycle, especially as gate counts increase to many millions. Core-based incremental placement algorithms, in conjunction with fast interactive routing, are investigated to reduce the design processing time by distinguishing the changes between design iterations and reprocessing only the changed blocks without affecting the remaining part of the design. Different from other incremental placement algorithms, this tool provides the function not only to handle small modifications; it can also incrementally place a large design from scratch at a rapid rate. Incremental approaches are inherently greedy techniques, but when combined with a background refinement thread, the incremental approach offers the instant gratification that designers expect, while preserving the fidelity attained through batch-oriented programs. An incremental FPGA design tool has been developed, based on the incremental placement algorithm and its background refiner. Design applications with logical gate sizes varying from tens of thousands to approximately one million are built to evaluate the execution of the algorithms and the design tool. The results show that this incremental design tool is two orders of magnitude faster than the competing approaches such as the Xilinx M3 tools without sacrificing much quality. The tool presented places designs at the speed of 700,000 system gates per second. The fast processing speed and user-interactive property make the incremental design tool potentially useful for prototype developing, system debugging and modular testing in million-gate FPGA designs.","abstract_html":"This dissertation presents a Field Programmable Gate Array (FPGA) design methodology that can be used to shorten the FPGA design-and-debug cycle, especially as gate counts increase to many millions. Core-based incremental placement algorithms, in conjunction with fast interactive routing, are investigated to reduce the design processing time by distinguishing the changes between design iterations and reprocessing only the changed blocks without affecting the remaining part of the design. Different from other incremental placement algorithms, this tool provides the function not only to handle small modifications; it can also incrementally place a large design from scratch at a rapid rate. Incremental approaches are inherently greedy techniques, but when combined with a background refinement thread, the incremental approach offers the instant gratification that designers expect, while preserving the fidelity attained through batch-oriented programs. An incremental FPGA design tool has been developed, based on the incremental placement algorithm and its background refiner. Design applications with logical gate sizes varying from tens of thousands to approximately one million are built to evaluate the execution of the algorithms and the design tool. The results show that this incremental design tool is two orders of magnitude faster than the competing approaches such as the Xilinx M3 tools without sacrificing much quality. The tool presented places designs at the speed of 700,000 system gates per second. The fast processing speed and user-interactive property make the incremental design tool potentially useful for prototype developing, system debugging and modular testing in million-gate FPGA designs.","abstract_has_math":false,"creators":["Ma, Jing"],"institution":"Virginia Tech","degree_name":"Ph. D.","degree_level":"doctoral","degree_discipline":"Electrical and Computer Engineering","degree_department":"Electrical and Computer Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Jones, Mark T.","Athanas, Peter M."],"committee_members":["Varadarajan, Srinidhi","Woerner, Brain D.","Midkiff, Scott F."],"year":2003,"date_issued":"2003-01-13","date_published":"2003-01-13","updated_at":"2026-07-22T22:19:48Z","subjects":["Incremental Design","Design Tool","Field programmable gate arrays","Placement"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-01202003-151943"],"render_values":[{"text":"etd-01202003-151943","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/26016","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Jones, Mark T.","Athanas, Peter M."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Varadarajan, Srinidhi","Woerner, Brain D.","Midkiff, Scott F."]},{"key":"dc:contributor.department","label":"Department","values":["Electrical and Computer Engineering"]},{"key":"dc:creator","label":"Author","values":["Ma, Jing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T20:06:48Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T20:06:48Z","2004-01-22"]},{"key":"dc:date.issued","label":"Date","values":["2003-01-13"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Incremental Design","Design Tool","Field programmable gate arrays","Placement"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-01202003-151943"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/26016"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This dissertation presents a Field Programmable Gate Array (FPGA) design methodology that can be used to shorten the FPGA design-and-debug cycle, especially as gate counts increase to many millions. Core-based incremental placement algorithms, in conjunction with fast interactive routing, are investigated to reduce the design processing time by distinguishing the changes between design iterations and reprocessing only the changed blocks without affecting the remaining part of the design. Different from other incremental placement algorithms, this tool provides the function not only to handle small modifications; it can also incrementally place a large design from scratch at a rapid rate. Incremental approaches are inherently greedy techniques, but when combined with a background refinement thread, the incremental approach offers the instant gratification that designers expect, while preserving the fidelity attained through batch-oriented programs. An incremental FPGA design tool has been developed, based on the incremental placement algorithm and its background refiner. Design applications with logical gate sizes varying from tens of thousands to approximately one million are built to evaluate the execution of the algorithms and the design tool. The results show that this incremental design tool is two orders of magnitude faster than the competing approaches such as the Xilinx M3 tools without sacrificing much quality. The tool presented places designs at the speed of 700,000 system gates per second. The fast processing speed and user-interactive property make the incremental design tool potentially useful for prototype developing, system debugging and modular testing in million-gate FPGA designs."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Incremental Design Techniques with Non-Preemptive Refinement for Million-Gate FPGAs"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Jones, Mark T.","Athanas, Peter M."],"dc:contributor.committeemember":["Varadarajan, Srinidhi","Woerner, Brain D.","Midkiff, Scott F."],"dc:contributor.department":["Electrical and Computer Engineering"],"dc:creator":["Ma, Jing"],"dc:date.accessioned":["2014-03-14T20:06:48Z"],"dc:date.available":["2014-03-14T20:06:48Z","2004-01-22"],"dc:date.issued":["2003-01-13"],"dc:description.abstract":["This dissertation presents a Field Programmable Gate Array (FPGA) design methodology that can be used to shorten the FPGA design-and-debug cycle, especially as gate counts increase to many millions. Core-based incremental placement algorithms, in conjunction with fast interactive routing, are investigated to reduce the design processing time by distinguishing the changes between design iterations and reprocessing only the changed blocks without affecting the remaining part of the design. Different from other incremental placement algorithms, this tool provides the function not only to handle small modifications; it can also incrementally place a large design from scratch at a rapid rate. Incremental approaches are inherently greedy techniques, but when combined with a background refinement thread, the incremental approach offers the instant gratification that designers expect, while preserving the fidelity attained through batch-oriented programs. An incremental FPGA design tool has been developed, based on the incremental placement algorithm and its background refiner. Design applications with logical gate sizes varying from tens of thousands to approximately one million are built to evaluate the execution of the algorithms and the design tool. The results show that this incremental design tool is two orders of magnitude faster than the competing approaches such as the Xilinx M3 tools without sacrificing much quality. The tool presented places designs at the speed of 700,000 system gates per second. The fast processing speed and user-interactive property make the incremental design tool potentially useful for prototype developing, system debugging and modular testing in million-gate FPGA designs."],"dc:description.degree":["Ph. D."],"dc:identifier.other":["etd-01202003-151943"],"dc:identifier.uri":["http://hdl.handle.net/10919/26016"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Incremental Design","Design Tool","Field programmable gate arrays","Placement"],"dc:title":["Incremental Design Techniques with Non-Preemptive Refinement for Million-Gate FPGAs"],"dc:type":["Dissertation"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Ph. D."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:48Z"}