跳轉到

1971-左緣演算法通道繞線#

案件摘要#

板上有兩排元件，中間是一條「通道（channel）」：上排的接腳要與下排或側邊的接腳相連，訊號在通道裡水平走、垂直進出。「至少要幾條水平軌道（tracks）才繞得完？」是通道繞線的核心懸案。1971 年，A. Hashimoto 與 J. Stevens 在第八屆 DAC 發表左緣演算法（Left-Edge Algorithm）：把每條 net 的水平跨度看成區間，按左端點排序，貪心把區間塞進第一條放得下的軌道。這個三行程的貪心，在「無垂直衝突」條件下可證明軌道數最少——EDA 演算法史上少數有最優性保證的亮案，也是所有軌道分配演算法的祖師。

前因 -- 為什麼會有這個案子#

  • PCB/IC 的雙排結構：SOG（sea-of-gates）與標準單元時代，單元成排擺放，單元間的通道是繞線資源的主戰場。
  • 通道面積 = 高度 × 寬度：通道高度由軌道數決定，軌道數直接換算成晶片面積與成本。
  • 迷宮法太盲目：Lee/線搜尋一次處理一條 net，不看全通道——全域觀點的「軌道分配」缺演算法。
  • 區間圖著色的理論就緒：「區間重疊不可同軌」正是圖著色的區間特例，而區間圖著色有已知的多項式最優解。

線索與推理 -- 數學式、程式、理論#

建模：區間圖著色#

每條 net \(i\) 的水平跨度是區間 \([l_i, r_i]\) 。兩 net 的區間重疊 ⇒ 不能共用同一軌道（會短路）。定義區間圖 \(G\) ：頂點是 net，邊 = 區間重疊。軌道分配 = 給 \(G\) 著色，軌道數 = 色數 \(\chi(G)\) 。

區間圖的關鍵性質： \(\chi(G) = \omega(G)\) （色數等於最大團），而區間圖的最大團 = 任一點被覆蓋的最大重疊數。因此最優軌道數 = 通道中同時活躍的最大 net 數（垂直密度 D）。

左緣貪心：為什麼最優#

  1. 把所有區間按左端點 \(l_i\) 排序；
  2. 依序處理：把區間放進第一條右端 \(\le l_i\) 的既有軌道；都不行則開新軌道。
def left_edge(intervals):
    """intervals: [(l, r, net_id)]，回傳 {net_id: track}。"""
    tracks = []                    # 每條軌道記錄最後右端
    assign = {}
    for l, r, net in sorted(intervals):
        for t, last_r in enumerate(tracks):
            if last_r <= l:        # 放得下（不重疊）
                tracks[t] = r; assign[net] = t; break
        else:
            tracks.append(r); assign[net] = len(tracks) - 1
    return assign, len(tracks)

ivs = [(0,4,'A'), (1,2,'B'), (3,6,'C'), (5,7,'D')]
print(left_edge(ivs))   # {'A':0,'B':1,'C':1,'D':0} → 2 條軌道

最優性證明骨架：處理區間 \(i\) 時若被迫開新軌道，則當前所有軌道的右端都 \(> l_i\) ，加上 \(i\) 本身， \(l_i\) 處有 \(t+1\) 個區間重疊 ⇒ 密度 \(D \ge t+1\) ，新軌道數 \(t+1\) 不超過下界。故貪心恰好用滿下界——貪心 = 最優（這是「可交換性/貪心選擇性質」的教科書案例）。

邊界：垂直衝突#

兩 net 區間不重疊但垂直端點相撞（一條的右端與另一條的左端在同一列、且上下 pin 衝突）時，左緣演算法的解不再可行——此時須 dogleg（分段折線，Deutsch 1976）或改用啟發式通道繞線（Yoshimura-Kuo 1988）。左緣的最優性只屬於「無垂直衝突」的理想世界，但它是所有現實演算法的起點與下界。

結案 -- 後果與影響#

  • 軌道分配的祖師：所有通道繞線器、標準單元繞線器的 track assignment 階段都直接或間接使用左緣思想（或其變體：右緣、最小右端等）。
  • 理論的教科書案例：區間圖 \(\chi = \omega\) 的性質與左緣最優性證明，成為演算法教材的經典範例——EDA 反哺理論的少數亮案。
  • 通道繞線的兩難路線：左緣（幾何貪心）與 Deutsch dogleg、Yoshimura-Kuo（垂直約束圖）構成 1970-80 年代通道繞線的雙主流，直到通道消失（over-the-cell routing, 1990s）。
  • 面積估算的公式化：左緣給出「通道高度 = 密度下界可達」的結論，讓 floorplanning 階段可提前估算繞線面積。

關鍵人物與文獻#

  • A. Hashimoto, J. Stevens：Univac/Sperry，通道繞線建模先驅。
  • 文獻：
  • A. Hashimoto, J. Stevens, "Wire Routing by Optimizing Channel Assignment within Large Apertures," 8th Design Automation Workshop, 1971.
  • D. N. Deutsch, "A 'Dogleg' Channel Router," DAC 1976.
  • T. Yoshimura, E. S. Kuh, "Efficient Algorithms for Channel Routing," IEEE TCAD 1, 25 (1982).