Two-Dimensional Compaction: Computing the Shape Function of a Slicing Layout (thesis)

Abstract:

We investigate a two dimensional compaction scheme for a slicing layout. The compaction scheme treats wires as topological entities, i.e. only the paths of wires that connect terminals of the same nets are known but not their physical locations. Wires are not present physically in the layout during compaction,
but they are expressed as constraints which describe the actual space required to accommodate them. This amounts to computing the shape function that captures the routing requirements of the layout. We present an O(k * n3) algorithm to compute the shape function of a stack of k two-component river routable channels with n nets, and a heuristic to approximate the shape function of a stack of multiple component river routable channels. We develop heuristics that use the algorithm and the heuristic above as their subroutines to approximate the shape function of a slicing layout under the restriction of river routing. The experimental results show the potential of the proposed compaction scheme. We study the asymptotic behavior of river routing and pitch aligning in uniform stacks and uniform arrays. We derive the condition under which river routing is better than pitch aligning for such uniform layouts. We discuss the problem of computing the shape function of a slicing layout with general channel routing. We use channel density as an estimate of channel width. We show an NP-completeness result for computing such a shape function. We present a pseudo-polynomial time algorithm to compute the shape function (using channel density as channel width) for a slicing layout of depth one, and we provide an efficient
heuristic to compute such a shape function. Experimental results show that the heuristic produces shape functions which are very close to the exact shape function.