Geometric Interconnection and Placement Algorithms

This dissertation examines a number of geometric interconnection, partitioning, and placement This dissertation examines a number of geometric interconnection, partitioning, and placement problems arising in the _eld of VLSI physical design automation. In particular, many of the results concern the geometric Steiner tree problem: given a set of terminals in the plane, _nd a minimum-length interconnection of those terminals according to some geometric distance metric.

Two new algorithms are introduced that compute optimal rectilinear Steiner trees. Both are provably faster than any previous algorithm for instances small enough to solve in practice, and both are also fast in practice. The _rst algorithm is a dynamic programming algorithm based on decomposing a rectilinear Steiner tree into full trees. A full tree is a Steiner tree in which every terminal is a leaf. Its time complexity is O(n3n), where n is the number of terminals. The second algorithm modi_es the _rst by the use of full-set screening, which is a process by which some candidate full trees are eliminated from consideration. Its time complexity is approximately O(n22:62n). We demonstrate that for instances small enough to reasonably solve in practice, these algorithms are faster than has been proven for any previous algorithm. Empirical evidence is also given indicating that both algorithms are faster in practice than several other popular algorithms for computing optimal rectilinear Steiner trees.

A new theorem is proven that allows efficient computation of rectilinear Steiner trees in the presence of obstacles. This theorem leads to the first algorithms that compute optimal obstacle-avoiding rectilinear Steiner trees in time corresponding to the size of the instance (the number of terminals and obstacle border segments) rather than the size of the routing area. Two types of algorithms are presented. The _rst computes optimal rectilinear Steiner trees in the presence of obstacles for small instances. The second computes heuristic solutions to arbitrary instances. In addition, two special cases are examined: the case when all terminals lie on obstacle perimeters and the case when all terminals lie on the perimeter of the routing region.

The power-p Steiner tree problem is introduced, in which the weight of an edge is its geometric length raised to the p power. A special case of the power-p Steiner tree problem is also considered: the bottleneck Steiner tree problem, which is to _nd a geometric Steiner tree with the length of the longest edge minimized. Algorithms are described for computing optimal optimal Euclidean power-2 Steiner trees, rectilinear bottleneck Steiner trees, and rectilinear Steiner trees that minimize a combination of bottleneck weight and total length. The power-p Steiner tree problem for p > 2 is also considered, and evidence given that the problem is essentially unsolvable for large p. In addition, bounds are given on the power-p Steiner ratio, which measures the quality of a minimum spanning tree as an approximation of a power-p Steiner tree. The exact value of the bottleneck Steiner ratio is also derived, and a fully polynomial-time approximation scheme is given for computing a bottleneck Steiner tree with a given topology in any distance metric. of the routing region.

Finally, a system called Mondrian is presented that performs simultaneous placement and global routing in _eld-programmable gate arrays (FPGAs). Mondrian is a recursive geometric partitioning strategy using optimal rectilinear Steiner trees of terminals that lie in a small grid. Experimental results show that Mondrian produces results signi_cantly superior to those of previous FPGA layout algorithms. In addition, we present a modi_ed
version of Mondrian that computes performance-driven placement and routing solutions, in which more accurate estimates of electrical delay are optimized. The development of Mondrian includes several results of independent interest, such as minimum-congestion routing in a cycle and computing optimal rectilinear Steiner trees for terminals in a small grid.