Hierarchical Approaches to Vlsi Circuit Layout

105 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.This thesis studies two hierarchical approaches to the circuit layout problem: the top-down approach and the bottom-up approach.The first part is devoted to the traditional top-down approach, and particularly, to an important subproblem thereof called the Channel Routing Problem (CRP). The complexity of CRP in three different layout modes--the reserved mode, the knock-knee mode, and the restricted-overlap mode--is studied. Besides the conventional square grid, two new grids, the alternate grid and the 45(DEGREES) grid, are considered, and their respective versatility is assessed.In the second part, a novel bottom-up technique for solving the layout problem is proposed. The strategy is to recursively interconnect a set of modules, in conformity with the design rules. The basic step consists of merging a pair of strongly-connected modules. This technique is elaborated on and the fundamental problems of this approach are discussed.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD