{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19656"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19656","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Routing algorithms in the physical design of VLSI circuits","abstract":"In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.","abstract_html":"In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.","abstract_has_math":false,"creators":["Cong, Jingsheng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, C.L."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:14:20Z","date_published":"2011-05-07T12:14:20Z","updated_at":"2026-07-22T22:25:14Z","subjects":["Engineering, Electronics and Electrical","Physics, Electricity and Magnetism","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Cong, Jingsheng"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114210","(UMI)AAI9114210"],"render_values":[{"text":"AAI9114210","href":null,"code":true},{"text":"(UMI)AAI9114210","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19656","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":["Cong, Jingsheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:14:20Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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","Physics, Electricity and Magnetism","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 Cong, Jingsheng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9114210","(UMI)AAI9114210","http://hdl.handle.net/2142/19656"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.","Chapter 2 and 3 address some global routing problems in the physical design of VLSI circuits. In Chapter 2, we present a global routing algorithm for standard cell design which connects all the nets in parallel. We show that only a linear number of possible connections need to be considered by our algorithm. In Chapter 3, we present an algorithm which combines the pin assignment step and the global routing step in the general cell design style. The complexity of the combined problem is reduced based on the block boundary decomposition.","In Chapter 4 and 5, we study some detailed routing problems. In Chapter 4, we show how to enhance channel compaction results by modifying the initial grid-based routing solution. We show that proper track permutation and local re-routing lead to significant reduction in channel routing area. In Chapter 5, we study a new channel routing model called over-the-cell channel routing. We show that the over-the-cell routing problem can be solved in three steps and we present efficient solutions to the sub-problems at each step.","In Chapter 6, we study the planar subset problem and the topological via minimization in multi-layer routing models. We show that the general problems are NP-hard and we give efficient solutions to the restricted problems.","Made available in DSpace on 2011-05-07T12:14:20Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114210.pdf: 5617450 bytes, checksum: 86c5d3ecf7076a4b886be42013f728bc (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:38:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:05-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":["Routing algorithms in the physical design of VLSI circuits"]}]}],"canonical_facts":{"dc:contributor":["Liu, C.L."],"dc:creator":["Cong, Jingsheng"],"dc:date":["2011-05-07T12:14:20Z","10000-01-01","1990"],"dc:description":["In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.","Chapter 2 and 3 address some global routing problems in the physical design of VLSI circuits. In Chapter 2, we present a global routing algorithm for standard cell design which connects all the nets in parallel. We show that only a linear number of possible connections need to be considered by our algorithm. In Chapter 3, we present an algorithm which combines the pin assignment step and the global routing step in the general cell design style. The complexity of the combined problem is reduced based on the block boundary decomposition.","In Chapter 4 and 5, we study some detailed routing problems. In Chapter 4, we show how to enhance channel compaction results by modifying the initial grid-based routing solution. We show that proper track permutation and local re-routing lead to significant reduction in channel routing area. In Chapter 5, we study a new channel routing model called over-the-cell channel routing. We show that the over-the-cell routing problem can be solved in three steps and we present efficient solutions to the sub-problems at each step.","In Chapter 6, we study the planar subset problem and the topological via minimization in multi-layer routing models. We show that the general problems are NP-hard and we give efficient solutions to the restricted problems.","Made available in DSpace on 2011-05-07T12:14:20Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9114210.pdf: 5617450 bytes, checksum: 86c5d3ecf7076a4b886be42013f728bc (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:38:32Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:05-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":["AAI9114210","(UMI)AAI9114210","http://hdl.handle.net/2142/19656"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Cong, Jingsheng"],"dc:subject":["Engineering, Electronics and Electrical","Physics, Electricity and Magnetism","Computer Science"],"dc:title":["Routing algorithms in the physical design of VLSI circuits"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:14Z"}