跳轉到

1983-Magic版圖編輯器#

案件摘要#

1980 年代初，版圖編輯器的老問題：工程師畫一條線，DRC（設計規則檢查）要跑幾分鐘甚至更久——互動設計淪為「畫一筆、泡咖啡、看結果」。1983-84 年，UC Berkeley 的 John Ousterhout 發表 Magic 版圖編輯器，背後是兩件法寶：角針織（corner stitching）資料結構——把每個矩形用「角落 + 針線」指標連結，相鄰關係 \(O(1)\) 級取得；增量式 DRC——只檢查被編輯區域的鄰近窗口，幾何檢查從全圖掃描降到局部常數。Magic 證明：資料結構選對，互動式設計與即時驗證可以同時發生。它成為學術界二十年的標準工具，其思想活在今日所有互動式版圖編輯器與 signoff 工具的增量式檢核裡。

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

  • 全圖 DRC 的鈍刀：掃描線 DRC（1976）已把複雜度降到 \(O(n \log n)\) ，但那是「全圖跑一次」的批處理模式；互動編輯需要「改一格、查一格」的即時回應。
  • Mead-Conway 的需求（1980）：符號版圖與 λ 規則讓大學生也能設計晶片，但需要一個能即時抓錯的工具——教育革命需要工具配套。
  • 資料結構是瓶頸：當時版圖以平鋪矩形列表儲存，查「這個點被誰蓋住、旁邊有誰」要掃全表——相鄰查詢是 \(O(n)\) 。
  • Berkeley 的傳統：SPICE（1973）已樹立「工具即教材」的傳統，Magic 是同一理念的實體設計版。

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

線索一：角針織——把平面切成針織布#

Ousterhout 的核心觀察：版圖中的空白（白區）與實體矩形同樣重要。角針織把整個版圖切成不重疊的矩形（實體 + 空白），每個矩形記錄四角的四條針線指標，指向右方/上方相鄰矩形：

+--------+--------+
|  R1    |  R2    |
|     east -----→ |      (east 指針連右鄰)
+--------+--------+
|  R3    |  R4    |
+--------+--------+

每個矩形儲存 (x1, y1, type, rt, tr, lb, bl)——其中 rt/tr（right-top 指標）等四個指標構成平面圖的連結表示。效果： - 點定位（point finding）：查 \((x,y)\) 所在矩形，從任一矩形出發沿指標走， \(O(\log n)\) 級（理論上均攤更快）； - 鄰居查詢：某矩形的上方鄰居沿 tr 一跳即得—— \(O(1)\) ； - 面積查詢：區域內所有矩形沿指標遍歷，只碰到相關者。

線索二：增量式 DRC——只查窗口#

編輯一個矩形時，錯誤只可能出現在被改矩形及其 3λ 鄰域（規則的影響半徑 = 最寬規則的一半）。Magic 的策略： 1. 編輯後，對「舊矩形 ∪ 新矩形 ∪ 影響半徑」的小窗口重跑檢查； 2. 窗口內用掃描線式的鄰居比對（角針織讓鄰居 \(O(1)\) 取得）； 3. 違規以紅色條紋即時標示。

\[ \text{成本} = O(\text{規則影響半徑內的鄰居數}) \approx O(1) \]

——「全圖 \(O(n \log n)\) 」變成「局部 \(O(1)\) 」，這是互動性的數學代價計算。

線索三：層次化與符號層#

Magic 支援階層式設計（cell 引用）與「抽象層」（只畫互連層，自動補 via/接觸孔）——與 Mead-Conway 的結構化設計（1980）直接銜接，讓學生專案能在個人工作站上跑。

結案 -- 後果與影響#

  • 互動式版圖設計的誕生：即時 DRC 讓「邊畫邊驗」成為標準工作模式，VLSI 設計從批處理時代進入互動時代。
  • 資料結構的教科書案例：角針織成為計算幾何與資料結構課程的經典（「用指標表達平面切割」），影響到地圖、繪圖系統的空間資料結構。
  • Ousterhout 的雙遺產：Magic 之後，Ousterhout 轉向散佈式系統（Sprite OS）與 Tcl 腳本語言——EDA 的資料結構訓練造就了通用軟體大師。
  • 增量化思想的普及：今日 signoff DRC/LVS 的增量檢核、SPICE 的增量分析，都是「只重算受影響區域」的同一推理——Magic 是這條主線的工程起點。

關鍵人物與文獻#

  • John K. Ousterhout：Berkeley，Magic 與角針織；後為 Tcl/Tk、Sprite OS、Raft 共識的作者。
  • 文獻：
  • J. K. Ousterhout, "Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools," IEEE Trans. CAD 3, 87 (1984).
  • J. K. Ousterhout et al., "Magic: A VLSI Layout System," DAC 1984.
  • G. T. Hamachi, J. K. Ousterhout, "A Switchbox Router with Obstacle Avoidance," DAC 1984（Magic 的繞線子系統）。