用於晶片擺置的靈活性多目標強化學習

link to paper

為了EDA Workshop看的。

本篇的亮點\貢獻：

提出彈性多目標的強化學習(flexible multiple-objective reinforcement learning, MORL)
提出選取STD CELL叢集尺寸的方法
改編policy gradient，使其能適用在MORL上

目前RL多半都只針對一個固定的目標進行訓練，但實際上工程師需要的是多樣的選擇，來應對設計時多變而不同的需求。而這篇論文便是希望做到這點，也就是產生出一群policy，形成一個Pareto frontier。

問題定義

混和尺寸擺置

我們可以將現代VLSI擺置問題定義為擺放一群node到尺寸不一的平面，並最小化cost──例如線長、繞線壅擠、時序違反、耗能等等。 node可能包含不同尺寸的macro(可移動或不可)與標準邏輯元件/叢集。我們的問題只討論可移動的macro與標準邏輯元件/叢集。流程是這樣的：

輸入檔案(LEF/DEF/RTL)
擺置
EDA Tool算出QoRs

google團隊將這個問題轉化為RL的最佳化問題，透過policy逐個擺放macro，並使用估計的PPA當作獎勵。

多目標強化學習

先定義MDP為($\mathcal{S},\mathcal{A},p,r$)的tuple，接下來把他擴展成多目標的multi-objective MDP(MOMDP)。定義multi-objective MDP(MOMDP) $\mathcal{M}$為具有state $\mathcal{S}$、action $\mathcal{A}$及固定轉場$p$的MDP，但他的獎勵是以$i$為索引的獎勵集合。第$i$個獎勵以$\textbf{r}=r^{(i)}$表示。
對於這樣的獎勵向量，我們可以用一個偏好參數： ${\omega}={(\omega_i)}^K_{i=1}$，
來使MOMDP$\mathcal{M}$ 塌縮為標準的MDP$\mathcal{M}^\omega$，也就是把獎勵復原為單一的值──定義凸組合：
$r_\omega=\text{R}(\textbf{r},\omega)=\sum_{i=1}^{K}r^{(i)}\omega_i$，$\omega\in(\Omega^K, \mu)$，也就是K維的單純型(simplex)與機率測度$\mu$。
MDP$\mathcal{M}^\omega$中的action與state則可以用$\omega$索引：$(s;\omega)$、$(a,\omega)$。

接下來討論MOMDP的解，解一個MOMDP相等於解每個獨立的MDP$\mathcal{M}^\omega$，亦即找出使初始狀態value，$J(\omega,\pi_\omega)=V_{\pi_\omega}(s_0;\omega)$，最大的一組策略$\pi_\omega$。
我們將這樣的策略組稱為：parametric policy family，定義為由$\theta$連續參數的一組策略集$\pi_{\omega,\theta}$。

在接下去之前，先介紹一個概念：Pareto optimality，這是一種每一項指標都最適化的情況，無法在不減少任何一個指標的前提下進一步優化。如果我們針對多目標的最佳化，每一個在平面上滿足Pareto optimalty的點會組成一條邊界，我們稱為Pareto frontier。

方法

目標與估計

這篇聚焦的目標除了線長、擁擠度和時序之外，還加入使用者自訂的錨定區域距離限制。也就是使其能處理fence region或datapath。
HPWL: $l_{WL}=-\sum\limits_n(\max\limits_{pin_i,pin_j,\in n}\lvert x_i-x_j\rvert + \max\limits_{pin_i,pin_j\in n}\lvert y_i-y_j\rvert)$
Congestion: $l_C=-\frac{ACE(k)}{4},k\in 0.5,1,2,5$，$ACE(k)$會取k%的壅擠值
User Anchor: $l_A=-\sum\limits_ia_i\sqrt{(X_i-x_i)^2+(Y_i-y_i)^2}$，$(X_i,Y_i)$是使用者自定義的目標位置，$(x_i,y_i)$則是macro的中心位置，$a_i$是權重。
定義EDA目標: $l_{EDA}=\alpha l_{WL}+\beta l_C+\delta l_A$。

但fence可以用density mask擋掉、datapath=connectivity高?應該還是可以最佳化?
再來每個設計anchor一定不一樣，這樣會不會失一般性?
不過這個做法比較要EDA domain knowledge才想得出來

用policy gradient解MOMDP

TL;DR

我們的目標函數$\hat{J}(\theta) = \mathbb{E}_{\omega}[J(\theta;\omega)]$最佳化之後，便可以產生一個最佳的輪廓，但不能保證$\epsilon$最適性。
$\epsilon$最適性必須透過$\pi_{\theta, \omega}$的結構以及參數來確定。

實作與網路架構

基於google那篇，做兩點改動：

將$\omega$加入state表示，維度維持32。
value函數複製K次，並允許獨立最佳化。

實驗

MOPPO訓練

資料

用ICCAD2015 Superblue訓練，macro數量84-294不等、std cell則有770k-1930k，並聚焦於superblue10跟superblue18這兩組只有長方形的資料。(但其他的資料結果品質也相近。)

Flexible Multiple-Objective Reinforcement Learning for Chip Placement 閱讀筆記