[EDA] Negotiation-Based Maze Routing 的部分困擾

Negotiation-based maze routing 可以說是現在 router 的基礎架構了，這個主要因素來自於當有許多 Net 要共同競爭相同的路徑以便縮短線長時，這個機制會讓競爭激烈的地區有相對大的成本，讓有其他選擇的 Net 可以轉而選擇相對較差但仍能完成繞線的路徑。當然，這種機制聽起來很單純美好，實作起來時總是會有其他許許多多衍伸的問題

先簡單的介紹 Negotiation-based maze routing 的機制，先看下面這張圖，相同顏色點就是要被連接起來的 Net。(這邊先不考慮有好幾層可以走，假設就這麼一層簡化問題)

從上圖我們可以看到，當這兩條 Net 都要走最短路徑時中途必定會有一個點要彼此競爭誰能走 (上圖左所指的 congestion point)。當然，因為只有一個人能走，所以必定有一條要被拔掉，此時這個 grid graph 就會在每個點上加上一個 history cost，用來記錄說當有人走過這個點的時候是不是有可能再被拔掉。因此所謂的 history cost 用簡單的概念來說，這 cost 越高代表走過這個點的代價會越高，因為之後又被人踩過去然後被拔掉的可能性也很高。當然，當你無路可走時你當然就一定會走過這個點，只是如果有其他選擇的話我們就可以選擇避開這個點改走其他地方，因此最後就能走成像上圖中間那張的狀況，黑色那條線選擇往下繞一個彎去避開。這就是被取名成 negotiation 的原因，藉由 history cost 讓多條 net 彼此權衡溝通，讓重要的資源有相對高的代價並留給真正需要的 net。

當然，事情有那麼單純就好辦了，history cost 設計的方法沒有固定的準則，原則上是要看自己的應用要自行調整或重新設計，其中一個很常見的問題就是 history cost 可能設太重，所以到最後就算他是最短路徑所必須經過的點，但因為代價太高所以能繞開就會繞開，這樣就有可能變成上圖右的那種狀況，沒有 net 想去走那個點，最後的總線長也因此增加。

另一個狀況是當整張 grid graph 都很壅擠時 (像是 cell layout 或是障礙物超多到處都會被擋)，history cost 的增長幅度就會相當驚人，因為怎麼走都會擠在一起，history cost 與其他 maze router 也有考慮的機制要如何權衡就是設計這些 cost 的時麻煩所在 (通常也是很需要經驗的地方)

以上，history cost 所衍伸的問題主要來自於過高的 history cost 會讓 router 乾脆避開這些點不走，結果最後沒有辦法產生預期的結果。解決方法簡單來說分兩類：

1. 良好的 cost 設計架構：各種 routing cost 權衡得好的話這問題自然能大幅降低，不過怎樣叫做好其實會發現是 case-by-case，也就是很難有一套機制可以縱橫天下處處適用，而且要調整這種東西超級花時間...
2. routing planning：這也是現在 router 不會單純只用 maze route 的原因，比較複雜的 case 如果有 routing plan 的話，maze route 可以依循著 routing plan 的結果再去微調即可，自然可以大幅降低 history cost 造成的負面影響

routing planning 的另一個優點在於它可以大幅降低 maze route 所需要的時間因為 maze route 可以依循著 planning 的結果，所以後續微調、修正、收斂的所需要的時間可以因此而縮短，routing framework 的 flow 通常就是上一步是在為下一步做事前準備，下一步是調整上一步的結果這樣。