[EDA] Routing Estimation / Planning - 前言

不知道大家有沒有玩過 (或看過) 一個遊戲叫做 "Flow Free"？遊戲畫面長得像下面這樣

這遊戲簡單來說就是給你一堆點且有各自的顏色，目標就是把相同顏色的二個點連接起來，次要目標則是盡可能的填滿所有格子 (所以會看到有些線, ex: 白色的線, 很明顯地有更短的連法)，限制則是線段之間不能重疊 / 接觸到。

這遊戲初期非常簡單，點非常少、盤面也很小，所以很容易就可以試出最終結果。但是到了中後期盤面加大、點的數量增加後，我想不難發現要再向初期那樣用 "試" 的試出一個結果的難度提高非常多，因為可能的結果太多了，因此同樣的方法在這時候會變得非常沒有效率，所以我們可以發現這遊戲到後期很需要一個概念：規劃。先粗略規劃一下每條線各自會占用的哪個區域，之後只要在規畫好的區塊內做嘗試就可以減少要嘗試的可能性。

舉例來說：

1. 有些點 (ex: 粉紅色) 直接一條線相連是最好的，因此這可以在最一開始就處理好
2. 有先點 (ex: 黃色)是在整個盤面的斜對角，因此不管怎麼走都會擋到一堆人，晚點處理就好
3. 有些點 (ex: 紅色、紫色) 有很明顯的地區性，先切割好區域後有助於分析會擋到那些點的線段

諸如此類的，像這樣的前期分析做過一次後我們會發現實際上要考慮的點剩下很少，而且因為這時候盤面規劃好後，就算前期規畫無法決定的點在這時候問題也被簡化了，很快就能試出最後結果了，這就是規劃的重要性與特色。

話又說回來，這遊戲其實就是 routing (中譯：繞線) 這問題的簡易版，晶片中的 routing 一樣會有許多的點要連，而且不一定會只有二個點互連，可能會有三個甚至幾十個、上百個點要連，所以主要目標就是把所有該互連的點連起來，次要目標跟 flow free 相反，是總線段長度最短，限制當然也是線段間不能重疊囉 (註 1)。因此上面這個例子是個說明在 routing 最前期規劃 (planning, estimation) 的重要性，沒有經過 planning 就相當於瞎子摸象永遠都只看得到局部的區域，無法有完整的視野加以調整修正最終結果

由於真正的 routing 其實必須考慮製造上的可行性與良率問題，實際上的規範多如牛毛 (X他X的煩...)，因此其實非常容易出現 trial and error 這種方法根本解決不了的狀況，因此一般 router 在設計時不可能一步到位，通常都會分成好幾個階段處理不同的問題：先從整個完整的局面開始粗略的規畫分析，然後把要處理的問題一個一個放進來調整前一步的結果，如此反覆直到得到最後結果。

在整個 routing flow 中最困難的其實就是第一步：因為這時候甚麼東西沒有，規劃的太粗糙導致跟最後結果差太多，那其實就像沒有規劃；規劃的太仔細其實就跟直接做 routing 差不多，失去規畫這一步的意義，也很浪費時間。這直接如何拿捏確實是 planning & estimation 這一步的最大考驗。

----------------------------------------------------------

註 1：其實這段敘述也是相當大程度的簡化 routing 這問題，因為首先依照 flow free 的模式去想的話會發現其中包含二點最基本的假設：

1. 線段沒有寬度：但是實際上 routing 的線段有最小寬度的限制
2. 有既定格線規範只能走在格子中：實際上並沒有這種東西

實際上的 router 有二種模式

1. grid-based：其實就是沒有格線我就自己畫格線的概念，優點當來是這能很大幅度的降低複雜性，劃格線時也只要先把最小線寬等納入考慮後再畫，這樣 routing 時就不用考慮線寬的問題；缺點相對不容易發現：就是可能會因此產生一些不易利用的零碎空間。絕大部分探討 routing 的論文都是 grid-based 的。
2. gridless：這東西的概念就是沒有格線就沒有隔線，完全 free style，優點就是沒有 grid-based 的缺點，所以設計正確的話是可以比 grid-based 的結果好的；缺點也很簡單：這東西超。級。難。寫。敝實驗室以前有出過一篇好像滿有名的 gridless router 的論文：NEMO，不過現在很容易遇上沒人可以維護的問題 XD