The General Interconnect Problem of Integrated Circuits

Ngai, 1984

Category: VLSI

Overall Rating

1.1/5 (8/35 pts)

This paper documents an early experimental routing tool based on a "stepping approach" emphasizing simplicity.
While interesting historically, its core geometric and electrical models (2 layers, coarse grid, simple RC delay) and greedy algorithms are fundamentally incompatible with modern VLSI challenges requiring multi-layer routing, dense layouts, complex timing, and signal integrity.
Rebuilding the approach for modern contexts would essentially mean designing a new router, not leveraging this specific work.

The paper's core "stepping approach," which navigates the routing problem by incrementally scanning the layout raster-by-raster... offers a fundamentally different paradigm from modern global-then-detailed routers.
This approach... could be highly relevant for routing challenges in non-uniform or dynamically changing physical substrates and connectivity landscapes where traditional global optimization is infeasible or too slow.
For instance, in emerging areas like in-memory computing architectures... the concept of processing the interconnect space incrementally... might be more robust and adaptable than algorithms requiring a complete global view.
Furthermore, the paper's discussion of a "Three Dimensional Hierarchy"... aligns with modern 3D integrated circuits and heterogeneous integration (chiplets).

The paper's core assumptions about the routing environment are severely outdated. It is primarily rooted in the late 1970s/early 1980s nMOS technology paradigm, explicitly mentioning a 7λ minimum spacing on a routing grid and focusing on a two-conducting-layer model...
The simple RC delay model... is inadequate for modern high-frequency designs where inductance, signal integrity (crosstalk), IR drop, and dynamic power noise are critical factors...
This paper likely faded into obscurity because its chosen algorithmic approach ("stepping," "greedy") prioritized simplicity and fast turnaround over optimization...
The result on the Deutsch benchmark (21 tracks vs. 19/20 for others, Section 4.2.2) demonstrates its inferiority even compared to contemporary channel routers...

Ignore