一種基于共軛次梯度算法的非光滑布圖規(guī)劃方法

摘 要：針對(duì)只有硬模塊的布圖規(guī)劃問題，通常將其構(gòu)建成組合優(yōu)化模型，但求解過程時(shí)間成本高。為提高求解效率，提出了一種基于非光滑解析數(shù)學(xué)規(guī)劃的布圖規(guī)劃算法?；诓紙D中器件的坐標(biāo)表示，構(gòu)建了一個(gè)泛化的非光滑解析數(shù)學(xué)規(guī)劃模型，將不同場(chǎng)景下的布圖規(guī)劃問題的不同優(yōu)化階段處理為該泛化模型的特例，并利用共軛次梯度算法（conjugate sub-gradient algorithm，CSA）對(duì)其進(jìn)行求解。針對(duì)固定輪廓布圖規(guī)劃問題，通過統(tǒng)一框架下的全局布圖規(guī)劃、合法化、局部?jī)?yōu)化三個(gè)階段，實(shí)現(xiàn)了在固定輪廓約束下的線長(zhǎng)優(yōu)化。針對(duì)無固定輪廓約束問題，提出了帶黃金分割策略的共軛次梯度算法（conjugate sub-gradient algorithm with golden section strategy，CSA_GSS），利用黃金分割策略縮小固定輪廓的面積，達(dá)到面積和線長(zhǎng)雙優(yōu)化的效果。實(shí)驗(yàn)在GSRC測(cè)試電路上與基于B*-樹表示的布圖規(guī)劃算法進(jìn)行比較，該算法對(duì)于大規(guī)模電路在線長(zhǎng)和時(shí)間方面均占據(jù)優(yōu)勢(shì)。實(shí)驗(yàn)結(jié)果表明，該算法能以更低的時(shí)間復(fù)雜度獲得更優(yōu)的線長(zhǎng)。

關(guān)鍵詞：大規(guī)模集成電路；布圖規(guī)劃；非光滑優(yōu)化；固定輪廓；共軛次梯度法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）09-026-2751-07

doi：10.19734/j.issn.1001-3695.2023.12.0628

Non-smooth floorplanning method based on conjugate sub-gradient algorithm

Sun Jian1a，Xu Ning1b，Wu Jian1b，Zhu Zhanyang1b，Chen Yu1a，Hu Jianguo2

（1.a.School of Science，b.School of Information Engineering，Wuhan University of Technology，Wuhan 430070，China;2.Shenzhen Research Institute，Sun Yat-Sen University，Shenzhen Guangdong 528406，China）

Abstract：Aiming at the floorplanning problem with only hard modules，it is usually constructed as a combinatorial optimization model，but the time cost of solving process is high.In order to improve the solving efficiency，this paper proposed a floorplanning algorithm based on non-smooth analytic mathematical programming.Based on the coordinate representation of mo-dules，this paper established a non-smooth mathematical programming model，which was a generalization of the optimization models corresponding to various optimization stages of different cases that were solved by the conjugate sub-gradient algorithm（CSA）.Aiming at the fixed-outline floorplanning problem，this paper achieved wirelength optimization under fixed-outline constraint through the general framework consisted of three stages：global floorplanning，legalization and local optimization.To address the case without fixed-outline constraint，this paper proposed a conjugate sub-gradient algorithm with golden section stra-tegy（CSA_GSS）.The algorithm adopted golden section strategy to reduce the area of the fixed-outline and to achieve the dual effect of both area and wirelength optimization.Compared with floorplanning algorithm based on B*-tree on GSRC test circuit，the proposed algorithm had advantages in terms of wirelength and time for large-scale circuits.Experimental results show that the algorithm can obtain better wirelength with lower time complexity.

Key words：VLSI;floorplanning;non-smooth optimization;fixed-outline;conjugate sub-gradient algorithm

0 引言

布圖規(guī)劃是超大規(guī)模集成電路（very large-scale integration circuit，VLSI）物理設(shè)計(jì)中的重要步驟，布圖結(jié)果對(duì)VLSI芯片的性能具有重要影響［1］。然而，VLSI布圖規(guī)劃需要在滿足約束條件的情況下考慮線長(zhǎng)、面積等多個(gè)優(yōu)化目標(biāo)來實(shí)現(xiàn)模塊的最佳放置，是一個(gè)具有復(fù)雜約束的多目標(biāo)優(yōu)化問題［2］。隨著集成電路技術(shù)的發(fā)展，VLSI布圖規(guī)劃場(chǎng)景越來越復(fù)雜，為高性能布圖規(guī)劃算法的設(shè)計(jì)帶來巨大的挑戰(zhàn)。

根據(jù)所建立的布圖規(guī)劃數(shù)學(xué)規(guī)劃模型，可將布圖規(guī)劃算法分為基于組合優(yōu)化模型的布圖規(guī)劃算法（floorplanning algorithm based on a combinatorial optimization model，F(xiàn)A-COM）和基于解析優(yōu)化模型的布圖規(guī)劃算法（floorplanning algorithm based on an analytical optimization model，F(xiàn)A-AOM）兩類。采用特定的布圖編碼刻畫布圖模塊之間的相對(duì)位置關(guān)系，F(xiàn)A-COM利用啟發(fā)式算法或元啟發(fā)式算法來求解布圖規(guī)劃的大規(guī)模組合優(yōu)化模型，進(jìn)而得到優(yōu)化的布圖結(jié)果［3～6］；雖然對(duì)相對(duì)位置關(guān)系的解碼結(jié)果能夠自然地滿足模塊的互不重疊約束，但算法的收斂速度會(huì)隨著問題規(guī)模的增大而急劇下降，難以滿足大規(guī)模布圖規(guī)劃的收斂性能需求。為了提高FA-COM算法的優(yōu)化效率，可以通過聚類或分區(qū)策略將問題預(yù)劃分若干個(gè)小規(guī)模布圖問題，采用分而治之的思想來實(shí)現(xiàn)對(duì)大規(guī)模的布圖規(guī)劃問題的快速求解［7，8］；然而，對(duì)小規(guī)模問題的局部?jī)?yōu)化難以對(duì)原問題的解空間進(jìn)行高效的全局探索，無法保證布圖規(guī)劃算法的全局收斂性。

受到VLSI全局布局的解析式優(yōu)化算法的啟發(fā)，F(xiàn)A-AOM算法采用模塊的絕對(duì)坐標(biāo)表示布圖規(guī)劃，并利用解析數(shù)學(xué)優(yōu)化算法求解布圖規(guī)劃的解析數(shù)學(xué)規(guī)劃模型，具有比FA-COM算法更低的時(shí)間復(fù)雜度［9～11］。因此，F(xiàn)A-AOM通常分成兩個(gè)階段：首先，在全局布圖階段對(duì)布圖規(guī)劃的解析優(yōu)化模型進(jìn)行求解，得到違背部分約束（例如部分模塊重疊或越界）但綜合指標(biāo)最優(yōu)的階段性布圖結(jié)果；然后，利用合法化技術(shù)消除全局布圖結(jié)果中的約束違背，得到合法的優(yōu)化布圖方案。對(duì)于包括軟模塊的大規(guī)模固定輪廓布圖規(guī)劃問題，文獻(xiàn)［10］采用基于靜電場(chǎng)建模的泊松方程來刻畫布圖規(guī)劃問題，并采用解析優(yōu)化方法對(duì)勢(shì)函數(shù)進(jìn)行優(yōu)化以得到全局布圖結(jié)果；然后，構(gòu)建水平約束圖和垂直約束圖消除重疊，生成滿足固定輪廓約束的自動(dòng)布圖結(jié)果。

為了實(shí)現(xiàn)基于導(dǎo)數(shù)信息的快速解析優(yōu)化，已有的FA-AOM需要對(duì)模塊重疊、半周長(zhǎng)等非光滑函數(shù)進(jìn)行光滑近似，從而得到光滑的優(yōu)化目標(biāo)函數(shù)和約束條件。然而，F(xiàn)A-AOM所采用的光滑近似函數(shù)非常復(fù)雜，對(duì)函數(shù)值和導(dǎo)數(shù)的計(jì)算復(fù)雜度比較高；同時(shí)，近似得到光滑目標(biāo)函數(shù)與原目標(biāo)函數(shù)的數(shù)學(xué)性質(zhì)不盡相同，可能得到與原問題具有不同最優(yōu)解的近似優(yōu)化模型；另外，F(xiàn)A-AOM常采用基于水平/垂直約束圖的合法化策略消除模塊重疊和越界，進(jìn)一步增加了算法的時(shí)間復(fù)雜度。鑒于此，本文構(gòu)建了布圖規(guī)劃的非光滑解析數(shù)學(xué)規(guī)劃模型，并利用共軛次梯度算法（conjugate sub-gradient algorithm，CSA）［12］來實(shí)現(xiàn)全局布圖和合法化以得到優(yōu)化的布圖規(guī)劃結(jié)果。具體地，提出了全局布圖和合法化的解析數(shù)學(xué)規(guī)劃模型并利用CSA進(jìn)行求解，得到了固定輪廓約束下對(duì)線長(zhǎng)進(jìn)行優(yōu)化的布圖規(guī)劃算法CSA_FC（conjugate sub-gradient algorithm with fixed-outline constraints）和無固定輪廓約束時(shí)對(duì)面積和線長(zhǎng)進(jìn)行優(yōu)化的布圖規(guī)劃算法CSA_GSS（conjugate sub-gradient algorithm with golden section strategy）。

1 布圖規(guī)劃問題的非光滑解析數(shù)學(xué)規(guī)劃模型

在VLSI布圖規(guī)劃問題中，需要在所有矩形模塊互不重疊的前提下將矩形模塊放置于平面布圖區(qū)域內(nèi)，并對(duì)影響VLSI性能的指標(biāo)如線長(zhǎng)、面積、模塊工作溫度等進(jìn)行優(yōu)化。記V={v1，v2，…，vn}為矩形模塊的集合，E={e1，e2，…，em}為線網(wǎng)集合。模塊vi的中心坐標(biāo)用（xi，yi）表示，寬與高分別用wi和hi表示，所有模塊的x-坐標(biāo)和y-坐標(biāo)向量記作x=（x1，…，xn），y=（y1，…，yn）。

本文重點(diǎn)研究?jī)深惤?jīng)典的布圖規(guī)劃問題：第一類是給定布圖區(qū)域?qū)€長(zhǎng)指標(biāo)進(jìn)行優(yōu)化的固定輪廓布圖規(guī)劃問題，第二類是同時(shí)對(duì)線長(zhǎng)和面積兩個(gè)指標(biāo)進(jìn)行優(yōu)化的無固定輪廓約束的布圖規(guī)劃問題?；诖耍梢越LSI布圖規(guī)劃的通用約束優(yōu)化模型

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

為了驗(yàn)證本文的算法的性能，在著名的測(cè)試基準(zhǔn)GSRC上進(jìn)行了實(shí)驗(yàn)。對(duì)于所有測(cè)試電路，I/O焊盤固定在給定坐標(biāo)處，所有電路的模塊都是硬模塊。本文的所有實(shí)驗(yàn)采用基于Windows操作系統(tǒng)的C++語言程序，處理器為AMD Ryzen 7 5800H，主頻3.2 GHz，內(nèi)存為16 GB。

3.1 共軛次梯度算法的收斂性能分析

本文在全局布圖規(guī)劃階段以及合法化階段均采用CSA作為優(yōu)化引擎，為了解CSA對(duì)布圖規(guī)劃數(shù)學(xué)模型的優(yōu)化效率，以GSRC測(cè)試集中的n100電路為例，分別研究了全局布圖規(guī)劃階段和合法化階段CSA的優(yōu)化性能，相應(yīng)目標(biāo)函數(shù)值隨迭代次數(shù)變化的折線圖如圖2所示。

圖2（a）為CSA在全局布圖階段的迭代過程，令u=（x，y），黑線、紅線、藍(lán)線、綠線分別代表目標(biāo)函數(shù)f1（u）、半周長(zhǎng)線長(zhǎng)HPWL、重疊項(xiàng)D（u）以及出界項(xiàng)B（u）的收斂曲線。在全局布圖的初始階段，算法具有較好的收斂效率，目標(biāo)函數(shù)f1（u）迅速降低;同時(shí)，由于重疊項(xiàng)系數(shù)λ較小，算法朝著線長(zhǎng)優(yōu)化的目標(biāo)迭代，HPWL快速下降而D（u）迅速增加。在迭代過程中，每50步迭代增加λ的值，在保持線長(zhǎng)優(yōu)化的同時(shí)加大對(duì)重疊的優(yōu)化，D（u）指標(biāo)迅速下降，而f1（u）與HPWL緩慢上升，最終趨于穩(wěn)定。由于目標(biāo)函數(shù)f1（u）綜合了HPWL、D（u）和B（u）三個(gè)指標(biāo)，在全局布圖階段，D（u）和B（u）指標(biāo)難以同時(shí)降為0，需要對(duì)結(jié)果進(jìn)行合法化處理。

圖2（b）為合法化階段的迭代過程，青線代表目標(biāo)函數(shù)（u）。函數(shù)值呈波動(dòng)下降。迭代初期步長(zhǎng)較大，函數(shù)值波動(dòng)幅度大，步長(zhǎng)隨迭代過程下降，函數(shù)值波動(dòng)幅度減小，最后趨近于0。

由于基于次梯度的CSA不是目標(biāo)下降算法，其局部收斂性能要弱于梯度下降類算法，優(yōu)化的目標(biāo)函數(shù)f1（u）在全局布局的中后期呈現(xiàn)出略微振蕩上升的趨勢(shì)，而合法化階段的目標(biāo)函數(shù)（u）則呈現(xiàn)振蕩下降的趨勢(shì)。然而，CSA具有更好的全局收斂性能，依照2.1.2節(jié)所提出的步長(zhǎng)選取策略，CSA能夠很好地求解本文所提出的布圖規(guī)劃模型，得到合法的布圖規(guī)劃結(jié)果。

3.2 固定輪廓約束的線長(zhǎng)優(yōu)化

根據(jù)給定的縱橫比R，固定輪廓的寬W*與高H*采用如下計(jì)算方法［16］：

γ=S（x，y）-AA×100%

本文選擇的開源布圖規(guī)劃器Parquet-4.5［17］與CSA_FC進(jìn)行比較。其中，Parquet-4.5采用基于B*樹布圖表示方法，通過模擬退火算法來對(duì)布圖規(guī)劃的組合優(yōu)化模型進(jìn)行求解，模型和算法參數(shù)均采用默認(rèn)設(shè)置。實(shí)驗(yàn)考慮縱橫比R為1，1.5，2，空白率γ為15%，所有電路的最大運(yùn)行次數(shù)tmax均為20，樣本數(shù)p均為5。對(duì)于不同的縱橫比設(shè)置（R），每組實(shí)驗(yàn)獨(dú)立運(yùn)行十次的平均半周長(zhǎng)（HPWL）、CPU時(shí)間（CPU）和成功率（SR）如表1所示。

實(shí)驗(yàn)結(jié)果表明，對(duì)于小規(guī)模測(cè)試問題（n10，n30），基于解析布局表達(dá)的CSA_FC算法的算法運(yùn)行時(shí)間和布圖成功率略差于基于B*樹表示的開源布圖器Parquet-4.5，而對(duì)于規(guī)模較大的布圖規(guī)劃問題（n50-n300），CSA_FC的CPU時(shí)間低于Parquet-4.5。由于B*-樹模型將布圖規(guī)劃問題轉(zhuǎn)換為一個(gè)組合優(yōu)化問題，當(dāng)模塊數(shù)量較小時(shí)，模擬退火算法能夠高效地求解該組合優(yōu)化問題，從而具有更高的布圖規(guī)劃成功率和更短程序運(yùn)行時(shí)間。隨著問題規(guī)模的增大，Parquet-4.5所求解的組合優(yōu)化模型的解呈指數(shù)級(jí)增長(zhǎng)，導(dǎo)致模擬退火算法的求解效率迅速降低；而基于次梯度的迭代機(jī)制使得CSA_FC能夠更有效地搜索布圖區(qū)域，從而具有更好的布圖優(yōu)化效率。

在固定輪廓的布圖實(shí)例中，優(yōu)化模型式（3）采用了重疊面積的平方根作為重疊程度衡量指標(biāo)，消除了重疊面積和線長(zhǎng)的量綱差異；同時(shí)，CSA_FC算法的迭代過程采用了先全局布圖再合法化的優(yōu)化機(jī)制，從而能夠更好地對(duì)線長(zhǎng)（HPWL）進(jìn)行優(yōu)化，對(duì)所有的測(cè)試實(shí)例上均能夠得到更好的線長(zhǎng)優(yōu)化結(jié)果。

3.3 無固定輪廓約束的線長(zhǎng)和面積優(yōu)化

對(duì)于無固定輪廓約束的布圖規(guī)劃問題，使用CSA_GSS對(duì)線長(zhǎng)和面積進(jìn)行優(yōu)化，本文進(jìn)行兩組實(shí)驗(yàn)，首先將它與Parquet-4.5以及HSA（hybrid simulated annealing algorithm）［18］進(jìn)行比較。在CSA_GSS中，ε=0.2%，所有電路的最大運(yùn)行次數(shù)tmax均為20，樣本數(shù)p均為5。HSA采用文獻(xiàn)［18］中的參數(shù)設(shè)置。

表1中的實(shí)驗(yàn)結(jié)果表明，在縱橫比R=1時(shí)布圖結(jié)果均能夠得到最好的線長(zhǎng)優(yōu)化結(jié)果，縱橫比越大，HPWL的值越大。對(duì)多數(shù)例子而言，CPU時(shí)間也隨R的增大而增大。因此在無固定輪廓約束的布圖實(shí)例中，布圖結(jié)果的縱橫比取值為R=1。對(duì)于GSRC中的每個(gè)例子，算法運(yùn)行十次的線長(zhǎng)（HPWL）、面積（S）和運(yùn)行時(shí)間（CPU）的平均值如表2所示。

結(jié)合特殊的種群初始化策略和個(gè)體生成機(jī)制，HAS能夠得到比Parquet-4.5更好的線長(zhǎng)優(yōu)化效果，對(duì)于小規(guī)模電路（n10，n30，n50）也能得到更小的布圖面積，但布圖效率隨著測(cè)試電路（n100，n200，n300）模塊數(shù)的增大而迅速降低，算法運(yùn)行時(shí)間急劇增加。對(duì)于無邊框約束的布圖規(guī)劃場(chǎng)景，CSA_GSS同樣能夠得到最佳的線長(zhǎng)優(yōu)化結(jié)果，隨著電路規(guī)模的增大，CSA_GSS在CPU運(yùn)行時(shí)間的增長(zhǎng)幅度最小，表明基于共軛次梯度法的CSA_GSS更適用于更大規(guī)模布圖規(guī)劃場(chǎng)景。同時(shí)，GSA_GSS算法布圖面積的優(yōu)化結(jié)果略差于基于B*樹和模擬退火算法的Parquet-4.5以及HAS。

文獻(xiàn)［19］將強(qiáng)化學(xué)習(xí)與遺傳算法相結(jié)合，提出了GA+RL，該算法同樣采用B*-樹作為布圖表示，利用遺傳算法進(jìn)行全局搜索，通過強(qiáng)化學(xué)習(xí)優(yōu)化局部搜索策略，并與傳統(tǒng)的GA+SA（hybrid genetic algorithm and simulated annealing）進(jìn)行比較。對(duì)于線長(zhǎng)計(jì)算，這里僅考慮模塊之間的互連關(guān)系。實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)，CSA_GSS的參數(shù)設(shè)置與上文一致。對(duì)于GSRC中的每個(gè)例子，算法運(yùn)行十次的線長(zhǎng)（HPWL）、面積（S）的平均值如表3所示。

對(duì)于n200和n300測(cè)試?yán)樱珻SA_GSS在面積和線長(zhǎng)方面均要優(yōu)于GA+SA和GA+RL。本文算法在大規(guī)模問題上具有優(yōu)勢(shì)，但對(duì)于小規(guī)模問題，兩種比較算法均優(yōu)于CSA_GSS。此外，結(jié)合強(qiáng)化學(xué)習(xí)策略的遺傳算法相對(duì)于傳統(tǒng)的GA+SA算法，整體上有著突出表現(xiàn)，具有研究潛力。圖3給出了CSA_GSS對(duì)n100、n200、n300電路的一次實(shí)驗(yàn)布圖結(jié)果。

4 結(jié)束語

針對(duì)只有硬模塊的布圖規(guī)劃問題，本文建立了一種基于非光滑解析數(shù)學(xué)規(guī)劃的布圖規(guī)劃模型，利用共軛次梯度法來求解帶固定輪廓和無固定輪廓的布圖規(guī)劃問題，提出了一種基于非光滑優(yōu)化的布圖規(guī)劃算法框架。該方法克服了基于組合優(yōu)化模型的布圖算法時(shí)間復(fù)雜度高的缺點(diǎn)，克服了基于解析數(shù)學(xué)規(guī)劃模型的布圖算法難以實(shí)現(xiàn)布圖合法化的不足。實(shí)驗(yàn)結(jié)果表明，在只有硬模塊的布圖規(guī)劃場(chǎng)景下，該布圖規(guī)劃算法框架能夠通過統(tǒng)一的優(yōu)化框架實(shí)現(xiàn)全局布圖規(guī)劃以及布圖規(guī)劃的合法化，能夠更好地優(yōu)化布圖結(jié)果的線長(zhǎng)。與B*樹的開源軟件Parquet-4.5和HAS算法相比，本文提出的基于非光滑解析優(yōu)化的算法具有更低的時(shí)間復(fù)雜度，運(yùn)行時(shí)間隨著問題規(guī)模的增加速度遠(yuǎn)低于Parquet-4.5和HAS，有望更好地推廣應(yīng)用到超大規(guī)模的硬模塊布圖規(guī)劃和布局問題中。

參考文獻(xiàn)：

［1］Srinivasan B，Venkatesan R，Aljafari B，et al.A novel multicriteria optimization technique for VLSI floorplanning based on hybridized firefly and ant colony systems［J］.IEEE Access，2023，11：14677-14692.

［2］Weng Yifan，Chen Zhen，Chen Jianli，et al.A modified multi-objective simulated annealing algorithm for fixed-outline floorplanning［C］//Proc of IEEE International Conference on Automation，Electronics and Electrical Engineering.Piscataway，NJ：IEEE Press，2018：35-39.

［3］Chen Jianli，Zhu Wenxing.A hybrid genetic algorithm for VLSI floorplanning［C］//Proc of IEEE International Conference on Intelligent Computing and Intelligent Systems.Piscataway，NJ：IEEE Press，2010：128-132.

［4］杜世民，夏銀水，儲(chǔ)著飛，等.面向軟模塊的穩(wěn)定固定邊框布圖規(guī)劃算法［J］.電子與信息學(xué)報(bào)，2014，36（5）：1258-1265.（Du Shimin，Xia Yinshui，Chu Zhufei，et al.A stable fixed-outline floorplanning algorithm for soft module［J］.Journal of Electronics & Information Technology，2014，36（5）：1258-1265.）

［5］Zou Dexuan，Wang Gaige，Pan Gai，et al.A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints［J］.Frontiers of Information Technology & Electronic Engineering，2016，17（11）：1228-1244.

［6］Ye Yin，Yin Xi，Chen Zhenyi，et al.A novel method on discrete particle swarm optimization for fixed-outline floorplanning［C］//Proc of IEEE International Conference on Artificial Intelligence and Information Systems.Piscataway，NJ：IEEE Press，2020：591-595.

［7］Yan J Z，Chu C.Defer：deferred decision making enabled fixed-outline floorplanning algorithm［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2010，29（3）：367-381.

［8］Ji Pengli，He Kun，Wang Zhengli，et al.A quasi-newton-based floorplanner for fixed-outline floorplanning［J］.Computers & Operations Research，2021，129：105225.

［9］Lin Jaiming，Hung Zhixiong.UFO：unified convex optimization algorithms for fixed-outline floorplanning considering pre-placed modules［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2011，30（7）：1034-1044.

［10］Li Ximeng，Peng Keyu，Huang Fuxing，et al.PeF：Poisson’s equation based large-scale fixed-outline floorplanning［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2023，42（6）：2002-2015.

［11］黃志鵬，李興權(quán)，朱文興.超大規(guī)模集成電路布局的優(yōu)化模型與算法［J］.運(yùn)籌學(xué)學(xué)報(bào)，2021，25（3）：15-36.（Huang Zhipeng，Li Xingquan，Zhu Wenxing.Optimization models and algorithms for placement of very large scale integrated circuits［J］.Operations Research Trans，2021，25（3）：15-36.）

［12］Zhu Wenxing，Chen Jianli，Peng Zheng，et al.Nonsmooth optimization method for VLSI global placement［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2015，34（4）：642-655.

［13］Chen Jianli，Zhu Wenxing.An analytical placer for VLSI standard cell placement［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2012，31（8）：1208-1221.

［14］劉浩洋，戶將，李勇鋒，等.最優(yōu)化：建模、算法與理論［M］.北京：高等教育出版社，2020：60-66.（Liu Haoyang，Hu Jiang，Li Yongfeng，et al.Optimization：modeling，algorithm and theory［M］.Beijing：Higher Education Press，2020：60-66.）

［15］徐杰，魯海燕，趙金金，等.拉丁超立方抽樣的自適應(yīng)高斯小孔成像蝴蝶優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（9）：2701-2708，2751.（Xu Jie，Lu Haiyan，Zhao Jinjin，et al.Self-adaptive Gaussian keyhole imaging butterfly optimization algorithm based on Latin hypercube sampling［J］.Application Research of Computers，2022，39（9）：2701-2708，2751.）

［16］Zou Dexuan，Hao Guosheng，Pan Gai，et al.An improved simulated annealing algorithm and area model for the fixed-outline floorplanning with hard modules［C］//Proc of the 3rd International Symposium on Computational and Business Intelligence.Piscataway，NJ：IEEE Press，2015：21-25.

［17］Roy J A，Adya S N，Papa D A，et al.Min-cut floorplacement［J］.IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems，2006，25（7）：1313-1326.

［18］Chen Jianli，Zhu Wenxing and Ali M.M，et al.A hybrid simulated annealing algorithm for nonslicing VLSI floorplanning［J］.IEEE Trans on Systems，Man，and Cybernetics，Part C（Applications and Reviews），2011，41（4）：544-553.

［19］Liu Ke，Gu Jian and Zhu Ziran.A hybrid reinforcement learning and genetic algorithm for VLSI floorplanning［C］//Proc of the 15th International Conference on Machine Learning and Computing.New York：ACM Press，2023：412-418.

收稿日期：2023-12-06

修回日期：2024-02-11

基金項(xiàng)目：深圳科技計(jì)劃資助項(xiàng)目（JCYJ20220818102002005）；科技部科技創(chuàng)新2030—“新一代人工智能”重大項(xiàng)目（2021ZD0114600）

作者簡(jiǎn)介：孫?。?999—），男，碩士，CCF會(huì)員，主要研究方向?yàn)閮?yōu)化算法在電子設(shè)計(jì)自動(dòng)化中的應(yīng)用；徐寧（1968—），男，教授，博導(dǎo)，博士，主要研究方向?yàn)殡娮釉O(shè)計(jì)自動(dòng)化、先進(jìn)封裝EDA、圖像處理、人工智能；吳建（1999—），男，碩士研究生，主要研究方向?yàn)殡娮釉O(shè)計(jì)自動(dòng)化；朱展洋（2001—），男，碩士研究生，主要研究方向?yàn)殡娮釉O(shè)計(jì)自動(dòng)化；陳彧（1981—），男（通信作者），副教授，碩導(dǎo)，博士，主要研究方向?yàn)橹悄軆?yōu)化算法、電子設(shè)計(jì)自動(dòng)化（ychen@whut.edu.cn）；胡建國(guó)（1977—），男，研究員，博導(dǎo)，博士，主要研究方向?yàn)楦叨思呻娐吩O(shè)計(jì)、電子設(shè)計(jì)自動(dòng)化、物聯(lián)網(wǎng)、人工智能.