2026-09-18T22:55:11Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/20933 2023-07-10 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Preparata, Franco P. Zhou, Dian 2011-05-07T12:53:30Z 2011-05-07T12:53:30Z 10000-01-01 1990 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 AAI9114483 (UMI)AAI9114483 http://hdl.handle.net/2142/20933 eng Copyright 1990 Zhou, Dian Engineering, Electronics and Electrical Computer Science Algorithms for VLSI routing text Electrical and Computer Engineering Electrical and Computer Engineering University of Illinois at Urbana-Champaign Dissertation Ph.D.