標題:Chip Placement with Deep Reinforcement Learning

用深度強化學習進行芯片布局食绿。對深度強化學習的理解是：強化學習有agent、environment、reward蠢甲、action等組成部分，就是一個智能體（agent）在一個未知的環(huán)境（environment）中肝集，不斷摸索抓谴，將動作（action）作用于環(huán)境，環(huán)境反饋獎勵（reward）給智能體怨愤，然后智能體根據(jù)獎勵來更新這個產(chǎn)生動作的決策函數(shù)派敷。當環(huán)境越來越復雜，這個決策函數(shù)進行決策和實現(xiàn)起來就越來越困難撰洗，而深度神經(jīng)網(wǎng)絡正好具有強大的擬合能力篮愉，所以可以將這個決策函數(shù)用深度神經(jīng)網(wǎng)絡來代替，這樣就形成了深度強化學習差导。

摘要

概述：基于學習的方法來進行芯片布局
特點：可以從過去的經(jīng)驗中學習试躏，并隨著時間不斷改善。接受訓練的芯片塊數(shù)量越多设褐，對之前沒見過的芯片塊進行布局優(yōu)化時速度越快颠蕴。
方法概述：將芯片布局問題轉(zhuǎn)化為強化學習問題，通過訓練agent往芯片畫布上放置芯片網(wǎng)表的節(jié)點络断。
關鍵步驟：
1.為了可以推廣到對之前沒見過的芯片塊的優(yōu)化裁替，選取有代表性的學習加入到預測布局效果的監(jiān)督任務中
2.通過設計一個神經(jīng)網(wǎng)絡，可以準確預測各種芯片網(wǎng)表和其布局的獎勵貌笨，從而可以生成輸入網(wǎng)表的豐富特征嵌入弱判。
3.借助這個架構將策略網(wǎng)絡和值網(wǎng)絡用到遷移學習中。
結(jié)果：最小化PPA（功耗性能面積）锥惋，6個小時完成的設計將優(yōu)于或媲美于專家花幾周完成的設計昌腰。

1.引言

計算機系統(tǒng)和硬件性能的提升促進了AI技術的飛速發(fā)展，但是在后摩爾定律和Dennard縮放比例定律的作用下膀跌，為了滿足AI算力的指數(shù)級增長遭商，硬件逐漸趨于專用化。一般芯片設計周期需要幾年捅伤，減少芯片設計的時間才能使得硬件更好地適應AI的飛速發(fā)展劫流。我們認為AI可以用于縮短芯片設計周期，從而讓硬件和AI建立共生關系，彼此互相推動祠汇。

我們提出了基于學習的芯片布局方法仍秤。目標是將宏（例如SRAMs）和標準單元（即邏輯門）的網(wǎng)表圖放置到芯片畫布上，在考慮布局密度和布線擁塞的約束下優(yōu)化芯片的功耗性能和面積可很。盡管在這個問題上已經(jīng)有很多年的研究诗力，但是始終離不開專家用現(xiàn)有的布局工具對此進行幾周的迭代設計工作，以得到滿足多重約束的芯片設計方案我抠。問題的復雜性來自網(wǎng)表圖的大小(數(shù)百萬到數(shù)十億個節(jié)點)苇本、用于放置這些圖的網(wǎng)格粒度、以及用EDA工具評估和計算相關指標的成本菜拓。盡管將問題分解為更易于管理的子問題（例如將節(jié)點分組為幾千個集群并減小網(wǎng)格的粒度）赊锚，狀態(tài)空間仍比目前已成功應用的基于學習的方法要大幾個數(shù)量級掰派。

為了解決這個難題餐茵，我們將芯片布局轉(zhuǎn)化為強化學習問題笙瑟，通過訓練一個agent（例如RL 策略網(wǎng)絡）來優(yōu)化布局。在每次訓練迭代中喷橙，芯片塊的所有宏均由agent順序放置啥么，然后通過力導向方法放置標準單元。訓練以agent 每一次芯片布局得到的reward作為指導贰逾。

據(jù)我們所知悬荣，上述的方法是目前第一種具有泛化能力的布局方法，這意味著它可以利用之前放置網(wǎng)表所學到的知識來為新的網(wǎng)表生成布局方案疙剑。隨著芯片數(shù)量和種類的增多氯迂，agent可以更高效地為新的芯片塊生成優(yōu)化布局方案，這使未來的芯片設計工程師可以借助具有豐富布局經(jīng)驗的agent進行芯片布局工作言缤。

我們的方法具有從經(jīng)驗中學習并隨著時間的推移而改進的能力嚼蚀，這為芯片設計人員開辟了新的可能性。與最新的基準相比管挟，我們的方法可以在真正的AI加速器芯片（Google TPU）上實現(xiàn)出色的PPA轿曙。此外，我們的方法可在6小時內(nèi)產(chǎn)生優(yōu)于或媲美于專家人工設計的布局僻孝，而以往性能最高的方案則需要人類專家耗費幾周時間才能獲得导帝。盡管我們主要借助AI加速器芯片進行方法評估，但這個方法可以推廣應用于任何芯片的布局優(yōu)化穿铆。

2.相關工作

全局布局是芯片設計中的長期挑戰(zhàn)您单，需要對日益復雜的電路進行多目標優(yōu)化。自1960年以來荞雏，提出了很多方法虐秦，可以分為三大類：1）基于分區(qū)的方法平酿，2）隨機/爬山方法，以及3）解析求解器的方法悦陋。

自1960年以來染服，工業(yè)界和學術界采用了基于分區(qū)的方法來進行芯片的全局布局，此外還采用了基于電阻網(wǎng)絡的方法叨恨。這些方法的特點是分而治之；即遞歸劃分網(wǎng)表和芯片畫布挖垛，直到子問題足夠小為止痒钝，此時使用最佳求解器將子網(wǎng)表放置到子區(qū)域中。這類方法執(zhí)行起來非沉《荆快送矩，并且它們的層次結(jié)構也允許它們被劃分為任意大的網(wǎng)表。但是哪替，通過孤立地優(yōu)化每個子問題栋荸，這類方法犧牲了全局優(yōu)化的質(zhì)量，尤其是布線擁塞凭舶。此外晌块，一個較差的早期分區(qū)可能導致最終無法調(diào)整的芯片布局。
在1980年代帅霜，出現(xiàn)了分析方法匆背，但很快被隨機/爬山算法取代，特別是模擬退火算法身冀《凼可以用冶金的過程來解釋模擬退火，即在冶金時先加熱金屬搂根，然后逐漸冷卻珍促，誘導其退火到能量最佳的晶體表面。模擬退火將隨機的擾動應用于一個給定的芯片布局（例如宏的移位剩愧，交換或旋轉(zhuǎn)）猪叙，然后測量其對目標函數(shù)的影響（例如半周線長）。如果擾動是一種改善隙咸，則將其應用沐悦；如果不是，它仍然以一定的概率被繼續(xù)應用五督，稱之為溫度藏否。溫度初始化為一個特定值，然后逐漸退火至較低值充包。盡管模擬退火算法可以產(chǎn)生高質(zhì)量的布局方案副签，但是運行速度非常緩慢且難以并行化遥椿，因此無法推廣應用到1990年代及以后日益大型和復雜的電路。
1990年至2000年代芯片布局有三個典型方法淆储，分別是多層劃分的方法冠场、解析技術例如力導向方法、以及非線性優(yōu)化器的方法本砰。二次方法的再次成功碴裙，部分原因是算法的進步，但也歸功于現(xiàn)代電路的大尺寸（1000萬-1億個節(jié)點）点额，這證明了將放置問題近似為放置零面積節(jié)點的合理性舔株。但是，盡管二次方法具有較高的計算效率还棱，但是與非線性方法相比载慈，它們往往較不可靠，并且產(chǎn)生的布局質(zhì)量較低珍手。
非線性優(yōu)化使用平滑的數(shù)學函數(shù)來估算成本办铡，例如線長的對數(shù)和表達式、加權平均模型琳要，以及布局密度的高斯模型和Helmholtz密度模型寡具。將這些函數(shù)通過拉格朗日懲罰或松弛組合為單目標函數(shù)。由于這些模型的復雜性較高稚补，因此有必要采用分層方法晒杈，放置的是集群而不是單個節(jié)點，然而這會降低布局的質(zhì)量孔厉。
過去十年見證了現(xiàn)代解析技術的興起拯钻，包括更高級的二次方法，以及最近的基于靜電的方法撰豺，如ePlace和RePlAce粪般。將網(wǎng)表布局建模為一個靜電系統(tǒng)，ePlace提出了密度損失的新公式污桦，其中網(wǎng)表的每個節(jié)點（宏或標準單元）類似于帶正電荷的粒子亩歹，節(jié)點面積對應于粒子的電荷量。在這種設定下凡橱，節(jié)點之間相互排斥的力與其電荷量（節(jié)點面積）成正比小作，密度函數(shù)和梯度對應于系統(tǒng)的勢能〖诠常可以對這種基于靜電的方法進行改進顾稀，以解決標準單元放置和混合尺寸放置的問題。RePlAce是一種最新的混合尺寸放置技術坝撑，它通過引入局部密度函數(shù)進一步優(yōu)化了ePlace的密度函數(shù)静秆，該函數(shù)根據(jù)每個容器的大小調(diào)整懲罰因子粮揉。第5節(jié)對最新的RePlAce算法的性能與我們的方法進行了比較。
最近的工作提出一種方法抚笔，即通過訓練模型來預測給定宏的布局違反DRC的次數(shù)扶认。DRC是確保所放置和連線的網(wǎng)表符合輸出要求的規(guī)則。未來生成具有較少DRC的宏布局殊橙，有相關工作使用了上述訓練模型的預測作為模擬退火中的評估函數(shù)辐宾。盡管這項工作代表了一個有趣的方向，但它報告的網(wǎng)表結(jié)果不超過6個宏膨蛮，遠遠少于任何現(xiàn)在的芯片塊螃概，而且該方法未對布局和布線進行任何優(yōu)化。因此在后續(xù)的優(yōu)化過程中鸽疾，布局和布線可能會發(fā)生巨大變化，實際DRC也會發(fā)生相應變化训貌，從而使模型預測無效制肮。另外，盡管芯片布局必須遵守DRC標準递沪，但是宏放置的首要目標還是對線長豺鼻、時序（例如最壞的負松弛（WNS）和總的負松弛（TNS））、功耗和面積進行優(yōu)化款慨。上述工作沒有考慮到這些首要的指標儒飒。
為了解決這個經(jīng)典問題，我們提出了一類新的方法：端到端基于學習的方法檩奠。這種方法與解析求解器（尤其是非線性求解器）最為相似桩了，因為它們都是通過梯度更新來優(yōu)化目標函數(shù)的。但是埠戳，我們的方法與以往的方法不同之處在于它可以從過去的經(jīng)驗中學習井誉，以在新的芯片上生成更高質(zhì)量的布局方案。與現(xiàn)有的從頭開始優(yōu)化每個芯片的布局的方法不同整胃，我們的方法利用了先前芯片布局獲得的知識颗圣，使得隨著時間推移芯片的布局變得更好。此外屁使，我們的方法可以直接對指標進行優(yōu)化在岂，例如線長、布局密度和布線擁塞蛮寂，而無需像其他方法一樣定義對應指標函數(shù)的凸近似蔽午。我們的公式不僅易于整合新的代價函數(shù)，而且能夠根據(jù)給定芯片塊的需求（例如酬蹋，關鍵時序或功耗約束）來權衡它們的相對重要性祠丝。
域適應是訓練策略的問題疾呻，該策略可以跨多種經(jīng)驗學習并遷移所獲得的知識，從而在新的未見過的情形下表現(xiàn)更好写半。對于芯片布局岸蜗，域適應包括在一組芯片網(wǎng)表中訓練策略，并將該策略應用于新的網(wǎng)表叠蝇。近來璃岳，用于組合優(yōu)化的域適應已經(jīng)成為趨勢。盡管先前工作的重點在于使用從優(yōu)化問題先例中學到的域知識來加快對新問題的策略訓練悔捶，但我們提出了一種方法铃慷，該方法首次可以通過利用過去的經(jīng)驗來生成更高質(zhì)量的結(jié)果。與從頭開始訓練策略相比蜕该，我們使用的域適應方法不僅可以得到更好的結(jié)果犁柜，而且還將訓練時間減少了8倍。

3.方法

3.1 問題重述

我們圍繞芯片布局優(yōu)化問題堂淡，將網(wǎng)表的節(jié)點（網(wǎng)表就是描述芯片的圖形）映射到芯片畫布（芯片畫布就是一個有界的2D空間）上馋缅，從而優(yōu)化功耗、性能和面積（PPA）绢淀。在本節(jié)中萤悴，我們概述如何將問題表述為強化學習問題，然后詳細描述獎勵函數(shù)皆的，動作和狀態(tài)的表示覆履，策略結(jié)構以及策略更新。

3.2 本文方法概述

我們采用深度強化學習（RL）的方法來解決布局問題费薄，其中agent(策略網(wǎng)絡)順序放置宏硝全；一旦放置了所有宏，就使用力導向法來對標準單元進行大致的布局楞抡，如圖1所示柳沙。RL問題可以表示為馬爾可夫決策過程(MDPs)，由四個關鍵元素組成：

state：所有可能狀態(tài)的集合（在我們的例子中拌倍，狀態(tài)就是網(wǎng)表在芯片畫布上每一個可能的放置情況）赂鲤。
action：agent所有可能采取的行動的集合（例如，給定當前要放置的宏柱恤，可能的動作就是在不違反密度或擁塞等約束下所有可能放置該宏的位置的集合数初。
state transfer：給定一個state和一個action，下一個state可能的概率分布梗顺。
reward：在一個state中采取某個action時得到的獎勵泡孩。（在我們的示例中，除最后一個action之外的所有action的reward都是0寺谤，其中reward是agent的線長和擁塞的負加權和仑鸥，它需要滿足第3.3節(jié)中描述的密度約束吮播。）

圖1 工作概述圖

在初始state，記為 s₀眼俊，我們有一個空的芯片畫布和一個未放置的網(wǎng)表意狠。最后的狀態(tài) s_T 對應于一個完全放置的網(wǎng)表（包括宏和標準單元）。在每一步中疮胖，放置一個宏环戈。因此，T 等于網(wǎng)表中宏的總數(shù)澎灸。在每個時間步 t 中院塞，agent從狀態(tài) s_t 開始，執(zhí)行一個動作 a_t 性昭，然后到達一個新的狀態(tài)即 s_{t +1}拦止，并從環(huán)境中獲得一個獎勵 r_t （當 t < T 時，reward為0糜颠；當 t = T 時汹族，reward 為負代理成本。）

我們把s_t 定義為時間 t 時可用于表征狀態(tài)的特征串聯(lián)括蝠，包括網(wǎng)表的圖形嵌入（包括放置和未放置的節(jié)點），當前要放置的宏的節(jié)點嵌入饭聚，關于網(wǎng)表的元數(shù)據(jù)（第4節(jié)）忌警，以及代表將當前節(jié)點放置到任一個網(wǎng)格單元的可行性的掩碼（第3.3.6節(jié)）。

動作空間是第 t^th 個宏的所有可能的放置位置秒梳，是第3.3.6節(jié)描述的密度掩模的函數(shù)法绵。動作 a_t 是由RL策略網(wǎng)絡選擇的第 t 個宏的單元格位置。

s_{t +1} 是下一個狀態(tài)酪碘，它包含新放置的宏的信息朋譬、一個更新的密度掩碼，以及對下一個要放置的節(jié)點的嵌入兴垦。

在我們的公式中徙赢，除了最后的 r_T 外，每個時間步的 r_t 都為0探越，其中 r_T 近似為線長和擁塞的加權和狡赐，如3.3節(jié)所述。

通過重復地執(zhí)行這些事件（state钦幔、action和reward的序列）枕屉，策略網(wǎng)絡學會采取將累積獎勵最大化的行動。當給出每次布局后的累積獎勵鲤氢，我們就可以使用近端策略優(yōu)化算法（Proximal Policy Optimization, PPO）來更新策略網(wǎng)絡的參數(shù)搀擂。

在這一節(jié)中西潘，我們定義獎勵為 r，狀態(tài)為 s 哨颂，動作為 a 喷市，以 $\theta$ 為參數(shù)的策略網(wǎng)絡為 $\pi_{\theta}(a | s)$ ，最后介紹了我們用這些參數(shù)來進行優(yōu)化的方法咆蒿。

3.3 獎勵

我們的目標是在布線擁塞和布局密度的約束下东抹，使功耗、性能和面積最小化沃测。我們真正的reward是EDA的輸出缭黔，包括線長、布線擁塞蒂破、布局密度馏谨、功耗、時序和面積附迷。然而惧互，RL策略需要100000個示例才能有效地學習，因此reward函數(shù)的快速評估非常重要喇伯，理想情況下在幾毫秒內(nèi)就能運行完成喊儡。為了有效，這些近似的reward函數(shù)也必須與真正的reward正相關稻据。因此艾猜，成本應該包含線長，因為它不僅評估成本較低捻悯，而且與功耗和性能（時序）相關匆赃。我們?yōu)榫€長和布線擁塞定義了近似的代價函數(shù)，如第3.3.1節(jié)和第3.3.5節(jié)所述今缚。

為了將多目標組合成一個單目標的reward函數(shù)算柳，我們對agent的線長和擁塞進行加權求和，其中權重可用于權衡兩個指標的影響姓言。

我們將布線擁塞視為一種軟約束（即較低的擁塞可以改善reward函數(shù)）瞬项。我們將布局密度作為硬約束，即采取密度不能超過最大密度的action（將節(jié)點放置到網(wǎng)格單元上）何荚，如第3.3.6節(jié)所述滥壕。

為了讓每次迭代的時間較小，我們對reward函數(shù)的計算做了以下近似：

我們使用 hMETIS 將數(shù)百萬個標準單元分組成數(shù)千個集群兽泣，這是一種基于歸一化最小割目標的分區(qū)技術绎橘。一旦所有宏被放置，我們使用力導向法來放置標準單元集群，如3.3.4節(jié)所述称鳞。這樣做可以使我們較快地得到一個大致的標準單元布局方案涮较，從而促進策略網(wǎng)絡的優(yōu)化。
我們將網(wǎng)格離散為幾千個網(wǎng)格單元冈止，并將宏和標準單元集群的中心放在網(wǎng)格單元的中心狂票。
在計算線長時，我們假設標準單元集群的所有連接都起源于集群的中心熙暴。
為了計算布線擁塞成本闺属，我們只考慮前10%最擁塞的網(wǎng)格單元的平均擁塞，如3.3.5節(jié)所述周霉。

3.3.1. 線長

我們采用半周線長（HPWL）掂器，這常用于對線長的近似。HPWL定義為網(wǎng)表中包含所有節(jié)點的邊框的半周長俱箱。給定邊為 i 的HPWL如下式所示：
$\begin{aligned} H P W L(i) &=\left(M A X_{b \in i}\left\{x_国瓮\right\}-M I N_{b \in i}\left\{x_\right\}+1\right)(1) \\ &+\left(M A X_{b \in i}\left\{y_狞谱\right\}-M I N_{b \in i}\left\{y_乃摹\right\}+1\right) \end{aligned}$
其中，x_b 和 y_b 表示網(wǎng)絡 i 的 x 和 y 坐標跟衅。然后對所有半周長的歸一化求和孵睬，計算出HPWL的總代價，如式（2）所示伶跷。q(i) 是歸一化因子掰读，可以通過增加節(jié)點數(shù)量帶來線長成本的增加來提高估計的準確性。N_netlist 是線網(wǎng)的數(shù)量撩穿。
$H P W L(\text {netlist})=\sum_{i=1}^{N_{n e t t i s t}} q(i) * H P W L(i）(2)$
直觀地說磷支，對于給定布局的HPWL大致是其Steiner樹的長度谒撼，這是布線成本的最低值食寡。

線長還具有關聯(lián)其他重要指標（例如功耗和時序）的優(yōu)勢。盡管我們沒有直接對這些其他指標進行優(yōu)化廓潜，但是我們在表2中可以觀察到這些指標例如功耗和時序的高性能（如表2所示）抵皱。

3.3.2. 網(wǎng)格行數(shù)和列數(shù)的選擇

給定芯片畫布的尺寸，有很多方法可以將2D畫布離散化為網(wǎng)格單元辩蛋。這將影響優(yōu)化的難度和最終放置的質(zhì)量呻畸。我們把最大行數(shù)和列數(shù)限制為128，將確定最佳行數(shù)和列數(shù)視為裝箱問題悼院，并根據(jù)行和列的浪費空間大小對不同的行數(shù)和列數(shù)進行排序伤为。在第5節(jié)描述的實驗中，我們平均使用30行和30列。

3.3.3. 宏放置順序的選擇

為了選擇宏的放置順序绞愚，我們對宏從大到小排序叙甸，并使用拓撲排序中斷連接。通過先放置較大的宏位衩，可以減少后續(xù)宏沒有放置空間的可能裆蒸。拓撲排序可以幫助策略網(wǎng)絡學習如何將互連的節(jié)點放得相互靠近。另一種可能的方法是學習聯(lián)合優(yōu)化宏的順序和它們的位置糖驴，選擇將action空間的下一步放置在哪個節(jié)點上僚祷。然而，這種擴大動作空間的方法會顯著增加問題的復雜性贮缕，我們發(fā)現(xiàn)這種啟發(fā)式方法在實踐中是有效的辙谜。

3.3.4. 標準單元的布局

為了放置標準單元集群，我們使用了一種類似于經(jīng)典力導向算法的方法跷睦。我們將網(wǎng)表表示為一個彈簧系統(tǒng)筷弦，該系統(tǒng)根據(jù) $weight$ x $distance$ 公式，對每個節(jié)點施加力抑诸，從而使緊密連接的節(jié)點相互吸引烂琴。我們還引入了重疊節(jié)點之間的斥力，以減少布局密度蜕乡。在施加所有的力后奸绷，我們將節(jié)點往力矢量的方向移動。為了減少振蕩层玲，我們?yōu)槊恳徊较拗屏俗畲缶嚯x号醉。

3.3.5. 布線擁塞

我們在計算agent 擁塞時使用了傳統(tǒng)的方法，即使用了基于驅(qū)動位置和網(wǎng)絡負載的簡單確定的布線辛块。布線網(wǎng)絡經(jīng)過每個網(wǎng)格單元時畔派，占用一定數(shù)量的布線資源。我們分別跟蹤每個網(wǎng)格單元的垂直和水平分配润绵。為了平滑布線擁塞的估計值线椰，我們在垂直和水平方向上運行 $5$ x $1$ 的卷積濾波器。當所有網(wǎng)表的布線完成后尘盼，我們?nèi)∏?0%擁塞值的平均值憨愉，這個靈感來自MAPLE中的ABA10度量。公式（4）表示的是布線擁塞成本卿捎，表示前10%擁塞值的平均值配紫，就是通過這個過程計算得到的。

3.3.6.布局密度

我們將密度視為硬約束午阵，不允許策略網(wǎng)絡將宏放置在會導致密度超過目標密度最大值或?qū)е潞曛丿B的位置躺孝。該方法有兩個優(yōu)點：（1）減少了策略網(wǎng)絡產(chǎn)生的無效放置的數(shù)量；（2）減少了優(yōu)化問題的搜索空間，使其更易于計算植袍。

標準單元集群的布局應滿足以下標準：每個網(wǎng)格單元放置的密度不應超過給定的目標密度閾值伪很。我們在實驗中將這個閾值設置為0.6。為了滿足這個約束奋单，在每個RL步驟中锉试，我們計算當前的密度掩碼，這是一個表示網(wǎng)格單元的二進制 m x n 矩陣览濒，我們可以在不違反密度閾值的情況下將當前節(jié)點的中心放置到該掩碼上呆盖。在從策略網(wǎng)絡的輸出中選擇action之前，我們首先取掩碼和策略網(wǎng)絡輸出的點積贷笛，然后取可行位置上的 argmax应又。這種方法可以防止策略網(wǎng)絡生成具有重疊宏或密集的標準單元布局。

我們還可以通過將布局擁塞區(qū)域的密度函數(shù)設置為1乏苦，從而來使放置時能考慮到擁塞（例如時鐘帶）株扛。

3.3.7. 后處理

為了用EDA工具對放置的效果進行評估，我們基于貪婪思想將宏放置到最近且合理的位置汇荐，同時滿足最小間距約束洞就。然后，我們確定宏的放置掀淘，使用EDA工具放置標準單元并評估放置情況旬蟋。

3.4. 動作的表示

為了優(yōu)化策略，我們將畫布轉(zhuǎn)換為一個 m x n 的網(wǎng)格革娄。因此倾贰，對于任何給定的state，action空間(或策略網(wǎng)絡的輸出)是當前宏在 m x n 網(wǎng)格上位置的概率分布拦惋。這個action就是這個概率分布的 argmax 匆浙。

3.5. 狀態(tài)的表示

我們的state包含了網(wǎng)表圖(鄰接矩陣)、它的節(jié)點特征(寬度厕妖、高度首尼、類型等)、邊特征(連接數(shù))叹放、當前要放置的節(jié)點(宏)饰恕、網(wǎng)表和底層技術的元數(shù)據(jù)(例如布線分配挠羔、總連接數(shù)井仰、宏、標準單元集群等)破加。在接下來的小節(jié)中，我們將討論如何處理這些特性來學習芯片布局的有效表示。

4.域遷移：從經(jīng)驗中學到更好的芯片布局

我們的目標是訓練RL agent冠跷，當他們獲得芯片布局的經(jīng)驗時，可以產(chǎn)生更高質(zhì)量的結(jié)果了罪。我們定義布局的目標函數(shù)如下：
$J(\theta, G)=\frac{1}{K} \sum_{g \sim G} E_{g, p \sim \pi_{\theta}}\left[R_{p, g}\right] (3)$
這里 $J(\theta, G)$ 是成本函數(shù)。agent 由 $\theta$ 參數(shù)化的聪全。大小為 $K$ 的網(wǎng)表圖數(shù)據(jù)集用 $G$ 表示泊藕，數(shù)據(jù)集中每個單獨的網(wǎng)表寫為 $g$ 。 $R_{p, g}$ 指在網(wǎng)表 $g$ 的策略網(wǎng)絡中放置 $p$ 時的獎勵难礼。
$\begin{array}{r} R_{p, g}=-\text {Wirelength}(p, g)-\lambda \text { Congestion}(p, g) \\ \text {S.t. density}(p, g) \leq \text {max}_{\text {density}} \end{array}(4)$
公式（4）表示我們用于策略網(wǎng)絡優(yōu)化的reward娃圆，即在密度約束下的線長和布線擁塞的負加權平均值。reward在3.3節(jié)中有詳細解釋蛾茉。在我們的實驗中讼呢，擁塞權重 $\lambda$ 設置為0.01，最大密度閾值設置為0.6谦炬。

4.1. 使能遷移學習的監(jiān)督方法

我們提出一種新的神經(jīng)架構悦屏，使我們能夠訓練領域自適應策略來進行芯片布局。訓練這樣一個策略網(wǎng)絡是一項具有挑戰(zhàn)性的任務键思，因為包含所有芯片的所有可能放置的狀態(tài)空間是巨大的础爬。此外，不同的網(wǎng)表和網(wǎng)格大小具有不同的屬性吼鳞，包括節(jié)點數(shù)量幕帆、宏大小、圖形拓撲以及畫布的寬度和高度赖条。為了解決這個挑戰(zhàn)失乾，我們首先關注于學習狀態(tài)空間的豐富表示。我們的直覺是纬乍，能夠跨芯片遷移布局優(yōu)化的策略網(wǎng)絡架構也應該能夠在推斷時將與新的芯片相關的狀態(tài)編碼為有意義的信號碱茁。因此，我們提出訓練一個能夠預測新網(wǎng)表reward的神經(jīng)網(wǎng)絡架構仿贬，最終目標是使用這個架構作為我們策略網(wǎng)絡的編碼層纽竣。

為了訓練這個監(jiān)督模型，我們需要一個大的芯片布局數(shù)據(jù)集和相應的獎勵標簽茧泪。因此蜓氨，我們創(chuàng)建了一個包含10000個芯片布局的數(shù)據(jù)集，其中輸入是與給定放置相關聯(lián)的狀態(tài)队伟，而標簽是對該放置的獎勵（線長和擁塞）穴吹。我們首先選擇5個不同的加速器網(wǎng)表，然后為每個網(wǎng)表生成2000個布局嗜侮，從而構建這個數(shù)據(jù)集港令。為了給每個網(wǎng)表創(chuàng)建不同的布局啥容，我們在不同的擁塞權重（從0到1）和隨機種子（seeds）下訓練了一個香草策略網(wǎng)絡（vanilla policy network），并在策略訓練過程中收集每種布局的情形顷霹。一個未經(jīng)訓練的策略網(wǎng)絡從隨機權重開始咪惠，生成的布局質(zhì)量較低差，但隨著策略網(wǎng)絡的訓練淋淀，生成的布局質(zhì)量不斷提高遥昧，這讓我們可以收集到具有不同布局質(zhì)量的數(shù)據(jù)集。

為了訓練一個能準確預測線長和擁塞標簽的監(jiān)督模型朵纷，并推廣應用到未知的數(shù)據(jù)渠鸽，我們開發(fā)了一種新的嵌入網(wǎng)表信息的圖神經(jīng)網(wǎng)絡結(jié)構。圖神經(jīng)網(wǎng)絡的作用是在一個大圖中提取關于節(jié)點類型和連接的信息柴罐，并將其轉(zhuǎn)換為低維向量的表示形式徽缚，從而可用于后續(xù)任務。后續(xù)任務例如節(jié)點分類革屠、器件放置凿试、連線預測和DRC預測。

我們通過串聯(lián)節(jié)點特征來對每個節(jié)點進行向量表示似芝。節(jié)點特征包括節(jié)點類型那婉、寬度、高度以及 x 和 y 坐標党瓮。我們還將節(jié)點鄰接信息作為輸入傳遞給算法详炬。然后，我們重復執(zhí)行以下更新：1) 每條邊通過將全連接網(wǎng)絡應用于中間節(jié)點嵌入的聚合表示來更新其表示寞奸，2) 每個節(jié)點通過取嵌入的相鄰邊的平均值來更新其表示呛谜。節(jié)點和邊的更新如公式（5）所示。
$\begin{aligned} e_{i j} &=f c_{1}\left(\operatorname{concat}\left(f c_{0}\left(v_{i}\right)\left|f c_{0}\left(v_{j}\right)\right| w_{i j}^{e}\right)\right) (5)\\ v_{i} &=\operatorname{mean}_{j \in \mathcal{N}\left(v_{i}\right)}\left(e_{i j}\right) \end{aligned}$

節(jié)點嵌入表示為 $v_{i}$ 枪萄，其中 $1<=i<=N$ 隐岛， $N$ 是宏和標準單元集群的總數(shù)。連接節(jié)點 $v_{i}$ 和 $v_{j}$ 的矢量邊表示為 $e_{i j}$ 瓷翻。邊 $\left(e_{i j}\right)$ 和節(jié)點嵌入 $\left(v_{i}\right)$ 都被隨機初始化聚凹，并且都是32維矩陣。 $f c_{0}$ 維度是 $32 \times 32, f c_{1}$ 維度是 $65 \times 32$ 齐帚，表示前饋網(wǎng)絡妒牙。 $w_{i j}^{e}$ 是對應邊的可學習的 $1 x 1$ 權重值。 $\mathcal{N}\left(v_{i}\right)$ 是 $v_{i}$ 的鄰節(jié)點对妄。算法的輸出是節(jié)點和邊的嵌入湘今。

我們的監(jiān)督模型包括：(1) 上述的圖數(shù)據(jù)神經(jīng)網(wǎng)絡，它嵌入了節(jié)點類型和網(wǎng)表鄰接矩陣的信息饥伊。(2) 一個全連接的前饋網(wǎng)絡象浑，該網(wǎng)絡嵌入元數(shù)據(jù)，包括底層半導體技術(水平和垂直連線容量)琅豆、網(wǎng)絡的總數(shù)量(邊)愉豺、宏和標準單元集群、畫布大小和網(wǎng)格中的行和列數(shù)茫因。(3) 一個全連接的前饋網(wǎng)絡(預測層)蚪拦，其輸入是網(wǎng)表圖與元數(shù)據(jù)嵌入的串聯(lián)，輸出是獎勵預測冻押。網(wǎng)表圖的嵌入是通過在邊嵌入上應用簡化均值函數(shù)來創(chuàng)建的驰贷。通過回歸訓練監(jiān)督模型，以最小化線長和擁塞的均方根損失的加權和洛巢。

這個監(jiān)督任務使我們可以找到泛化網(wǎng)絡列表的獎勵預測所必須的特征和架構括袒。為了將此體系結(jié)構合并到策略網(wǎng)絡中，我們移除了預測層稿茉，然后將其用作策略網(wǎng)絡的編碼組件锹锰，如圖2所示。

圖2 策略和值網(wǎng)絡架構圖

行和列的不同選擇會帶來網(wǎng)格大小的不同漓库，為了解決這個問題恃慧，我們將網(wǎng)格大小設置為128 x 128，并為小于128行和列的網(wǎng)格大小屏蔽未使用的“L形”部分渺蒿。

在推理時痢士，為了放置一個新的測試網(wǎng)表，我們加載策略網(wǎng)絡的預訓練權重茂装，并將其應用于新網(wǎng)表怠蹂。我們將未進行微調(diào)的預訓練的策略網(wǎng)絡所產(chǎn)生的布局稱為“zero-shot”布局。這樣的布局可以在不到一秒的時間內(nèi)生成少态，因為它只需要預訓練策略網(wǎng)絡的一個推理步驟褥蚯。通過微調(diào)策略網(wǎng)絡，我們可以進一步優(yōu)化布局質(zhì)量况增。這樣的方法給了我們極大的靈活性赞庶，既可以使用預訓練的權值（已經(jīng)學習了輸入狀態(tài)的豐富表示），又可以進一步調(diào)整這些權值以優(yōu)化特定芯片網(wǎng)表的屬性澳骤。

4.2. 策略網(wǎng)絡架構

圖2概述了策略網(wǎng)絡（借由公式3中的 $\pi_{\theta}$ 建模）和我們?yōu)樾酒季纸⒌闹稻W(wǎng)絡架構歧强。這些網(wǎng)絡的輸入是網(wǎng)表圖（圖鄰接矩陣和節(jié)點特征）、當前要放置的節(jié)點ID为肮，以及網(wǎng)表和半導體技術的元數(shù)據(jù)摊册。如前所述，網(wǎng)表圖通過我們提出的圖神經(jīng)網(wǎng)絡架構颊艳。該圖神經(jīng)網(wǎng)絡生成（1）部分布局的圖嵌入和（2）當前節(jié)點嵌入茅特。我們使用一個簡單的前饋網(wǎng)絡來嵌入（3）元數(shù)據(jù)忘分。將這三個嵌入向量連接起來以形成狀態(tài)嵌入，然后將其傳遞到前饋神經(jīng)網(wǎng)絡白修。將前饋網(wǎng)絡的輸出饋送到策略網(wǎng)絡（由5個反卷積層和Batch歸一化層組成）妒峦，以生成動作的概率分布，并傳遞到價值網(wǎng)絡（由前饋網(wǎng)絡組成）以預測輸入狀態(tài)的值兵睛。注意到肯骇，反卷積層的核大小為3x3，步進為2祖很，分別有16笛丙、8、4假颇、2和1個濾波通道胚鸯。

4.3. 策略網(wǎng)絡更新：訓練參數(shù) $\theta$

在方程3中，目標是訓練策略網(wǎng)絡的 $\pi_{\theta}$ 笨鸡，使其在策略網(wǎng)絡的布局分布上reward( $R_{p, g}$ )的期望值( $E$ )最大化蠢琳。為了優(yōu)化這個參數(shù)，我們使用了近端策略優(yōu)化算法(PPO)镜豹，其目標如下:
$L^{C L I P}(\theta)=\hat{E}_{t}\left[\min \left(r_{t}(\theta) \hat{A}_{t}, \operatorname{clip}\left(r_{t}(\theta), 1-\epsilon, 1+\epsilon\right) \hat{A}_{t}\right)\right]$
其中 $\hat{E}_{t}$ 代表每一時步 $t$ 的期望值傲须， $r_{t}$ 代表新策略和舊策略的比率， $A_{t}$ 是每一時步 $t$ 的估計優(yōu)勢趟脂。

5. 結(jié)果

本節(jié)將對我們的方法進行評估泰讽，并回答以下問題：我們的方法是否支持域遷移和從經(jīng)驗中學習？使用預訓練策略對結(jié)果的質(zhì)量有什么影響昔期？與最先進的基準相比已卸，我們方法生成的布局質(zhì)量如何？我們還仔細分析了生成的布局的外觀硼一，并對策略網(wǎng)絡作出相關決定的原因進行分析累澡。

5.1. 遷移學習的結(jié)果

圖3對比了預訓練和從零開始訓練這兩個策略網(wǎng)絡所產(chǎn)生的布局質(zhì)量。Zero-shot指我們將預訓練的策略網(wǎng)絡應用到一個沒有微調(diào)的新網(wǎng)表上般贼，結(jié)果可以在不到一秒的時間內(nèi)得到一個布局愧哟。我們還展示了在2小時和12小時內(nèi)針對一個設計的預訓練策略網(wǎng)絡進行微調(diào)的結(jié)果。從零開始訓練的策略網(wǎng)絡需要花更長的時間才能達到收斂哼蛆，訓練24小時后得到的結(jié)果比微調(diào)的策略網(wǎng)絡訓練12小時后的結(jié)果還要差蕊梧。這證明了經(jīng)過學習得到的權重和接觸多種不同類型的設計，可以幫助我們在更短的時間內(nèi)對一個新的設計實現(xiàn)更高質(zhì)量的布局腮介。

圖3 不同訓練策略的結(jié)果對比

圖4顯示了對Ariane RISC-V CPU分別采取從零開始訓練和預訓練的策略網(wǎng)絡的收斂圖肥矢。預訓練的策略網(wǎng)絡在微調(diào)開始時具有較低的布局成本。隨后叠洗，預訓練的策略網(wǎng)絡收斂到更低的布局成本甘改。當收斂到相同的值時旅东，從零開始訓練的策略網(wǎng)絡要多花30個小時。

圖4 預訓練和從零開始訓練收斂時間的對比

5.2. 從較大的數(shù)據(jù)集中學習

隨著我們在更多芯片塊上訓練十艾，我們能夠加快訓練過程并更快地產(chǎn)生更高質(zhì)量的結(jié)果抵代。圖5（左）顯示了更大的訓練數(shù)據(jù)集對性能的影響。訓練數(shù)據(jù)集是從內(nèi)部TPU塊創(chuàng)建的疟羹。訓練數(shù)據(jù)由各種模塊組成主守，包括內(nèi)存子系統(tǒng)禀倔、計算單元和控制邏輯榄融。當我們將訓練數(shù)據(jù)集的塊數(shù)從2增加到5，最后增加到20時救湖，zero-shot和微調(diào)相同小時的這兩種策略網(wǎng)絡均會產(chǎn)生更好的布局愧杯。圖5（右）顯示了在對策略網(wǎng)絡進行訓練時測試數(shù)據(jù)的布局成本。我們可以看到鞋既，對于較小的訓練數(shù)據(jù)集力九，策略網(wǎng)絡快速產(chǎn)生過擬合，并且測試數(shù)據(jù)的性能下降邑闺，而對于最大的數(shù)據(jù)集跌前，策略網(wǎng)絡產(chǎn)生過擬合的時間更長些。在較大的數(shù)據(jù)集上預訓練策略網(wǎng)絡在測試數(shù)據(jù)上會產(chǎn)生更好的結(jié)果陡舅。該圖表明抵乓，隨著我們在更多不同種類的芯片塊中訓練策略網(wǎng)絡，盡管預訓練時間會更長靶衍，但策略網(wǎng)絡變得不容易產(chǎn)生過擬合灾炭，并且可以更好地為新的芯片塊找到優(yōu)化的位置。

圖5 訓練集的大小對布局成本和訓練時間的影響

5.3. 可視化分析

圖6顯示了Ariane RISCV CPU的布局結(jié)果颅眶。左圖是zero-shot策略網(wǎng)絡的布局蜈出，右側(cè)是經(jīng)過微調(diào)的策略網(wǎng)絡的布局。zero-shot可以對未見過的芯片生成布局涛酗。zero-shot策略網(wǎng)絡將標準單元放在由宏包圍的畫布中心铡原，這非常接近最優(yōu)布局。微調(diào)后商叹，宏的放置變得更規(guī)則眷蜈，并且中心的標準單元區(qū)域變得更不擁塞。

圖6 芯片布局可視化

圖7給出了布局的可視化：左圖是手動布局的結(jié)果沈自，右圖是我們方法得到的結(jié)果酌儒。白色區(qū)域是宏的布局，綠色區(qū)域是標準單元的布局枯途。我們的方法是在標準單元周圍創(chuàng)建宏的環(huán)狀布局忌怎，從而減少了總線長籍滴。

圖7 兩種方式的布局可視化

5.4. 與基準方法的比較

在本節(jié)中，我們將我們的方法與3種基準方法進行比較榴啸，分別是：模擬退火孽惰、RePlAce和人類專家基準。我們的方法在最大的數(shù)據(jù)集（包含20個TPU塊）上使用預訓練的策略鸥印，然后在5個未見過的目標塊上進行微調(diào)勋功，分別記為塊1到塊5。數(shù)據(jù)集包括各種模塊库说，包括內(nèi)存子系統(tǒng)狂鞋、計算單元以及控制邏輯。出于保密潜的，我們無法透露這些塊的詳細信息骚揍，但給出塊的規(guī)模，即每個塊最多包含數(shù)百個宏和數(shù)百萬個標準單元啰挪。

和模擬退火的比較：模擬退火（SA）是一種功能強大但緩慢的優(yōu)化方法信不。但是，像RL一樣亡呵，模擬退火能夠優(yōu)化任意不可微的成本函數(shù)抽活。為了了解RL的相對樣本效率，我們進行了實驗锰什，將RL替換為基于模擬退火的優(yōu)化器下硕。在這些實驗中，我們使用與以前相同的輸入和成本函數(shù)歇由，但是在每個事件中卵牍，模擬退火優(yōu)化器都會放置所有宏，然后執(zhí)行FD步驟放置標準單元集群沦泌。根據(jù)SA更新規(guī)則糊昙，使用指數(shù)衰減退火進度表接受每個宏的布局。SA需要花費18個小時才能收斂谢谦，而我們的方法花費不超過6個小時释牺。

為了公平比較，我們通過掃描不同的超參數(shù)進行了多次SA實驗回挽，包括最小和最大溫度没咙、種子和最大SA集，以使得SA和RL在模擬中花費相同的CPU時間并搜索相同數(shù)量的狀態(tài)千劈。表1列出了實驗的最低成本結(jié)果祭刚。由表可知，與我們的方法相比，即使有更多的時間涡驮，SA也很難產(chǎn)生高質(zhì)量布局暗甥，并且產(chǎn)生的布局平均線長比我們的方法高14.4%，平均擁塞高24.1%捉捅。

表1 SA和RL結(jié)果對比
與RePIAce和人工布局的比較：表 2 將我們的結(jié)果與最先進的RePlIAce 和人工布局進行了比較撤防。人工布局是由一個芯片設計團隊生成的，涉及許多布局優(yōu)化的迭代棒口，由商業(yè)EDA工具在幾周內(nèi)提供反饋指導寄月。

關于RePlAce，我們有相同的優(yōu)化目標无牵，即優(yōu)化芯片布局漾肮，但是我們使用不同的目標函數(shù)。因此合敦，我們沒有比較不同成本函數(shù)的結(jié)果初橘，而是著眼于商業(yè)EDA工具的輸出結(jié)果验游。為了進行比較充岛，我們調(diào)整了我們的方法和RePlAce方法生成的宏布局，并允許EDA工具按照默認設置來進一步優(yōu)化標準單元的布局耕蝉。然后崔梗，得到總線長、時序（最差（WNS）和總（TNS）負松弛）垒在、面積和功率指標的輸出報告蒜魄。如表2所示，在滿足設計要求下场躯，我們的方法得到的布局結(jié)果優(yōu)于RePLAce谈为。給定底層半導體技術相關約束，如果WNS明顯高于100 ps時踢关，或者水平和垂直的任一擁塞超過1％導致一些RePLAce（塊1伞鲫、2、3）布局不可用時签舞，則在設計后期這些塊的布局無法滿足時序約束秕脓。這些結(jié)果表明，我們這個考慮到擁塞的方法可以有效生成符合設計標準的高質(zhì)量布局儒搭。

表2 我們的方法與RePLAce方法吠架、專家布局方法的對比

RePIAce比我們的方法更快，因為它收斂時間為1到3.5小時搂鲫，而我們的方法收斂時間為3到6小時傍药。可是，我們的方法具有一些很基本的優(yōu)點：1) 我們的方法可以輕松對各種不可微的成本函數(shù)進行優(yōu)化拐辽，而無需建立這些成本函數(shù)的可微分等價方程褪秀。例如，雖然很容易將線長建模為凸函數(shù)薛训，但對于布線擁塞或時序卻不是這樣媒吗。 2) 隨著策略學習到更多的芯片塊，我們的方法能夠隨著時間的推移而不斷改進乙埃；3) 我們的方法能夠滿足各種設計約束闸英，例如不同形狀的塊。

表2還顯示了由人工專家設計的結(jié)果介袜。我們的方法和人類專家一樣甫何，都可以生成可行的布局，即都滿足時間和擁塞設計標準遇伞。在WNS辙喂、面積、功耗和線長方面鸠珠，我們的方法得到的結(jié)果勝過或者可以與專家設計的結(jié)果相媲美巍耗。此外，我們的端到端基于學習的方法只需要不到6個小時渐排，而手工基線的方法則需要專家多次參與緩慢的迭代優(yōu)化工作炬太，這可能需要數(shù)周時間。

5.5. 討論

進一步優(yōu)化我們方法的可能：有多種機會可以進一步提高我們方法的布局質(zhì)量驯耻，例如標準單元的分區(qū)亲族、行數(shù)和列數(shù)的選擇、以及放置宏的順序等可缚。我們的方法還可以從其他標準單元布局算法得到進一步優(yōu)化霎迫。目前，考慮到標準單元較快的運行速度帘靡，我們使用力導向法對其進行布局知给。可是测柠，我們相信有更好的方法對標準單元進行布局炼鞠，例如RePlAce和DREAMPlace，這些方法可以生成更準確的標準單元布局轰胁，以指導訓練策略網(wǎng)絡谒主。這將會很有用，因為如果策略網(wǎng)絡在宏布局如何影響標準單元布局和最終指標方面有更清晰的信號赃阀，則它可以學習做出更優(yōu)化的宏布局決策霎肯。
方法的推廣和應用：本文的工作只是域適應策略應用于優(yōu)化問題的一個例子擎颖，可以擴展應用到芯片設計的其他階段，例如架構和邏輯設計观游、邏輯綜合和驗證搂捧，其共同目標是訓練機器學習的模型并讓模型隨著學習實例增加而不斷改善《疲基于學習的方法還可以在芯片設計的流程中執(zhí)行關于設計空間探索和協(xié)同優(yōu)化的工作允跑。

6. 總結(jié)

本文針對復雜且重要的芯片布局問題，提出了一種基于強化學習的方法搪柑，使遷移學習成為可能聋丝。由于RL agent在大量的芯片網(wǎng)表上學習布局經(jīng)驗，因此芯片布局的質(zhì)量將變得更快更好工碾。實驗證明了我們的方法優(yōu)于最先進的基準弱睦，在現(xiàn)代加速器布局方面優(yōu)于或媲美于人類專家設計。我們的方法是端到端的渊额，可在6小時內(nèi)完成布局况木，而最好的基準需要人類專家花幾周時間進行多次迭代優(yōu)化工作。

拓展學習鏈接

[RL]https://zh.wikipedia.org/wiki/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0
[Dennard縮放比例定律]https://www.jiqizhixin.com/articles/2019-10-23-13
[什么是baseline]https://blog.csdn.net/Lison_Zhu/article/details/97554928
[初窺模擬退火]https://zhuanlan.zhihu.com/p/47628209
[遷移學習的全面概述]https://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650724800&idx=2&sn=0d5e47e071c346eb4a485980deee5744&chksm=871b1dbeb06c94a81b74afcde32d759b7118d60e60b710570a2d6cf53fbe2a9badaed44c5f05#rd
[力導向布局算法]http://www.reibang.com/p/d3c64a39535a
[拓撲排序]http://www.reibang.com/p/b59db381561a

谷歌AI布局論文解讀1：翻譯部分