# Routability Prediction and Optimization Using Explainable AI.

## Abstract

（ML）技術在預測早期階段的路由能力方面得到了廣泛研究。為了在放置和路由迭代期間減少設計迭代時間，精確預測設計規則違規（DRV）熱點是至關重要的，而且要在實際詳細路由之前進行。然而，ML的複雜網絡結構使人難以理解ML如何生成預測以及識別對預測有重大影響的因素。ML的這種黑盒性質限制了將預測技術有效集成到優化流程中。可解釋的人工智能使我們能夠解釋ML模型的決策基礎，並為模型預測提供原因。在本文中，我們提出了一個路由優化框架，該框架使用可解釋模型分析與預測的DRV熱點相關的輸入特徵，並選擇最適合的優化方法。所提出的框架包括三個步驟—（1）在早期全局路由階段預測DRV熱點，（2）計算每個輸入特徵對預測的貢獻程度，以及（3）應用適當的優化方法以提高路由能力。在16個設計佈局中，我們平均減少了78%的DRV數量，同時沒有降低設計質量。關鍵詞—路由能力預測與優化，設計規則違規，可解釋人工智能（XAI），人工電路列表

## Introduction

這篇論文主要是針對現今複雜的設計規則和高密度的電路設計，提出了一個基於可解釋人工智慧的路徑可行性預測和優化框架。這個框架不僅可以預測設計規則違反的熱點，還可以分析輸入特徵並選擇最適合的優化方法。透過可解釋人工智慧，我們可以解釋機器學習模型的決策原理，並理解模型預測的原因。

這篇論文的主要貢獻有以下三點：

1. 提出了一個基於可解釋人工智慧的路徑可行性預測和優化框架，可以有效地減少設計規則違反，並提高設計的可行性。

2. 提出了一個貢獻分數圖，可以幫助我們有效地識別影響設計規則違反熱點的位置和特徵類型。

3. 引入了一種數據準備方法，可以在各種基準測試中訓練模型，並將這種方法應用到商業EDA工具中，使其更加實用。

---

## Preliminary

### A. Design Rule Violations

我們通常要在detail routing後才可以得知有沒有design rule violation。最基本的DRV包含幾個
1. Metal short:當一個物理重疊存在於一個via金屬或線金屬元件和其他物體之間，例如阻塞、引腳形狀或其他via和線金屬時，就會發生金屬短路違反。重疊區域被稱為短路區域。這個設計規則是為了確保電路設計的可靠性和功能性而制定的。

3. Parallel-run spacing:它規定了兩個平行金屬物體之間所需的間距。該設計規則要求根據它們的投影長度和寬度進行間距設置。換句話說，它調節兩個平行金屬線之間的距離，以確保它們不會互相干擾並引起短路或其他問題。這個設計規則對於確保電路設計的可靠性和功能性非常重要。

5. Cut spacing:它規定了同一個切割層上的via之間應該安排適當的距離，以確保它們的切割形狀之間有足夠的距離。這個設計規則是為了確保電路設計的可靠性和功能性而制定的。如果via之間的距離太近，可能會導致切割形狀之間的重疊，進而導致設計規則違反。

### B. Residual Block Based Network

這一節介紹了將佈局切分成小塊以預測可路由性並識別設計規則違反區域的方法。所提出的框架使用了一種稱為 "Residual Block Based Network" 的強大深度神經網絡架構(ResNet)，用於執行計算機視覺任務。創建這種神經網絡架構的主要原因是解決深度神經網絡中梯度消失的問題。

Residual Block 是 Residual Network 的基本單元，由多個卷積層和shortcut connections組成。卷積層從輸入圖像中提取特徵，快捷連接結合塊的輸入和輸出。這有助於網絡更平穩地傳播梯度信號，從而實現更有效的學習過程。因此，這種機制允許網絡學習更複雜的特徵，具有更深的結構。所提出的框架應用了 "Residual Block Based Network" 來預測設計規則違反熱點並選擇最適合的優化方法。

[Resnet 介紹](https://medium.com/@rossleecooloh/%E7%9B%B4%E8%A7%80%E7%90%86%E8%A7%A3resnet-%E7%B0%A1%E4%BB%8B-%E8%A7%80%E5%BF%B5%E5%8F%8A%E5%AF%A6%E4%BD%9C-python-keras-8d1e2e057de2)

### C. DeepSHAP

在本文中，"DeepSHAP" 一節介紹了一種解釋性人工智能技術，用於計算模型中每個輸入特徵對預測結果的貢獻。DeepSHAP 結合了 DeepLIFT 和 SHAP 值的方法，以捕捉特徵之間的交互作用和準確的預測解釋。DeepLIFT 通過鏈式法則向後傳播梯度，計算每個輸入特徵對模型輸出的貢獻。然而，DeepLIFT 只考慮單個特徵的解釋，無法考慮多個特徵之間的複雜交互作用。為了解決這個問題，DeepSHAP 引入了 SHAP 值，使用多個參考輸入來估計所有可能特徵組合的平均貢獻。DeepSHAP 結合了 DeepLIFT 的鏈式法則和 SHAP 值，以捕捉特徵之間的交互作用和準確的預測解釋。在所提出的路由性優化框架中，DeepSHAP 算法用於計算單個特徵對 DRV 熱點預測的貢獻，生成貢獻分數圖，表示對 DRV 熱點預測有主導影響的特徵的空間信息。

---

## Proposed Method

### A. Overall Flow of Routability Optimization Framework

一節介紹了所提出的路由性優化框架的整體流程。該框架由三個階段組成。

1. extract layout features after early-global routing (可以拿來做DRV hotspot prediction)

首先，在早期全局路由之後提取佈局特徵

2. use the DeepSHAP algorithm to compute the contribution of individual features in predicting the DRV hotspots.

然後利用這些特徵進行 DRV 熱點預測。接著，使用 DeepSHAP 算法計算單個特徵對 DRV 熱點預測的貢獻。框架生成貢獻分數圖，基於計算的特徵貢獻。

3. The framework generates a contribution score map based on the computed feature contributions

4. Finally, by considering the dominant feature contributions and their spatial distributions, the proposed framework can determine the most suitable optimization method to resolve the predicted DRV hotspots

最後，通過考慮主導特徵貢獻及其空間分布，所提出的框架可以確定最適合解決預測的 DRV 熱點的優化方法。所提出的框架可以有效地識別 DRVs 的原因並選擇適當的優化方法，平均減少 DRVs 的數量達到 78%，同時不會降低路由質量和時序閉合。


所以她整個flow: 先有一個train好的ML-based DRV prediction，在輸入layout feature後他會去predict一個DRV Heatmap Hmap，接著再去計算DeepSHAP，最後會得到一個Contribution Score Map Cmap，這些就是告訴我們的EDA Tool哪裡可能會比較容易有DRV，告訴placer那個地方可能就要擺散一點之類的。

### B. Data Preparation

介紹了數據準備的過程。為了有效地推廣優化方法，需要訓練無偏差的模型，並獲取包含各種 DRVs 原因的多樣化數據集。通過修改佈局設置或設計參數的數據增強可以幫助訓練模型識別電路設計質量的模式。但是，這些數據集不能保證對未見過的電路進行準確預測。在 P&R 流程中，數據庫的覆蓋範圍取決於用於訓練的基準的多樣性。

[ANG github](https://github.com/daeyeon22/artificial_netlist_generator)

ANG can be used to perform (a) data augmentation by modifying topolgical parameters extracted from real-world circuits, or (b) data exploration by random sampling in unseen circuit space to be expected. We believe that those approaches will increase the feature coverage of the post-layout database compared to only using real-world circuit benchmarks.

準備Data的流程:

為了應對這個挑戰，我們使用人工電路網表生成器（ANG）[18]，[35] 來產生閘級網表。ANG通過利用封裝電路的時序和互連複雜性特性的輸入拓撲參數來促進網表生成（見表I）。此外，也要考慮可能影響路由可行性的P&R設計參數。對於P&R設計參數，我們考慮了版面利用率、長寬比和頂層金屬層 - 這些都是影響路由可行性的重要元素[25]。

### C. Routability Prediction Model Implementation

1. 特徵提取與資料處理：為了提升預測模型的性能，我們在放置和早期全局路由階段設計了各種特徵。一般而言，有關佈局的物理信息，如單元和連線，與DRV的發生強烈相關。為了對DRV熱點進行像素級別的分類預測，我們採用了一種切片方法，將整個佈局分割成一個網格。網格的每個單位被定義為一個Gcell，它作為分析的基本構建塊。因此，我們在Gcell級別為預測模型導出用作輸入的特徵。我們將這些特徵的集合表示為特徵圖，它被定義為屬於RCin的{p(1,1)，···，p(X,Y)}。參數Cin是特徵數量，(X, Y)表示Gcell網格的寬度和高度。隨後，我們將特徵圖剪切到目標Gcell周圍的特定窗口大小w。這個剪切的地圖，表示為c(x,y)，被表示為{p(x−w,y−w)，···，p(x+w,y+w)}。c(x,y)的尺寸為(Cin，2w + 1，2w + 1)，並將其用作我們模型的輸入[26]。這種方法使我們能夠對佈局進行詳細分析，捕捉重要的局部變化和模式。以下是用於預測Routability的代表性特徵：
+ Cell density
+ Pin Density
+ Flip-flop cell ratio
+ Wire density
+ Via density
+ Number of instances / nets / terminals
+ Channel density
+ Horizontal / Vertical channel density
+ Local / Global / Special net RUDY
+ we used the rectangular uniform wire density (RUDY) [10], one of the most common approaches for estimating routing demand.

2. Model Architecture

DRV（Design Rule Violation）熱點預測可以視為像素級別的二元分類問題。為了通過可解釋的預測來對優化方法進行分類，確保無偏的模型訓練過程至關重要。如果模型存在偏見，它可能在預測中反映這些偏見，這可能妨礙根據不同特徵的貢獻進行優化的能力。通過利用殘差塊構建更深的神經網絡，我們可以提高模型對於複雜特徵的預測性能以及在各種基準測試上的泛化能力[28]。因此，我們將基於殘差塊的網絡應用於所提出的框架。

基本架構採用了三個殘差塊組和三個全連接（FC）層。Ci 和 Fi 分別表示第 i 個殘差塊的輸出通道大小和第 i 個 FC 層中的神經元數量。維度（H，W）對應於特徵圖的寬度和高度，等同於2w + 1，其中 w 代表滑動窗口的大小 [26]。

3. Model Hyper-parameter Searching:

超參數可以顯著影響預測模型的性能，因為它們控制模型訓練的行為[29]。然而，手動優化超參數可能是一項繁瑣且耗時的任務。因此，我們使用貝葉斯優化[30] 來迅速識別實現所需性能的最佳建模參數。在不平衡的二元分類情境中，其中少數類別的實例數顯著低於多數類別，考慮能夠有效評估少數類別預測性能的評估指標是至關重要的。由於DRV熱點和非熱點類別數量的不平衡，我們選擇F1分數作為驗證數據集的目標函數。

由於Gcell的大小影響模型的性能[31]，我們在這個過程中包括了Gcell和剪切窗口大小。Gcell和剪切窗口大小都被確定為單行高度的倍數。針對優化的超參數包括Gcell大小、窗口大小、輸出通道大小（Ci）、神經元數量（Fi）和學習率。有關Ci和Fi的信息可參見圖5。在訓練期間，使用二元交叉熵損失函數，對每個折疊設定20個epochs的5折交叉驗證方法。

### D. Contribution Score Map

為了使用DeepSHAP估計SHAP值，我們計算了在一組背景樣本上的預期模型輸出與當前模型輸出之間的差異，然後將這些差異相加。然而，SHAP值可能會根據背景樣本而變化。因此，我們使用來自訓練集的背景樣本的SHAP值的平均值來減少變異性。我們定義了一個貢獻分數圖（CSM），它在幾何上表示特徵的貢獻。 CSM是一個與Gcell網格大小相等的矩陣，其中將應用優化方法。首先，我們預測DRV熱點（圖7a）。然後，我們估算在預測的DRV熱點及其周圍的SHAP值，以考慮鄰近區域的影響（圖7b）。為了評估Gcell對DRV熱點的影響，我們在相應於每個Gcell坐標的CSM上累積SHAP值（圖7c）。然後，CSM包含有關特徵及其相應貢獻分數的信息。


算法1概述了CSM構建流程的伪代碼。該算法的輸入包括大小為(N,H,W)的特徵圖Fmap，大小為(H,W)的DRV熱點圖Hmap，DeepSHAP對象f，並產生大小為(N,H,W)的貢獻分數圖Cmap作為輸出。這裡，N、H和W分別表示特徵的數量，以及由Gcell平鋪的輸入特徵圖的高度和寬度。算法遍歷DRV熱點圖中的每個Gcell，檢查它是否是一個熱點（第4行）。如果是一個熱點，它確定一個目標區域，該區域包括熱點Gcell及其周圍Gcell的行和列索引（第5-10行）。接下來，它提取目標區域的特徵圖值，並將它們作為DeepSHAP對象的輸入來計算SHAP值（第11行）。SHAP值然後被添加到對應於目標區域的CSM中（第12行）。最後，一旦所有熱點都被處理，CSM作為輸出返回（第16行）。CSM表示模型輸出預測中每個特徵的重要性，得分越高表示重要性越大。


### E. Optimization Method Selection

我們根據最具影響力的特徵（圖8）選擇優化方法。我們根據每個Gcell的貢獻分數優先考慮特徵，並基於其最大貢獻分數選擇進行優化的Gcell。此後，我們將優化方法分為兩組 - （i）與placement related 和（ii）與routing related。

這兩者根據Gcell的主導特徵進行分類。圖9提供了每種情況的主導特徵和優化方法類別的概述。首先，與放置相關的方法被歸類為增強由於高單元密度和本地網絡擁擠而產生的DRVs。與路由相關的方法被歸類為解決由於全球網絡錯誤規劃或有限的路由資源而導致的DRVs。此外，圖9中未提及的其他輸入特徵也具有類似的特性。

我們使用三種優化方法：

1. cell spreading
2. wire density control
3. reserve routing track using tool commands

請注意，諸如單元擴散、線路密度控制和保留路由軌跡等優化是在post-placement, global routing and early global routing stage.



單元擴散是基於早期全局路由擁擠結果逐步移動單元，旨在通過擴散單元來改善擁擠熱點。因此，它可以在Gcell周圍創建和重新分配空白區域，以減少單元擁擠並增強引腳的可訪問性。密集區域中的單元可能增加本地網絡擁擠並限制引腳的可訪問性。

因此，為了應對高度的單元擁擠，我們在處理高單元密度、包含大量單元的Gcells，或者單元中缺乏引腳訪問點的情況下使用單元擴散。這些情況發生在單元密度、實例數量或引腳密度等特徵對預測的DRV熱點具有主導影響的情況下。