[EDA] Design Challenge in Rouoting Algorithm - 繞線演算法的設計困難處

在 IC 設計中，Routing (中譯：繞線) 的用意就是把需要連接的地方用金屬線連起來，概念很簡單。要判別一個 routing 結果的好與壞也很容易：計算總線長就好。因為總線長越長也就意謂著需要越多的金屬線以及空間，所以如果有許多種不同的 routing 結果，我們會選擇總線長最少的那個當成最後結果。

隨著製程的演進，現在 routing 要考慮的因素越來越多，因此在演算法的設計上也就越趨複雜，而且通常難以有個通盤考量的好結果。這一篇要來簡單的總結現在 routing 上最重要的設計考量 - 繞線資源的規劃與使用 (routing resource estimation & management, 以下簡寫 RREM)

誠如前面所提，routing 這問題本質上只是想要找個方法用金屬線把數個點連接起來，並且讓所使用的金屬線總線長最小，如此而已。在早期 IC 的大小還很小的時後，這問題可以轉成最短路徑問題 (shortest-path problem)，如果沒有特殊考量，甚至可以直接利用寬度優先搜尋 (breadth-first-search, BFS) 來解。然而，在現今動輒有數十萬、上百萬條線要連接的情況下，即便是最簡單的 BFS 都很費時。2000 年初頭有不少篇論文在強調其發展的 routing 演算法不但效能快、routing 結果又好，說穿了就是針對其所發現的特性所提出的演算法可以比 BFS 快，但又能有相當好的 routing 結果，自然就速度又快、品質也好。然而隨著製程的進步，現在 routing 要考慮的因素越來越多、也越來越雜。比方說，你的金屬線不能有特定的形狀、兩條線的距離會依據他周遭的金屬線狀況有所不同...等等之類會大幅增加 routing 複雜的討厭規定，因此現在設計 routing 的演算法其實有一個相當重要的關鍵點：評估並管理可用的繞線資源 (RREM)。這原因在於當有非常多的線要連接，同時又要遵守如上述多如牛毛又很找麻煩的規範時，如何妥善且有效率的分配可用的繞線資源絕對是開發高品質繞線演算法的關鍵。

RREM 的其中一項關鍵在於 "評估"，也就是如何準確的評估假設用 A 方法完成繞線，大致會用掉多少繞線資源 (routing resource) 以及會對其他尚未接起來的金屬線造成多少影響；相對的，如果是 B 方法? C 方法? ... 藉由評估數種不同的繞線方式的好與壞，事先就可以掌握要採用哪種方法比較好。當然，這個評估越準確，我們可以對繞線的結果有更精確的掌握，因為 RREM 就像是對未來的預測並加以控制，預測的越準確也就越能準確的知道後果並且加以控制。然而越精準的評估往往代價就是高昂的執行時間，更甚者，有時評估的難度在於如果想要精準的評估，只能實際產生一個結果去計算；想要依據評估的結果去 routing，卻又因為必須先有結果才能開始評估，換言之，這是個雞生蛋、蛋生雞的難解問題，這也正是 RREM 的困難之處。所以可以非常準確的預測未來的幾乎都是神棍。

一般來說為了解決這種雞生蛋、蛋生雞的討厭問題，常見的做法是這樣：

1. 先根據許多的假設提出一個簡陋的評估方式
2. 根據 1 先產生一個初步的繞線結果，當然，這繞線結果肯定有很多問題
3. 基於 2 的結果改良第 1 點的評估方式，並藉此產生新的繞線結果
4. 重複 2 ~ 3，並且設定好結束條件

這種漸進式的架構其概念就是先把問題做簡化，基於簡化後的問題提出一個解法，再慢慢的把先前簡化的條件放寬，並修正繞線演算法，最終得以有個通盤考量所有問題的評估方式以及繞線演算法。

RREM 的發展會隨著製程的演進而持續的改良，因為當有新的製程出現就意謂著有新的規則要遵守，也因此必須持續的修改 RREM。即便是相同的製程，有更準確與快速的 RRM 就意謂著可以產生比別人更好的結果。不過要有非常突破性的方法很難，所以往往都是針對新發現的問題提出另一種改良後的 RREM，畢竟有論文產出的壓力時，這樣做比較快，但也因此會發現不同的 RREM 往往基本概念都是一樣的 (笑)。