{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20933"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20933","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms for VLSI routing","abstract":"This thesis considers the problems arising from VLSI routing design. Algorithms are proposed for solving both global and local routing problems.","abstract_html":"This thesis considers the problems arising from VLSI routing design. Algorithms are proposed for solving both global and local routing problems.","abstract_has_math":false,"creators":["Zhou, Dian"],"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":["Preparata, Franco P."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:53:30Z","date_published":"2011-05-07T12:53:30Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Zhou, Dian"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114483","(UMI)AAI9114483"],"render_values":[{"text":"AAI9114483","href":null,"code":true},{"text":"(UMI)AAI9114483","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20933","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Preparata, Franco P."]},{"key":"dc:creator","label":"Author","values":["Zhou, Dian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:53:30Z","10000-01-01","1990"]},{"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 1990 Zhou, Dian"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114483","(UMI)AAI9114483","http://hdl.handle.net/2142/20933"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis considers the problems arising from VLSI routing design. Algorithms are proposed for solving both global and local routing problems.","For routing multiterminal nets in the gate array and sea-of-gates technologies, we present a global router which upper bounds the global density of the routing by 2$s\\sp{\\*}$, where $s\\sp{\\*}$ is the span of the nets. For standard cell technology, we present a global router which achieves the optimal horizontal density while upper bounding the vertical density by 2$s\\sp{\\*}$. The parallel implementations of the proposed global routing algorithms are presented.","For the local routing problem, we first investigate the efficiency of the Manhattan routing model. We study in detail how the grid points are used in the Manhattan model and, consequently, establish a general lower bound on the channel width for routing two-terminal nets in a channel. All of the previous known results (lower bounds on the channel width) can be derived from our general lower bound. Furthermore, an asymptotically tight lower bound is obtained. We are also able to establish the lower bounds on the routing area for routings in L-, S-, T- and X-junctions in both the Manhattan and knock-knee models.","For routing in an arbitrary rectilinear polygon, which is a generalization of many local routing problems, we present a sublinear time algorithm running in O(m log$\\sp2$ m), where m is the number of edges in the boundary of the polygon. The presented algorithm produces the minimal routing area. For routing in the restricted wire-overlap model, we present an optimal algorithm which constructs a routing with minimum channel width. In the routing produced by the algorithm, the length of the wire overlap between any two nets is upper bounded by O(k), where k is the multiplicity of the nets.","Made available in DSpace on 2011-05-07T12:53:30Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114483.pdf: 4808851 bytes, checksum: 2213ae5777f3c533662984997779515a (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:47:21Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:21:22-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":["Algorithms for VLSI routing"]}]}],"canonical_facts":{"dc:contributor":["Preparata, Franco P."],"dc:creator":["Zhou, Dian"],"dc:date":["2011-05-07T12:53:30Z","10000-01-01","1990"],"dc:description":["This thesis considers the problems arising from VLSI routing design. Algorithms are proposed for solving both global and local routing problems.","For routing multiterminal nets in the gate array and sea-of-gates technologies, we present a global router which upper bounds the global density of the routing by 2$s\\sp{\\*}$, where $s\\sp{\\*}$ is the span of the nets. For standard cell technology, we present a global router which achieves the optimal horizontal density while upper bounding the vertical density by 2$s\\sp{\\*}$. The parallel implementations of the proposed global routing algorithms are presented.","For the local routing problem, we first investigate the efficiency of the Manhattan routing model. We study in detail how the grid points are used in the Manhattan model and, consequently, establish a general lower bound on the channel width for routing two-terminal nets in a channel. All of the previous known results (lower bounds on the channel width) can be derived from our general lower bound. Furthermore, an asymptotically tight lower bound is obtained. We are also able to establish the lower bounds on the routing area for routings in L-, S-, T- and X-junctions in both the Manhattan and knock-knee models.","For routing in an arbitrary rectilinear polygon, which is a generalization of many local routing problems, we present a sublinear time algorithm running in O(m log$\\sp2$ m), where m is the number of edges in the boundary of the polygon. The presented algorithm produces the minimal routing area. For routing in the restricted wire-overlap model, we present an optimal algorithm which constructs a routing with minimum channel width. In the routing produced by the algorithm, the length of the wire overlap between any two nets is upper bounded by O(k), where k is the multiplicity of the nets.","Made available in DSpace on 2011-05-07T12:53:30Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114483.pdf: 4808851 bytes, checksum: 2213ae5777f3c533662984997779515a (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:47:21Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:21:22-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":["AAI9114483","(UMI)AAI9114483","http://hdl.handle.net/2142/20933"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Zhou, Dian"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Algorithms for VLSI routing"],"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:16Z"}