Provably Good Moat Routing

Report
Authors:Ganley, JL, Department of Computer ScienceUniversity of Virginia Cohoon, JP, Department of Computer ScienceUniversity of Virginia
Abstract:

Moat routing is the routing of nets between the input/output pads and the core circuit. In this paper, it is proved that moat routing is NP-complete under the routing model in which there are no vertical con
icts and doglegs are disallowed (i.e., every net is routed within a single track). This contrasts with the fact that channel routing is e�ciently solvable under these restrictions. The paper then presents an approximation algorithm for moat routing that computes moat routing solutions that are guaranteed to use at most three times the optimal number of tracks. Empirical results are presented indicating that for a number of industrial benchmarks, the algorithm produces solutions that are near optimal and that use signi�cantly fewer tracks than previous moat routing strategies.
Note: Abstract extracted from PDF text

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

Ganley, JL, and JP Cohoon. "Provably Good Moat Routing." University of Virginia Dept. of Computer Science Tech Report (1995).

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