跳轉到

1976-掃描線DRC#

案件摘要#

版圖畫好了，但金屬線間距 2μm、寬度 3μm——數百萬個幾何圖形，兩兩比對是 \(O(n^2)\) 的天文數字。1970 年代，幾何演算法找到了破案招式：掃描線（sweep line）——一根垂直線從左到右掃過版圖，只維護「正在掃描線上」的活動邊有序表，規則檢查只發生在掃描線的鄰近窗口。寬度、間距、包含等 DRC（設計規則檢查）從 \(O(n^2)\) 降到 \(O(n \log n)\) ——這是計算幾何與 EDA 的第一次深度合流，也是 Calma GDSII（1978）到今日 signoff DRC 引擎共同的核心演算法。

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

  • 製程規則越來越細：微影對位誤差使「線太窄、間距太小」都會短路或斷路，DRC 是流片前的生死關。
  • 暴力兩兩比對不可行： \(n\) 個矩形的寬度/間距檢查是 \(\binom{n}{2}\) 級；1970 年代的記憶體與 CPU 完全撐不住。
  • GDSII 格式（Calma, 1978）讓版圖以幾何資料流通，但檢查演算法仍是瓶頸——資料有了，偵辦手段缺。
  • 計算幾何就緒：區間樹、平衡樹、平面掃描（Bentley-Ottmann 1979 的線段交點掃描線）等工具已成熟。

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

核心：事件驅動的掃描線#

矩形集合 \(R = \{r_1, \dots, r_n\}\) 。掃描線沿 \(x\) 軸移動，事件有兩種： - 左邊界事件：矩形進入活動表（插入， \(O(\log n)\) ）； - 右邊界事件：矩形離開（刪除）。

活動表按 \(y\) 座標排序（紅黑樹/區間樹）。不變量：任何間距違規的兩矩形，其 \(x\) 區間必然同時與掃描線重疊的某時刻進入活動表——所以只需在活動表的鄰居間檢查 \(y\) 向規則：

\[ |y_a - y_b| < \text{spacing} \Rightarrow \text{violation} \]
import bisect

def scanline_spacing(rects, spacing):
    """rects: [(x1,y1,x2,y2)]，掃描線檢查 y 向間距（示意）。"""
    events = sorted({(r[0], 'in', i) for i, r in enumerate(rects)} |
                    {(r[2], 'out', i) for i, r in enumerate(rects)})
    active = {}            # y1 -> y2
    bad = []
    for x, kind, i in events:
        if kind == 'in':
            y1, y2 = rects[i][1], rects[i][3]
            ys = sorted(active)
            j = bisect.bisect_left(ys, y1)
            for yy in ys[max(0, j-1):j+1]:      # 只查鄰居
                if abs(yy - y1) < spacing and active[yy] > y1 - spacing:
                    bad.append((i, x))
            active[y1] = y2
        else:
            active.pop(rects[i][1], None)
    return bad

複雜度：事件排序 \(O(n \log n)\) + 每事件樹操作 \(O(\log n)\) + 只查常數個鄰居 ⇒ \(O(n \log n)\) ，對比暴力 \(\binom{n}{2}\) ——這是指數級到近線性的降維。

延伸：面積規則與多層#

  • 面積/密度規則（CMP 均勻性）：用掃描線維護累計面積的滑動窗口；
  • 多層規則（via 覆蓋、通孔到線）：掃描線 + 分層活動表，窗口規則不變；
  • Bentley-Ottmann（1979）：同樣的掃描線框架解線段交點枚舉，成為 polygon boolean（AND/OR/XOR）的基礎，而 polygon boolean 正是 LVS（佈圖與網表比對）與 fill（dummy fill）的引擎。

結案 -- 後果與影響#

  • DRC 從不可行變成例行公事：掃描線讓數百萬圖形的檢查在主機上以小時級完成，1970 年代末的 VLSI 流片從此必過 DRC。
  • 計算幾何的第一次工業化：區間樹、掃描線、平面圖論自此成為 EDA 物理驗證的標準工具箱，反哺計算幾何學科本身。
  • LVS/opc/fill 的共同引擎：掃描線框架延伸出的 polygon boolean，支撐了 LVS 比對、dummy fill、OPC 預處理——一族演算法吃下整個 physical verification。
  • Magic 的增量式補集（1983）：Ousterhout 把掃描線檢查限定在被編輯的局部區域，實現互動式即時 DRC——掃描線 + 增量化的合流。

關鍵人物與文獻#

  • Jon L. Bentley, Derick Wood 等計算幾何學者：掃描線框架的理論化。
  • 文獻：
  • J. L. Bentley, D. Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. Computers C-29, 571 (1980).
  • J. L. Bentley, T. A. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections," IEEE Trans. Computers C-28, 643 (1979).
  • G. E. Uhler? （略）——工業實現：Calma GDSII 系統手冊（1978）。