Left-Edge Channel Routing
The setting
Standard-cell chips of the 1970s and 1980s alternated rows of cells with empty channels: rectangular routing regions with pins fixed on the top and bottom edges. Inside a channel every net is wired the same way: one horizontal trunk on one of the channel's tracks, plus vertical stubs connecting the trunk to its pins. The number of tracks used is the channel's height, so every track saved was chip area saved. Channel routing was the central detailed-routing problem of its era, and left-edge is its classic algorithm.
The abstraction: nets become intervals
Ignore the vertical stubs and each net reduces to the horizontal span between its leftmost and rightmost pin:
lcolumn of the net's leftmost pinrcolumn of the net's rightmost pin
Two nets can share a track exactly when their intervals do not overlap. Packing intervals into the fewest tracks under that rule is interval-graph coloring, one of the few coloring problems a greedy algorithm solves optimally.
The recipe
Step 1 (sort). Sort the intervals by left endpoint. The sort key is the algorithm's name.
Step 2 (first fit). Take the intervals in sorted order. For each, scan the existing tracks from the top and place the trunk on the first track that fits:
r_lastright endpoint of the last interval already placed on that track
Step 3 (open). If no track fits, open a new track below the existing ones and place the trunk there.
The result is provably optimal, measured against the channel's density:
crossing can interval [l, r] crosses column c when l ≤ c ≤ r
Every net crossing a column needs its own track at that column, so no routing can use fewer tracks than the density. And the greedy sweep never uses more: it opens a new track only when every existing track overlaps the current interval's left endpoint, which means that many intervals cross that column at once. Tracks used equals density.
Vertical constraints and doglegs
Where two nets have pins in the same column, the net pinned on top must run its trunk above the net pinned on the bottom, or their vertical stubs would overlap. These vertical constraints restrict which track the greedy may choose; while they stay acyclic the sweep survives. Cycles (net A above net B in one column, B above A in another) make one-trunk-per-net routing impossible. Deutsch's dogleg router (1976) breaks the cycles by splitting a net's trunk at pin columns into several pieces on different tracks, in practice landing within a track or two of density even on hard channels; his benchmark channel, "Deutsch's difficult example", became the standard test of the era.
Watch it work: the greedy sweep
Six nets. The walkthrough shows the channel, then the sorted interval list, then one placement per step with the fit test's arithmetic spelled out; the final frame checks the result against the density bound. Vertical constraints are left out so the optimality argument is visible in pure form.
Pros, cons, and the trade-off
Strengths
- Provably optimal track count when vertical constraints are absent: greedy meets the density lower bound.
- Near-linear and simple: a sort and one sweep.
- A reusable idea: interval packing by left edge solves problems far beyond channels.
- Extensible: doglegs handle constraint cycles with small overhead.
Weaknesses
- Its world is gone: over-the-cell routing on many metal layers dissolved channels decades ago.
- Model rigidity: one trunk per net (absent doglegs), fixed pins on two edges: strong assumptions modern layouts violate everywhere.
- Vertical-constraint cycles defeat the pure algorithm; dogleg splitting is required.
- Two-layer thinking: the elegant optimality does not survive many-layer freedom.
The trade-off
Left-edge is exactness inside a restricted model: within the channel abstraction it is provably optimal, and when the abstraction was no longer used the optimality lost its application while the packing idea moved into other problems. A perfect lesson in how algorithms outlive the worlds that created them.
Is it actually used today?
The evidence for left-edge separates chip signal routing, where the channel model it was built for ended decades ago, from the places the interval-packing core still runs.
- Inside detailed routers: track assignment, packing route segments into tracks within a panel, is interval packing, and left-edge-style sweeps are standard tooling there.
- Beyond routing: register allocation over live ranges, interval scheduling, and channel-like resource assignment problems reuse the identical greedy argument.
- Teaching and exams: the cleanest optimality proof in physical design, and a perennial interview and homework favorite.