[EDA] Routing Resource Estimation & Planning - Pattern Routing

• Resource Estimation: 重點主要是放在估算可用的 routing resource

• Resource Planning: 重點偏向粗略規劃 routing 的結果

其實這兩者現在很少有人分開來講，原因在於 planning 的結果先決條件就是估算可用的 routing resource 這一步算得有多準；相對的，estimation 做得再好，沒有 planning 就沒有意義，因此就我的經驗來說，目前沒有人會特地把這二步分開來講，而是提出一套完整的方法同時包含這二個步驟。這次就先整理最簡單、也最常被使用的一個方法：pattern routing，概念是來自於 [1] 這篇論文。

其實說穿了 pattern routing 的概念非常簡單：由於現在的 routing 在處理的 net 都是點對點繞線，也就是從一個點開始當起點，想辦法連到另一個點 [2]，因此最簡單的 routing topology 可以歸納成三種：直線、L-shape、Z-shape，其中有些人會用轉彎的數量做區分：直線 (0-bend)、L-shape (1-bend)、Z-shape (2-bend)。想當然，轉彎數量越多 routing 的彈性也就越大，但是實作起來也會越複雜，因此常用的只停在 Z-shape，雖然曾經也有人提出過 3-bend routing [3]，但我是很少看到有人真的拿出來用。而 pattern routing 的概念簡單來說就是只用這些簡單好用又好實作的 "pattern" 做 routing，這樣就能同時完成分析哪邊 routing 最壅擠、以及整體的 routing plan。

pattern routing 由於所用的 pattern 單純，所以在 routing 初期甚麼東西都沒有的時候很適合用來產生一個初始的結果供後期分析，又因為 pattern 單純好實作，所以這速度可以非常快。因此後面有些 routing 的方法其實就是根據這樣的概念去做延伸修改的，只要根據需求去變更 pattern 的樣式，這概念其實可以有很大的延伸應用，像是 [4]。

不過由於現在先進製程的 design rule 複雜許多，pattern route 這概念被提出來時雖然他們的實驗說準確率很高，但放到現在的製程上來說其實已經沒那麼有效，因此就算這概念通用，實際上的方法都會做過相當大的調整變更以符合需求。

-----

[1] Ryan Kastner, Elaheh Bozorgzadeh and Majid Sarrafzadeh, "Predictable routing," in proc. ICCAD, pp. 110-114, 2000.

[2] 其實絕大多數的 net 都不只擁二個pin (叫做 multi-pin net)，在這種情況下現行的方法中最常用的叫做 two-pin net decomposition，也就是把這條 net 拆成許多個只有二個 pin 的 net，當這先 net 都各自完成 routing 後這條multi-pin net 也就把所有 pin 都接起來了。常用方法也是分成兩大類：minimum spanning tree (MST) & minimum steiner tree (SMT)，其差異與特色這邊就不多提。

[3] Yue Xu, Yanheng Zhang and Chris Chu, "FastRoute 4.0: Global router with efficient via minimization," in proc. ASP-DAC, 2009.

[4]  Yanheng Zhang and Chris Chu, "RegularRoute: An Efficient Detailed Router Applying Regular Routing Patterns," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, issue 9, pp. 1655-1668, 2012.