Provably good moat routing
| Autor: | Joseph L. Ganley, James P. Cohoon |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Static routing
Dynamic Source Routing Equal-cost multi-path routing Computer science Routing table ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS Topology Routing Information Protocol Link-state routing protocol Hardware and Architecture Multipath routing Hardware_INTEGRATEDCIRCUITS Destination-Sequenced Distance Vector routing Electrical and Electronic Engineering Algorithm Software |
| Zdroj: | Integration. 27:47-56 |
| ISSN: | 0167-9260 |
| DOI: | 10.1016/s0167-9260(98)00015-7 |
| Popis: | 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 conflicts and doglegs are disallowed (i.e., every net is routed within a single track). This contrasts with the fact that channel routing is efficiently 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 significantly fewer tracks than previous moat routing strategies. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect