2026-09-19T13:29:14Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/19656 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Liu, C.L. Cong, Jingsheng 2011-05-07T12:14:20Z 2011-05-07T12:14:20Z 10000-01-01 1990 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 AAI9114210 (UMI)AAI9114210 http://hdl.handle.net/2142/19656 eng Copyright 1990 Cong, Jingsheng Engineering, Electronics and Electrical Physics, Electricity and Magnetism Computer Science Routing algorithms in the physical design of VLSI circuits text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.