{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22655"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22655","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Timing-constrained layout algorithms for symmetrical field-programmable gate arrays","abstract":"In this thesis, we address timing-constrained placement and routing in symmetrical field-programmable gate arrays (FPGAs).","abstract_html":"In this thesis, we address timing-constrained placement and routing in symmetrical field-programmable gate arrays (FPGAs).","abstract_has_math":false,"creators":["Raman, Srilata"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Liu, C.L."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:46:58Z","date_published":"2011-05-07T13:46:58Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1994 Raman, Srilata"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512518","(UMI)AAI9512518"],"render_values":[{"text":"AAI9512518","href":null,"code":true},{"text":"(UMI)AAI9512518","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22655","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, C.L."]},{"key":"dc:creator","label":"Author","values":["Raman, Srilata"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:46:58Z","10000-01-01","1994"]},{"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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1994 Raman, Srilata"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512518","(UMI)AAI9512518","http://hdl.handle.net/2142/22655"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we address timing-constrained placement and routing in symmetrical field-programmable gate arrays (FPGAs).","First, we present a timing-driven placement algorithm for symmetrical FPGAs. The algorithm combines the computational simplicity of a net-based algorithm with the net length flexibility permitted by a path-based algorithm. The algorithm has three phases. First, we determine the relative placement of logic blocks in accordance with timing requirements, using the classical force-directed placement technique modified to reflect the goal of satisfying timing constraints. Second, we assign logic blocks to 2D grid positions on the array using an algorithm whose cost function incorporates timing considerations. The net weights depend on the net delays obtained from a timing analysis of the circuit. Third, the timing requirements that are not satisfied are remedied by adaptively reassigning the net weights. The first two phases are repeated with the set of new net weights to generate a solution that meets the timing constraints. Experiments indicate that the algorithm is effective in meeting all the timing constraints and in increasing the speed of the resulting circuit. The routability is not seriously degraded and the CPU time required by our algorithm is much smaller than that required by a simulated annealing based placement algorithm.","Second, we present a timing-driven routing algorithm for symmetrical FPGAs. Our algorithm exploits the architectural features of symmetrical FPGAs while providing timing-accurate routing solutions. The salient features of our algorithm are as follows. (1) Uses a one-step routing approach that combines global and detailed routing. (2) Assigns nets to routing resources dictated by the characteristics of the resource. (3) Calculates delays of sinks using the Elmore delay models. (4) Routes on a sink-by-sink, as opposed to a net-by-net basis, (referred to as incremental routing tree construction). (5) Incorporates incremental feedback of timing delays of currently routed sinks to guide the routing process.","Experimental results indicate that the algorithm is successful in meeting the timing requirements imposed on the circuit, utilizes the routing resources judiciously, completely routes all the nets, and incurs a low CPU time.","Made available in DSpace on 2011-05-07T13:46:58Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512518.pdf: 4906643 bytes, checksum: af88b25d7a7fd0dedbb3b0cc82f3a515 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:51-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Timing-constrained layout algorithms for symmetrical field-programmable gate arrays"]}]}],"canonical_facts":{"dc:contributor":["Liu, C.L."],"dc:creator":["Raman, Srilata"],"dc:date":["2011-05-07T13:46:58Z","10000-01-01","1994"],"dc:description":["In this thesis, we address timing-constrained placement and routing in symmetrical field-programmable gate arrays (FPGAs).","First, we present a timing-driven placement algorithm for symmetrical FPGAs. The algorithm combines the computational simplicity of a net-based algorithm with the net length flexibility permitted by a path-based algorithm. The algorithm has three phases. First, we determine the relative placement of logic blocks in accordance with timing requirements, using the classical force-directed placement technique modified to reflect the goal of satisfying timing constraints. Second, we assign logic blocks to 2D grid positions on the array using an algorithm whose cost function incorporates timing considerations. The net weights depend on the net delays obtained from a timing analysis of the circuit. Third, the timing requirements that are not satisfied are remedied by adaptively reassigning the net weights. The first two phases are repeated with the set of new net weights to generate a solution that meets the timing constraints. Experiments indicate that the algorithm is effective in meeting all the timing constraints and in increasing the speed of the resulting circuit. The routability is not seriously degraded and the CPU time required by our algorithm is much smaller than that required by a simulated annealing based placement algorithm.","Second, we present a timing-driven routing algorithm for symmetrical FPGAs. Our algorithm exploits the architectural features of symmetrical FPGAs while providing timing-accurate routing solutions. The salient features of our algorithm are as follows. (1) Uses a one-step routing approach that combines global and detailed routing. (2) Assigns nets to routing resources dictated by the characteristics of the resource. (3) Calculates delays of sinks using the Elmore delay models. (4) Routes on a sink-by-sink, as opposed to a net-by-net basis, (referred to as incremental routing tree construction). (5) Incorporates incremental feedback of timing delays of currently routed sinks to guide the routing process.","Experimental results indicate that the algorithm is successful in meeting the timing requirements imposed on the circuit, utilizes the routing resources judiciously, completely routes all the nets, and incurs a low CPU time.","Made available in DSpace on 2011-05-07T13:46:58Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512518.pdf: 4906643 bytes, checksum: af88b25d7a7fd0dedbb3b0cc82f3a515 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:59:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:51-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9512518","(UMI)AAI9512518","http://hdl.handle.net/2142/22655"],"dc:language":["eng"],"dc:rights":["Copyright 1994 Raman, Srilata"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Timing-constrained layout algorithms for symmetrical field-programmable gate arrays"],"dc:type":["text"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}