Minimum Density Interconnection Trees

Report
Authors:Alpert, C, Department of Computer ScienceUniversity of Virginia Cong, J, Department of Computer ScienceUniversity of Virginia Kahng, A, Department of Computer ScienceUniversity of Virginia Robins, G, Department of Computer ScienceUniversity of Virginia Sarrafzadeh, M, Department of Computer ScienceUniversity of Virginia
Abstract:

We discuss a new minimum density objective for spanning and Steiner tree constructions in the plane. This formulation is motivated particularly by the need for balanced usage of routing resources to achieve minimum-area VLSI layouts. We present two efficient heuristics for constructing low-density spanning trees, and prove that their outputs are within small constants of optimal with respect to both tree weight and density. Our proof techniques suggest a non-uniform lower bound schema, which may be used to establish the quality of the heuristic solution for any given instance. More interesting is the fact that the minimum density objective can be transparently combined with a number of previous interconnection objectives, without affecting the solution quality with respect to these previous metrics. As examples, we show how sets of competing measures (e.g., cost, density, radius; or cost, density, skew) can be simultaneously optimized. Extensive simulation results suggest that applications to VLSI global routing are promising.
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Alpert, C, J Cong, A Kahng, G Robins, and M Sarrafzadeh. "Minimum Density Interconnection Trees." University of Virginia Dept. of Computer Science Tech Report (1992).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1992