基于視覺強(qiáng)化學(xué)習(xí)的數(shù)字芯片全局布局方法

摘 要：在數(shù)字芯片后端設(shè)計(jì)中，全局布局需要同時(shí)兼顧線長與合法化，是一個(gè)組合優(yōu)化問題。傳統(tǒng)的退火算法或者遺傳算法耗時(shí)且容易陷入局部最優(yōu)，目前強(qiáng)化學(xué)習(xí)的解決方案也很少利用布局的整體視覺信息。為此，提出一種融合視覺信息的強(qiáng)化學(xué)習(xí)方法實(shí)現(xiàn)端到端的全局布局。在全局布局中，將電路網(wǎng)表信息映射為多個(gè)圖像級特征，采用卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）和圖卷積網(wǎng)絡(luò)（graph convolutional network，GCN）將圖像特征和網(wǎng)表信息相融合，設(shè)計(jì)了一整套策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)，實(shí)現(xiàn)對全局布局的全面分析和優(yōu)化。在ISPD2005基準(zhǔn)電路上進(jìn)行實(shí)驗(yàn)，結(jié)果證明設(shè)計(jì)的網(wǎng)絡(luò)收斂速度加快7倍左右，布局線長減少10%～32%，重疊率為0%，可為數(shù)字芯片全局布局任務(wù)提供高效合理的方案。

關(guān)鍵詞：全局布局； 深度強(qiáng)化學(xué)習(xí)； 計(jì)算機(jī)視覺； 圖卷積神經(jīng)網(wǎng)絡(luò)； 數(shù)字芯片

中圖分類號：TP391.7文獻(xiàn)標(biāo)志碼： A文章編號：1001－3695（2024）04－046－1270－05

doi：10.19734/j.issn.1001－3695.2023.08.0385

Visual－based reinforcement learning for digital chip global placement

Xu Fanfeng， Tong Minglei

Abstract： In the back－end design of digital chips， it needs to consider both wire length and legalisation during global placement. Global placement represents a combinatorial optimization problem. Traditional annealing algorithms or genetic algorithms consume a significant amount of time and are susceptible to entering local optima. Current reinforcement learning solutions seldom leverage the overall visual information of the placement. Therefore， this paper proposed a reinforcement learning method that incorporated visual information to attain end－to－end global placement. During the global placement， it mapped the circuit netlist information into multiple image－level features， and utilized CNN and GCN to merge the image features with the netlist information. It employed a complete set of strategy networks and value networks to conduct comprehensive analysis and optimization of the global placement. Experiments on the ISPD2005 benchmark circuit demonstrate that the designed networks accelerate the convergence speed by approximately 7 times， reduce the placement wire length by 10% to 32%， and achieve a 0% overlap rate. This approach offers an efficient and rational solution for the global placement task of digital chips.

Key words：global placement; deep reinforcement learning; computer vision; graph convolutional neural network; digital chip

0 引言

近幾十年來， 隨著超大規(guī)模集成電路（VLSI）技術(shù)的發(fā)展［1］， 數(shù)字芯片的集成度不斷提高， 芯片中使用大量的知識產(chǎn)權(quán)核心（IP）來實(shí)現(xiàn)模塊化［2］。因此在后端設(shè)計(jì)中，全局布局需要考慮的宏塊（如SRAM）數(shù)量逐漸增加，其尺寸和復(fù)雜性也隨之增加。在后端設(shè)計(jì)流程中，全局布局至關(guān)重要［3］，其中涉及如何在硅片水平方向上放置宏塊，且在有限的芯片面積內(nèi)合理布局，極大數(shù)量的宏塊［4］。在過去的幾十年中，人們在芯片自動(dòng)全局布局領(lǐng)域［5］取得了很大進(jìn)展，但實(shí)現(xiàn)完全自動(dòng)化的設(shè)計(jì)規(guī)劃仍然非常困難［6］。目前，即使最先進(jìn)的EDA工具也需要物理設(shè)計(jì)工程師的手動(dòng)干預(yù)和優(yōu)化［7］，以便產(chǎn)生可制造的全局布局。全局布局的可制造性［8］通常包括芯片尺寸、器件密度、布線長度等方面。

全局布局可以視為帶有幾何約束的2D裝箱問題的復(fù)雜變種［9］，其目標(biāo)是實(shí)現(xiàn)宏塊零重疊并減少線長。近年來，國內(nèi)外學(xué)者針對此問題的研究可以概述為兩類［9］，分別是基于優(yōu)化的方法和基于學(xué)習(xí)的方法。

基于優(yōu)化的方法包括：a）基于模擬退火算法采用了一種隨機(jī)游走的優(yōu)化策略，優(yōu)勢在于在短時(shí)間內(nèi)能夠?qū)ふ业捷^優(yōu)解，然而劣勢在于可能陷入局部最優(yōu)解；b）基于遺傳算法采用進(jìn)化計(jì)算技術(shù)，優(yōu)勢在于能夠搜索解空間中的多個(gè)最佳解，并可自動(dòng)調(diào)整搜索策略，但需投入大量的計(jì)算時(shí)間和資源，因此在大規(guī)模芯片設(shè)計(jì)場景下并不十分適用；c）基于貪心算法采用貪心策略，從初始布局出發(fā)，逐步優(yōu)化布局，其優(yōu)勢在于速度快，適用于中小規(guī)模芯片設(shè)計(jì)，但缺陷在于難以找到全局最優(yōu)解；d）基于力導(dǎo)向布局算法運(yùn)用物理學(xué)中的力學(xué)原理，通過在芯片元件間構(gòu)建彈性力學(xué)模型，使其在不同的布局空間內(nèi)運(yùn)動(dòng)，最終生成最優(yōu)布局，這一方法的優(yōu)勢在于規(guī)避局部最優(yōu)解，且能有效處理布局約束，但同樣需要大量的計(jì)算時(shí)間和資源。需要注意的是，這些基于優(yōu)化的方法都需要對目標(biāo)函數(shù)進(jìn)行定義和優(yōu)化，這個(gè)過程本身可能存在一定的主觀性，因此結(jié)果可能并不是絕對準(zhǔn)確的。此外，這些方法在應(yīng)對復(fù)雜的約束條件和大規(guī)模芯片設(shè)計(jì)時(shí)也存在一定的挑戰(zhàn)。

基于學(xué)習(xí)的方法現(xiàn)在仍處于起步階段，隨著GPU性能越來越強(qiáng)大和機(jī)器學(xué)習(xí)應(yīng)用越來越廣泛，在很多領(lǐng)域都能發(fā)揮極大的作用，甚至在某些方面可以超越人類專家。深度強(qiáng)化學(xué)習(xí)有自適應(yīng)性和搜索能力，被認(rèn)為是一種有潛力解決這類NP－h(huán)ard問題［10］的方法。通過學(xué)習(xí)最佳策略，可以在給定的約束條件下找到近似最優(yōu)的解決方案，比如現(xiàn)在的AlphaZero［11］、ChatGPT［12］等。對宏塊的放置可以類似看作一個(gè)下圍棋的過程，每次執(zhí)行一步都會對未來產(chǎn)生影響，如DeepPR［13］中采用PPO算法搭建網(wǎng)絡(luò)，智能體把每一個(gè)宏塊看作像素點(diǎn)，依次在畫布上擺放。

然而，現(xiàn)有的基于學(xué)習(xí)方法的全局布局在優(yōu)化線長時(shí)沒有充分利用電路原始信息，只利用了宏塊位置，將單一信息作為狀態(tài)空間的輸入，導(dǎo)致線長的下降達(dá)到瓶頸，也沒有對合法化進(jìn)行硬約束。針對上述問題，本文提出了一種基于A2C算法［14］的強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)框架，實(shí)現(xiàn)了端到端的全局布局，采用計(jì)算機(jī)視覺分別把宏塊的位置、尺寸和連接關(guān)系映射為四張像素圖，并結(jié)合圖論方法［15］， 實(shí)現(xiàn)多模態(tài)輸入狀態(tài)空間，充分利用了圖像和電路結(jié)構(gòu)的信息。在考慮真實(shí)宏塊大小的情況下，以最小化線長和零重疊為目標(biāo)，優(yōu)化了密集內(nèi)在獎(jiǎng)勵(lì)和外在獎(jiǎng)勵(lì)。以精妙的策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)提取整體和局部信息，設(shè)計(jì)了合適的環(huán)境，可以實(shí)現(xiàn)自動(dòng)讀取電路網(wǎng)表信息的功能，包括芯片面積、宏塊大小、引腳偏移、連接關(guān)系，并將這些信息等比縮放映射到一個(gè)128×128的平面上，便于智能體進(jìn)行交互，在硅片上自動(dòng)分配宏塊位置，最終得出網(wǎng)表優(yōu)化結(jié)果。

實(shí)驗(yàn)結(jié)果表明，在ISPD2005基準(zhǔn)電路［16］中，本設(shè)計(jì)的全局布局重疊率可以達(dá)到0%，線長比目前的先進(jìn)方法降低10%～32%，網(wǎng)絡(luò)收斂速度比同樣是強(qiáng)化學(xué)習(xí)方法的DeepPR快7倍左右。綜上所述，本文為數(shù)字芯片全局布局任務(wù)提供了快速合理的解決方案。

1 相關(guān)工作

1.1 全局布局

目前主流的EDA公司都把布局布線算法嵌入到本公司的EDA軟件中。在數(shù)字電路后端設(shè)計(jì)中，布局布線流程如圖1所示。全局布局是芯片設(shè)計(jì)過程中最關(guān)鍵且最耗時(shí)的步驟之一，直接影響了芯片的性能、功耗、可靠性、成本和未來的可維護(hù)性。全局布局的輸入是網(wǎng)表，其中包括每個(gè)網(wǎng)絡(luò)內(nèi)宏塊的互連關(guān)系。此環(huán)節(jié)中主要考慮的是如何以最小化布線長度在有限的芯片面積內(nèi)精確分配宏塊位置，并輸出供詳細(xì)布局使用的優(yōu)化網(wǎng)表。良好的全局布局會帶來更好的芯片面積利用率和時(shí)序性能，而較差的全局布局會影響芯片的性能，甚至使其無法制造。

1.2 基于優(yōu)化的全局布局方法

ePlace ［17］和RePlAce ［18］采用力導(dǎo)向法和非線性優(yōu)化器，這兩種方法將網(wǎng)表的每個(gè)節(jié)點(diǎn)（宏塊）表示為帶正電的粒子。通過排斥力的調(diào)節(jié)，模擬節(jié)點(diǎn)之間的相互作用，密度函數(shù)D（x， y）對應(yīng)系統(tǒng)勢能。該分析方法基于梯度的優(yōu)化方案更新宏塊的位置，引入了基于靜電的全局平滑密度代價(jià)函數(shù)和內(nèi)斯特羅夫方法，非線性優(yōu)化器能更平滑地逼近代價(jià)函數(shù)，但是計(jì)算成本高，推理速度慢，需要大量計(jì)算資源且不能達(dá)到最優(yōu)解。

DREAMPlace［19］基于最先進(jìn)的分析放置算法RePlAce，通過深度學(xué)習(xí)工具包PyTorch實(shí)現(xiàn)手動(dòng)優(yōu)化的關(guān)鍵操作符，與基于CPU的工具相比，實(shí)現(xiàn)了超過30倍的加速。該方法以最小化線長函數(shù)WL（x，y）和密度函數(shù)D（x，y）為目標(biāo)，放松了密度約束，不能直接生成有效的可制造布局，還需后續(xù)的手動(dòng)調(diào)整，使布局達(dá)到合法化。

1.3 基于學(xué)習(xí)的全局布局方法

graph placement［20］是一種基于學(xué)習(xí)的端到端宏塊放置方法的創(chuàng)新，采用強(qiáng)化學(xué)習(xí)智能體擺放15%的宏塊以減少計(jì)算量，其余宏塊采用優(yōu)化的方法放置。價(jià)值網(wǎng)絡(luò)采用GCN對網(wǎng)表信息進(jìn)行編碼，該方法的代價(jià)是要舍棄宏塊的引腳偏移，因?yàn)楹陦K上可能存在成百上千個(gè)引腳，如果把帶有豐富引腳信息的網(wǎng)表輸入GCN，會導(dǎo)致網(wǎng)絡(luò)難以學(xué)到復(fù)雜的連接關(guān)系。不同的網(wǎng)絡(luò)中宏塊之間是通過不同引腳連接的，粗略放置會導(dǎo)致線長的增加。同時(shí)此方法存在獎(jiǎng)勵(lì)稀疏問題，不利于智能體的學(xué)習(xí)。

DeepPR同樣也采用了GCN，也存在和graph placement同樣的問題。其采用了隨機(jī)蒸餾作為內(nèi)在密集獎(jiǎng)勵(lì)，此方法能使智能體增加探索，但是和最終布局完成的外在獎(jiǎng)勵(lì)關(guān)系不緊密，會影響智能體的優(yōu)化方向。同時(shí)DeepPR把宏塊均映射為32×32平面上的1個(gè)像素點(diǎn)，沒有考慮宏塊真實(shí)尺寸，導(dǎo)致重疊率大大增加，即使后期修正也有可能無解，任何重疊在實(shí)際中都是不可行的。

2 問題描述與注釋

全局布局的主要任務(wù)是將尺寸不同的宏塊放到有限面積的硅片上，其有兩大優(yōu)化目標(biāo)。首先，合法化是確保宏塊之間的擺放互不重疊且不超出硅片邊界，重疊率的計(jì)算公式如下：

其中：m表示宏塊數(shù)量；si表示每個(gè)宏塊實(shí)際大??；Sreal表示放置完成后宏塊占據(jù)硅片的總面積。圖2中的情況是不可制造的無效布局。

其次，另一個(gè)目標(biāo)是盡量將同一網(wǎng)絡(luò)的宏塊放置在靠近的位置，將連線的長度最小化。在布局優(yōu)化中，對于線長的優(yōu)化通常采用半周長線長（half－perimeter wirelength，HPWL）進(jìn)行衡量。HPWL的定義為

其中：xi、yi表示網(wǎng)絡(luò)內(nèi)引腳的坐標(biāo)，通過此方法可以找到容納網(wǎng)絡(luò)內(nèi)所有引腳的最小矩形，并取矩形周長的一半作為網(wǎng)絡(luò)線長。結(jié)果與實(shí)際線長成正比，因此該方法較為準(zhǔn)確且計(jì)算復(fù)雜度低。

本文引入了引腳偏移的概念，采用了五角星點(diǎn)計(jì)算HPWL，相比于不引入引腳偏移時(shí)統(tǒng)一采用左下角圓點(diǎn)計(jì)算HPWL，引入引腳偏移可以更精準(zhǔn)地評估線長，如圖3所示。

3 數(shù)字芯片全局布局方法設(shè)計(jì)

3.1 馬爾可夫決策過程

利用強(qiáng)化學(xué)習(xí)方法解決此問題，需要構(gòu)建包括狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)在內(nèi)的馬爾可夫決策過程［21］，如圖4所示。

模型應(yīng)用流程如下：

a）輸入待優(yōu)化電路的網(wǎng)表信息到預(yù)處理模塊，提取需要的宏塊和芯片信息給環(huán)境。

b）環(huán)境中生成初始狀態(tài)s0和初始內(nèi)在獎(jiǎng)勵(lì)ri0。

c）智能體讀取狀態(tài)s0并生成動(dòng)作a0。

d）動(dòng)作a0返回環(huán)境生成下一狀態(tài)s1和內(nèi)在獎(jiǎng)勵(lì)ri1。

e）重復(fù)流程c）d）。

f）擺放最后一個(gè)宏塊后，環(huán)境給出外在獎(jiǎng)勵(lì)re。

g）輸出優(yōu)化之后的電路網(wǎng)表信息。

3.2 網(wǎng)絡(luò)結(jié)構(gòu)

本文設(shè)計(jì)的強(qiáng)化學(xué)習(xí)端到端網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示。

策略網(wǎng)絡(luò)中將一張宏塊位置圖、一張位置遮罩圖、一張線長熱力圖和一張引腳熱力圖，四張圖拼接作為分支卷積網(wǎng)絡(luò)的輸入，得到兩個(gè)輸出特征F1、F2。再將位置遮罩圖、線長熱力圖和引腳熱力圖拼接，并通過重提取神經(jīng)網(wǎng)絡(luò)整合原始信息到更高級別的特征表示中，使得網(wǎng)絡(luò)更容易學(xué)習(xí)到細(xì)粒度的特征和局部信息。得到的特征F3與F2拼接后經(jīng)過一個(gè)1×1的卷積層，再與位置遮罩圖、線長熱力圖和引腳熱力圖點(diǎn)乘，此過程本質(zhì)上是通過一種加權(quán)融合的方式得到動(dòng)作at。價(jià)值網(wǎng)絡(luò)中將網(wǎng)表信息和宏塊坐標(biāo)輸入圖神經(jīng)網(wǎng)絡(luò)，再與分支神經(jīng)網(wǎng)絡(luò)輸出的特征F1拼接，最后通過全連接層輸出價(jià)值vt。

3.3 狀態(tài)空間

本設(shè)計(jì)采用計(jì)算機(jī)視覺的方法從四個(gè)角度提取硅片當(dāng)前的狀態(tài)信息，并表示為四張128×128的像素圖，這樣可以更好地捕捉狀態(tài)的多樣性和復(fù)雜性，讓智能體精準(zhǔn)地學(xué)習(xí)最佳策略。

3.3.1 宏塊位置圖

如圖6所示，宏塊位置圖表示當(dāng)前硅片上宏塊的擺放情況，強(qiáng)化學(xué)習(xí)算法選擇的動(dòng)作是宏塊的左下角坐標(biāo)，原點(diǎn)坐標(biāo)為左下角。下文將以該坐標(biāo)作為宏塊位置的參考點(diǎn)。

3.3.2 位置掩碼圖

為了貼合實(shí)際情況引入宏塊尺寸，在宏塊放置時(shí)要避免重疊問題。如圖7所示，當(dāng)放置第t個(gè)宏塊M3時(shí)，將前t-1個(gè)宏塊按照M3的尺寸（2，4）向左下方膨脹。宏塊M1尺寸為 （u，v），宏塊M2尺寸為（m，n），膨脹后M1的左下角坐標(biāo)從（x y1）平移到（x2- y2-3），尺寸膨脹為（u+ v+3），M2左下角坐標(biāo)從（x2，y2）平移到（x2- y2-3），尺寸膨脹為（m+ n+3），同時(shí)為了防止宏塊超出全局布局邊界，將上邊界膨脹（4-1）個(gè)單位大小，右邊界膨脹（2-1）個(gè)單位大小，每個(gè)模塊放置之前都會進(jìn)行同樣的膨脹操作，圖7中白色區(qū)域?yàn)楹陦KM3可用位置。此方法相較于傳統(tǒng)方法中驗(yàn)證每個(gè)像素點(diǎn)是否重疊，大大降低了計(jì)算復(fù)雜度。

3.3.3 線長熱力圖

放置第t個(gè)宏塊時(shí)，首先篩選出與其相連的所有宏塊，然后取這n個(gè)宏塊的中心點(diǎn)，最后通過高斯核生成線長熱力圖用于指導(dǎo)第t個(gè)宏塊的最佳擺放位置，以使得線長最短。如圖8所示，M1、M2是互連的宏塊，以它們的中心點(diǎn)生成高斯核熱力圖，顏色越淺表示下一個(gè)宏塊加入后，增加的線長越短。

3.3.4 引腳熱力圖

生成線長熱力圖的這些宏塊，互相之間不一定存在連接關(guān)系。因此，還需要第t個(gè)宏塊引腳所在網(wǎng)絡(luò)的精確信息，進(jìn)一步細(xì)化連接關(guān)系，保證每個(gè)網(wǎng)絡(luò)的引腳盡量靠近，降低線長。

放置第t個(gè)宏塊時(shí)，需要確定其所在的網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含宏塊的引腳相連信息。首先通過已擺放宏塊的引腳偏移計(jì)算出網(wǎng)絡(luò)的形狀，然后計(jì)算每個(gè)點(diǎn)到該網(wǎng)絡(luò)的曼哈頓距離并生成引腳熱力圖。如圖9所示，如果第t個(gè)模塊在此網(wǎng)絡(luò)中的引腳放置在矩形框區(qū)域內(nèi)，則線長增加為0。如果第t個(gè)宏塊有n個(gè)引腳，則會計(jì)算n個(gè)網(wǎng)絡(luò)的熱力圖并將其疊加，生成此宏塊的引腳熱力圖。

3.4 動(dòng)作空間

將芯片等比例縮放映射為128×128的平面作為動(dòng)作空間，像素圖上的點(diǎn)表示可選動(dòng)作，即宏塊可放置位置。

3.5 放置順序

為了使線長熱力圖和引腳熱力圖發(fā)揮最大的作用，不同于其他設(shè)計(jì)按宏塊的序號或尺寸擺放，本設(shè)計(jì)考慮到引腳偏移和連接關(guān)系的復(fù)雜度，因此設(shè)定了一個(gè)特殊的宏塊擺放順序，即按宏塊的引腳數(shù)量從大到小排序。此方法可以保證在前期宏塊放置的過程中，能盡快把網(wǎng)絡(luò)的形狀確定下來。反之，如果后期放置時(shí)存在某個(gè)大量引腳的宏塊，該宏塊可能引起十幾個(gè)甚至上百個(gè)網(wǎng)絡(luò)的變動(dòng)，從而導(dǎo)致線長波動(dòng)增大，使模型不穩(wěn)定。

3.6 內(nèi)在獎(jiǎng)勵(lì)和外在獎(jiǎng)勵(lì)

內(nèi)在獎(jiǎng)勵(lì)為宏塊擺放前后半周長線長（HPWL）變化值的相反數(shù)，公式如下：

其中：rit表示放置第t個(gè)宏塊的內(nèi)在獎(jiǎng)勵(lì)；ni表示第i個(gè)網(wǎng)絡(luò)。相比于DeepPR，使用隨機(jī)蒸餾作為內(nèi)在獎(jiǎng)勵(lì)，本設(shè)計(jì)同樣保證了獎(jiǎng)勵(lì)的密集度，也保證了每個(gè)時(shí)間步的獎(jiǎng)勵(lì)都和最終的獎(jiǎng)勵(lì)、最終的獎(jiǎng)勵(lì)總線長相關(guān)，使智能體以減少每個(gè)網(wǎng)絡(luò)的HPWLm為明確目標(biāo)。

外在獎(jiǎng)勵(lì)計(jì)算公式如下，其中HPWLc（N）是采用DREAMPlace工具對最終的全局布局結(jié)果進(jìn)行詳細(xì)布局的結(jié)果，超參λ根據(jù)給定的電路情況進(jìn)行調(diào)節(jié)。

3.7 強(qiáng)化學(xué)習(xí)

本文采用A2C算法，一種基于策略梯度和價(jià)值函數(shù)的強(qiáng)化學(xué)習(xí)方法。策略網(wǎng)絡(luò)的策略梯度更新公式如下：

其中：J（θ）表示目標(biāo)策略的性能;θJ（θ）表示策略梯度；π（at|st）表示在宏塊擺放狀態(tài)st下選擇位置at的概率；Aπ（st，at）表示相對于基準(zhǔn)函數(shù)B（st）的優(yōu)勢函數(shù)。

對于價(jià)值網(wǎng)絡(luò)的值函數(shù)更新，則需要先計(jì)算出每一次的獎(jiǎng)勵(lì)，然后使用TD誤差計(jì)算當(dāng)前狀態(tài)值和下一時(shí)刻狀態(tài)值之間的誤差，進(jìn)而更新價(jià)值網(wǎng)絡(luò)的參數(shù)，公式如下：

其中：r是當(dāng)前時(shí)刻的獎(jiǎng)勵(lì)；γ是折扣因子；V（s′）是下一時(shí)刻的狀態(tài)值；V（s）是當(dāng)前時(shí)刻的狀態(tài)值，使用每個(gè)狀態(tài)s的TD誤差δ的平方來衡量當(dāng)前值函數(shù)V（s）的誤差，并用該誤差更新價(jià)值網(wǎng)絡(luò)的參數(shù)。

A2C算法流程如下：

a）初始化策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)的參數(shù)。

b）128×128的空白圖像作為初始化狀態(tài)s0的輸入，使用策略網(wǎng)絡(luò)生成第一塊宏塊位置，即動(dòng)作a0。

c）環(huán)境中生成下一時(shí)刻的狀態(tài)s1和對應(yīng)的內(nèi)在獎(jiǎng)勵(lì)r1。

d）使用價(jià)值網(wǎng)絡(luò)估計(jì)當(dāng)前的狀態(tài)值，并計(jì)算TD誤差δ。

e）更新價(jià)值網(wǎng)絡(luò)的參數(shù)以減少TD誤差。

f）使用TD誤差δ計(jì)算優(yōu)勢函數(shù)Aπ（st，at）。

g）使用策略梯度公式更新策略網(wǎng)絡(luò)參數(shù)。

h）將狀態(tài)更新為下一狀態(tài)s 并返回步驟b）。

經(jīng)過大約50輪的迭代，策略和價(jià)值網(wǎng)絡(luò)的參數(shù)將會逐漸趨于最優(yōu)狀態(tài)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)配置

本文的實(shí)驗(yàn)基于64位Linux操作系統(tǒng)，以Python 3.7為語言環(huán)境，PyTorch 1.12為深度學(xué)習(xí)框架。實(shí)驗(yàn)在12核20線程的i7－12700KF CPU和32 GB內(nèi)存上運(yùn)行，并由10 GB的NVIDIA GeForce RTX3080 GPU加速。CUDA版本為11.7。訓(xùn)練本文模型時(shí)，Adam優(yōu)化器［22］學(xué)習(xí)率設(shè)置為6×10E-3。

4.2 基準(zhǔn)電路

表1中的6個(gè)電路均是ISPD2005基準(zhǔn)電路，來源于現(xiàn)代工業(yè)專用集成電路設(shè)計(jì)。這些基準(zhǔn)電路包括相當(dāng)獨(dú)特的功能特征，以代表現(xiàn)代物理設(shè)計(jì)的挑戰(zhàn)，其中提供了待布局的原始網(wǎng)表數(shù)據(jù)和電路信息。首先對每個(gè)基準(zhǔn)電路進(jìn)行處理，篩選出和其他宏塊不連接的獨(dú)立宏塊，接著把處理好的電路文件輸入到本文的端到端模型，智能體負(fù)責(zé)對可移動(dòng)宏塊進(jìn)行放置，最后得出優(yōu)化之后的網(wǎng)表結(jié)果。

4.3 全局布局結(jié)果與主流算法效果對比

目前，最先進(jìn)的全局布局器包括基于優(yōu)化方法的DREAMPlace、基于強(qiáng)化學(xué)習(xí)方法的DeepPR，以及將強(qiáng)化學(xué)習(xí)和優(yōu)化方法融合的graph placement。本文參考之前的研究［20］，計(jì)算放置完標(biāo)準(zhǔn)單元之后的HPWL（×107），并采用式（3）來計(jì)算全局布局中的重疊率，其中DREAMPlace是參照文獻(xiàn)［20］的實(shí)驗(yàn)設(shè)置。

如表2所示，本文提出的全局布局模型與其他算法布局結(jié)果相比，線長減少了10%～32%且能達(dá)到零重疊。這意味著在設(shè)計(jì)中能夠有效地減少電路元件之間的沖突，從而提高電路的可靠性和性能。圖10（a）和（b）為DeepPR及本文模型分別在電路adaptec3上全局布局的實(shí)際結(jié)果圖，很明顯本文結(jié)果更符合實(shí)際應(yīng)用。

4.4 算法復(fù)雜度對比

表3對比了同樣是強(qiáng)化學(xué)習(xí)方法的DeepPR和本文模型布局網(wǎng)絡(luò)的收斂速度，結(jié)果表明，本文模型收斂速度可以比DeepPR更快收斂到最優(yōu)解。

傳統(tǒng)組合優(yōu)化方法的DREAMPlace中雖然部分采用了深度學(xué)習(xí)工具包PyTorch以及GPU加速，但本質(zhì)上是在連續(xù)的空間上搜索宏塊位置，仍需要經(jīng)過多次迭代、局部搜索、參數(shù)調(diào)整等優(yōu)化過程，這些過程需要很多計(jì)算時(shí)間來達(dá)到最優(yōu)解或接近最優(yōu)解。表4所示，本文模型和DeepPR是在離散空間上搜索動(dòng)作，均比DREAMPlace的推理速度快兩倍左右。

4.5 消融實(shí)驗(yàn)

為了驗(yàn)證策略網(wǎng)絡(luò)中各個(gè)模塊對網(wǎng)絡(luò)有積極影響，在adaptec3電路圖上設(shè)計(jì)消融實(shí)驗(yàn)，結(jié)果如表5所示。

進(jìn)一步分析實(shí)驗(yàn)結(jié)果，得到以下結(jié)論：

a）在狀態(tài)空間中，宏塊位置圖可以讓智能體獲取宏塊的精準(zhǔn)位置和整體擺放情況，位置掩碼圖提取可用位置信息，線長熱力圖提供宏塊間粗略的連接關(guān)系，引腳熱力圖提供網(wǎng)絡(luò)引腳的詳細(xì)連接關(guān)系。因此，它們相結(jié)合才能保證線長最短和零重疊。在方案1～3中，線長增加2.70%～32.32%；在方案4中，雖然線長減少60.35%，但是重疊率上升到了79.85%，這種全局布局是無意義的。

b）圖卷積神經(jīng)網(wǎng)絡(luò)通過探索網(wǎng)表的物理意義，用低維向量表示節(jié)點(diǎn)的類型和連接性信息。方案5中，如不嵌入詳細(xì)的網(wǎng)表信息，則線長增加24.94%，重疊率上升為2.45%。

c）重提取神經(jīng)網(wǎng)絡(luò)可以將較淺層的特征直接傳遞到較深層，提高模型對細(xì)節(jié)的捕捉能力和表示能力。在缺乏該網(wǎng)絡(luò)提供的特征融合機(jī)制的情況下（方案6），線長增加13.74%。

4.6 算法對比

圖11展示了本文嘗試使用A2C、PPO、ACKTR和Rainbow DQN算法對本文模型進(jìn)行訓(xùn)練的對比結(jié)果。結(jié)果表明，A2C算法更適合本文設(shè)計(jì)的模型。

5 結(jié)束語

針對數(shù)字芯片全局布局這一組合優(yōu)化問題，提出了基于視覺和強(qiáng)化學(xué)習(xí)的混合方法，設(shè)計(jì)了一套完整的策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)，通過視覺多角度獲取宏塊擺放過程中的狀態(tài)信息，豐富輸入特征，從而提高智能體對動(dòng)作決策的準(zhǔn)確性；設(shè)計(jì)了重提取神經(jīng)網(wǎng)絡(luò)，此特征融合機(jī)制有助于綜合利用不同層級的信息，提升整體全局布局質(zhì)量；引入了圖神經(jīng)網(wǎng)絡(luò)，通過學(xué)習(xí)網(wǎng)表的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)間的關(guān)系，使模型能夠更好地理解電路全局布局的特征和相互作用，從而更準(zhǔn)確地進(jìn)行全局布局決策。實(shí)驗(yàn)證明，本文算法各項(xiàng)指標(biāo)高于目前最先進(jìn)的全局布局算法，為數(shù)字芯片后端設(shè)計(jì)流程中的全局布局提供了高效合理的實(shí)際解決方案。

參考文獻(xiàn)：

［1］Markov I L， Hu Jin， Kim M C. Progress and challenges in VLSI placement research［C］//Proc of IEEE/ACM International Confe－rence on Computer－Aided Design. Piscataway， NJ： IEEE Press， 2012： 275－282.

［2］Rabaey J M. Digital integrated circuits a design perspective［M］.［S.l.］： Prentice－Hall Inc.， 1999.

［3］Zaruba D， Zaporozhets D， Kureichik V. Artificial bee colony algorithm—a novel tool for VLSI placement［C］//Proc of the 1st International Scientific Conference on “Intelligent Information Technologies for Industry”. Cham：Springer， 2016： 433－442.

［4］Cheng Ruoyu， Lyu Xianglong， Li Yang， et al. The policy－gradient placement and generative routing neural networks for chip design［J］.Advances in Neural Information Processing Systems ， 2022，35 ： 26350－26362.

［5］Wang L T， Chang Yaowen， Cheng K T T，et al.Electronic design automation： synthesis， verification， and test［M］. San Francisco，CA：Morgan Kaufmann Publishers， 2009.

［6］Tang Maolin， Yao Xin. A memetic algorithm for VLSI floor planning［J］.IEEE Trans on Systems Man and Cybernetics， Part B（Cybernetics） ， 2007， 37 （1）： 62－69.

［7］Lienig J， Scheible J， Lienig J，et al.Steps in physical design： from netlist generation to layout post processing［M］//Fundamentals of Layout Design for Electronic Circuits. Cham： Springer， 2020： 165－211.

［8］Kahng A B， Lienig J， Markov I L，et al.VLSI physical design： from graph partitioning to timing closure［M］. Berlin： Springer， 2011.

［9］Yan Junchi， Lyu Xianglong， Cheng Ruoyu，et al.Towards machine learning for placement and routing in chip design： a methodological overview［EB/OL］. （2022－02－28）. https：//arxiv.org/abs/2202.13564.

［10］Hochba D S. Approximation algorithms for NP－h(huán)ard problems［J］.ACM SIGACT News，1997，28 （2）： 40－52.

［11］Zhang Hongming， Yu Tianyang. AlphaZero［M］//Deep Reinforcement Learning： Fundamentals， Research and Applications. Berlin： Springer， 2020： 391－415.

［12］Brown T， Mann B， Ryder N，et al.Language models are few－shot learners［J］.Advances in Neural Information Processing Systems ， 2020， 33 ：1877－1901.

［13］Cheng Ruoyu， Yan Junchi. On joint learning for solving placement and routing in chip design［J］.Advances in Neural Information Processing Systems ， 202 34 ： 16508－16519.

［14］Mnih V， Badia A P， Mirza M，et al.Asynchronous methods for deep reinforcement learning［C］//Proc of International Conference on Machine Learning.［S.l.］：PMLR， 2016： 1928－1937.

［15］Kipf T N， Welling M. Semi－supervised classification with graph con－volutional networks［EB/OL］. （2017－02－22）. https：//arxiv.org/abs/1609.02907.

［16］Nam G J， Alpert C J， Villarrubia P，et al.The ISPD2005 placement contest and benchmark suite［C］//Proc of International Symposium on Physical Design. New York：ACM Press， 2005： 216－220.

［17］Lu Jingwei， Chen Pengwen， Chang C C，et al.ePlace： electrostatics－based placement using fast Fourier transform and Nesterov’s method［J］.ACM Trans on Design Automation of Electronic Systems，2015， 20 （2）： 1－34.

［18］Cheng C K， Kahng A B， Kang I，et al.RePlAce： advancing solution quality and routability validation in global placement［J］.IEEE Trans on Computer－Aided Design of Integrated Circuits and Systems ， 2018， 38 （9）： 1717－1730.

［19］Lin Yibo， Dhar S， Li Wuxi，et al.DREAMPlace： deep learning toolkit－enabled GPU acceleration for modern VLSI placement［C］//Proc of the 56th Annual Design Automation Conference. Piscataway， NJ： IEEE Press， 2019： 1－6.

［20］Mirhoseini A，Goldie A，Yazgan M， et al.A graph placement metho－dology for fast chip design［J］.Nature ， 202 594 （7862）： 207－212.

［21］Zhao Hang， Zhu Chenyang， Xu Xin，et al.Learning practically feasible policies for online 3D bin packing［J］.Science China Information Sciences ， 2022， 65 （1）： 112105.

［22］Kingma D P， Ba J. Adam： a method for stochastic optimization［EB/OL］. （2017－01－30）. https：//arxiv.org/abs/1412.6980.

收稿日期：2023－08－16；修回日期：2023－10－01基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（62105196）

作者簡介：徐樊豐（1999—），男，上海人，碩士研究生，CCF會員，主要研究方向?yàn)閿?shù)字芯片全局布局布線、深度強(qiáng)化學(xué)習(xí)；仝明磊（1976—），男（通信作者），山東菏澤人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)镋DA智能化、深度學(xué)習(xí)、計(jì)算機(jī)視覺（tongminglei@shiep.edu.cn）．