Abstract
With the increasing density of VLSI circuits, interconnection wires are getting packed even closer. This has increased the effect of interaction between wires on circuit performance and hence, the importance of controlling crosstalk. Maze routing is a robust and general approach which can be used in many situations including multi-layer interconnections. In this paper, we consider crosstalk avoidance in maze routing. The crosstalk-constrained maze routing problem is first formulated. Then we show it is equivalent to the multi-constrained shortest path problem and is strongly NP-complete. Based on the Lagrangian relaxation technique, an effective heuristic algorithm is designed to solve the problem.
| Original language | English (US) |
|---|---|
| Pages | 628-633 |
| Number of pages | 6 |
| State | Published - 1997 |
| Externally published | Yes |
| Event | Proceedings of the 1997 International Conference on Computer Design - Austin, TX, USA Duration: Oct 12 1997 → Oct 15 1997 |
Other
| Other | Proceedings of the 1997 International Conference on Computer Design |
|---|---|
| City | Austin, TX, USA |
| Period | 10/12/97 → 10/15/97 |
ASJC Scopus subject areas
- Hardware and Architecture
- Electrical and Electronic Engineering