摘要: 綜述超大規(guī)模集成電路(VLSI)布圖規(guī)劃方法, 探討布圖規(guī)劃在集成電路設(shè)計中的重要性, 以及其對芯片面積、 互連線長和設(shè)計周期的影響. 首先, 回顧集成電路技
術(shù)的發(fā)展歷程, 強調(diào)布圖規(guī)劃在確定模塊位置、 尺寸和旋轉(zhuǎn)角度中的作用. 其次, 詳細介紹4類主要的VLSI布圖規(guī)劃方法: 直觀構(gòu)造方法、 分析法、 迭代
法和基于機器學習的方法. 再次, 討論兩個VLSI 設(shè)計領(lǐng)域中常用的基準數(shù)據(jù)集MCNC和GSRC對測試和評估布圖設(shè)計方法的重要性. 最后, 總結(jié)布圖規(guī)劃領(lǐng)域的研究進展, 并指出未來的研究方向.
關(guān)鍵詞: 超大規(guī)模集成電路; 布圖規(guī)劃; 布局; 構(gòu)造法; 分析法; 迭代法; 機器學習方法
中圖分類號: TP391; TN47" 文獻標志碼: A" 文章編號: 1671-5489(2025)01-0139-12
Research Review of Floorplanning Methodsfor Very Large Scale Integration
SHI Zihui, OUYANG Dantong, ZHANG Liming
(College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering
of Ministry of Education,Jilin University, Changchun 130012, China)
收稿日期: 2024-12-05.
第一作者簡介: 史梓慧(2001—), 女, 漢族, 碩士研究生, 從事布圖規(guī)劃的研究, E-mail: shizh23@ mails.jlu.edu.cn.
通信作者簡介: 歐陽丹彤(1968—), 女, 滿族, 博士, 教授, 博士生導師, 從事基于模型診斷和語義網(wǎng)的研究, E-mail: ouyd@jlu.edu.cn.
基金項目: 國家自然科學基金(批準號: 62076108; 61872159; 61672261).
Abstract: We review" the" floorplanning methods for very large scale integration (VLSI), explore the significance of floorplanning in integrat
ed circuit design, and its impact on chip area, interconnect length, and design cycle. Firstly, we" review the development history of integrated circuit technology,
emphasize the role of floorplanning in determining the position, size, and rotation angles of modules. Secondly, we provide a detailed introduction to four main c
ategories of VLSI floorplanning methods: intuitive construction methods, analytical methods, iterative methods and machine learning methods.
Thirdly, we discuss two commonly used" MCNC and GSRC benchmark datasets, which are crucial for testing and evaluating floorplanning methods in the VLSI design field.
Finally, we summarize the research progress in the field of floorplanning and point out future research directions.
Keywords: very large scale integration; floorplanning; placement; construction method; analysis method; iterative method; machine learning method
集成電路技術(shù)的發(fā)展極大縮小了電子器件的尺寸, 降低了功耗, 提升了性能, 并簡化了器件間的連接. 在集成電路早期研究中, 主要采用小規(guī)模集成電路(SSI). 隨著集成電路技術(shù)的進步和制造工藝的改進, 集成度顯著
提升, 從早期的小規(guī)模集成電路逐步過渡到中規(guī)模集成電路(MSI)和大規(guī)模集成電路(LSI), 最終發(fā)展至超大規(guī)模集成電路(VLSI)[1]. VLSI技術(shù)使單個芯片上能集成數(shù)百萬個晶體管甚至更多, 極大增強了
電子設(shè)備的性能和復雜性. 這種集成度的飛躍不僅極大推動了計算機和電子設(shè)備性能的顯著提升, 也加速了信息技術(shù)的發(fā)展, 為現(xiàn)代電子工程和計算機科學的進步奠定了堅實的基礎(chǔ).
布圖規(guī)劃是集成電路設(shè)計中的重要環(huán)節(jié)之一, 其目的是確定模塊在芯片版圖中的位置、 尺寸和旋轉(zhuǎn)角度, 從而生成一個合理的布圖, 最小化芯片的面積和模塊間的互連線長
[2]. 一個好的布圖可提升芯片的質(zhì)量, 還能縮短芯片的設(shè)計周期; 而一個效率高、 效果好的布圖規(guī)劃算法, 可降低芯片的設(shè)計成本, 提高生產(chǎn)效益, 推動VLSI和電子設(shè)計自動化(EDA)相關(guān)產(chǎn)業(yè)發(fā)展.
從計算角度, 布圖規(guī)劃是一個NP-難組合優(yōu)化問題[3]. 目前, 超大規(guī)模集成電路的布圖規(guī)劃和布局問題主要有4類方法: 1) 直觀構(gòu)造方法, 這類算法
是使用分而治之策略的經(jīng)典布圖算法; 2) 分析方法, 將布圖和布局問題轉(zhuǎn)化為數(shù)學規(guī)劃問題再求解; 3) 迭代法; 4) 基于機器學習的方法. 在超大規(guī)模集成電路
布圖規(guī)劃領(lǐng)域, 迭代方法因其在尋找最優(yōu)解過程中的高效性而受到廣泛關(guān)注, 其通常結(jié)合元啟發(fā)式策略, 如模擬退火、 粒子群優(yōu)化和遺傳算法等, 可在巨大的搜索空間中探索高質(zhì)
量的解決方案. 而基于學習的方法以其速度快、 泛化能力強等優(yōu)勢, 同樣在該領(lǐng)域展現(xiàn)出巨大的潛力.
1 基于構(gòu)造的布圖規(guī)劃方法
在集成電路設(shè)計問題中, 構(gòu)造法以其簡單直觀的特性成為經(jīng)典方法之一. 該類算法通常采用分而治之的策略, 通過直接的啟發(fā)式規(guī)則或遞歸式分割生成初始布局. 盡管構(gòu)造算法在實現(xiàn)
效率和初步布局生成方面性能優(yōu)異, 但也存在局限性, 例如缺乏全局視野和深度優(yōu)化能力. 因此, 許多研究在構(gòu)造算法的基礎(chǔ)上進行改進, 以提高布局效果和適應(yīng)性. 下面介紹
幾種典型的構(gòu)造算法, 包括Bottom-Left(BL)[4]及其改進算法Bottom-Left-Fill(BLF)[5]、 Bottom-Left-Decreasing(BLD)[6]和BLD*[7],
以及基于角點占據(jù)的COA算法, 并分析其特點、 應(yīng)用場景及局限性.
1.1 BL布圖規(guī)劃算法
BL算法由Baker等[4]提出, 該算法將每個矩形物體盡可能地移動到左下角位置, 具有簡單直觀、 易實現(xiàn)、 執(zhí)行速度較快等特點. 通過改變輸入列表順序, 可顯著影響算法的性能. 例如, 按寬度遞減順序排列矩形可顯
著改善包裝效果, 而按寬度遞增排序方式則會導致效果不佳. 該算法缺乏全局視野, 無法有效優(yōu)化復雜目標. 對某些隨機順序的矩形排列性能較差, 無法保證生成的解達到全局最優(yōu), 適用于初始布局生成.
1.2 BLF布圖規(guī)劃算法
BLF算法[5]在BL算法的基礎(chǔ)上進行了改進, 不僅將矩形物體移向左下角, 還嘗試填補已放置物體周圍的空白區(qū)域. 與BL算法相比, 能更有效地填補
空隙, 從而實現(xiàn)更密集的填充. 該算法的計算成本比BL算法高. 但BLF算法能更有效地利用空間, 因此在需要高效材料利用和精確布局的應(yīng)用中有一定價值.
1.3 BLD和BLD*布圖規(guī)劃算法
BLD算法[6]是一種用于二維矩形包裝問題的啟發(fā)式算法. 該算法先將矩形按高度、 寬度、 面積和周長的降序進行排序, 然后嘗試將每
個矩形放置在當前可用的最底部和最左側(cè)位置. 這種方法通常返回4種排序中的最優(yōu)包裝結(jié)果. 在電子設(shè)計自動化中, 矩形打包用于布圖規(guī)劃, 目的是最小化芯片面積, 同時減少布線
長度. 盡管BLD算法在某些情況下表現(xiàn)良好, 但它在隨機排序的場景中性能通常不佳.
BLD*算法[7]是BLD算法的一種隨機搜索改進版, 引入了隨機擾動原始排序的概念. 使用隨機擾動排序法從BLD的固定排序中生成排列, 并評估其性能. 通過隨機
擾動擴展搜索范圍, 有效避免陷入局部最優(yōu), 可在較短時間內(nèi)顯著提高打包效果. 相比傳統(tǒng)的BLD算法, BLD*算法在精度和靈活性上都有顯著提升.
BLD*算法雖然在優(yōu)化問題中有一定的優(yōu)勢, 但其局限性也不容忽視. 首先, 由于需要多次嘗試隨機擾動排序, 該算法的計算復雜度顯著提高, 導致在處理大規(guī)模數(shù)據(jù)集時產(chǎn)
生較高的時間成本. 其次, 隨機性雖然有助于提升搜索空間的覆蓋率, 但也會引入性能的不穩(wěn)定性, 使不同運行結(jié)果之間存在較大差異, 缺乏一致性. 此外, 該算法對初始排序質(zhì)量
依賴較高, 如果初始排序較差, 隨機擾動的優(yōu)化效果會受到限制, 進而降低算法的整體性能. 最后, 對一些規(guī)模較大的問題, 隨機搜索策略無法有效覆蓋全部優(yōu)選解, 導致搜索效果
的局限性. 因此, 在實際應(yīng)用中, 應(yīng)充分考慮這些限制并與具體問題需求相結(jié)合, 以優(yōu)化算法的適用性和效率.
1.4 角點占據(jù)布圖規(guī)劃算法
角點占據(jù)(corner-occupying action, COA)算法[8]是用于解決二維矩形打包問題的啟發(fā)式算法, 基于“角點占據(jù)行為”和“凹陷度優(yōu)化”兩個核心概念設(shè)計, 旨
在通過合理放置矩形提高空間利用率, 減少未利用的碎片空間. 應(yīng)用場景包括制造業(yè)的鋼板、 玻璃等材料的切割優(yōu)化, 通過減少材料浪費降低成本; 物流領(lǐng)域貨物裝載和倉儲規(guī)劃,
提高空間利用率; 超大規(guī)模集成電路設(shè)計中的模塊布局, 布局緊湊和高效利用空間.
COA算法的核心思想是通過優(yōu)先占據(jù)角點[9]放置矩形, 同時利用凹陷度指標對放置位置進行優(yōu)化. 角點是指由已放置矩形或容器邊界形成的交點, 這些點通常是
打包中潛在的最佳位置, 因為占據(jù)這些位置可顯著減少剩余空隙, 從而提高打包密度. 凹陷度則用來衡量矩形與周圍環(huán)境的接近程度, 凹陷度值越高, 說明放置后的矩形與周圍矩形貼合越緊密, 打包方案越緊湊.
角點占據(jù)行為是該算法的基礎(chǔ), 通過優(yōu)先將待放置矩形安排在由已放置矩形或容器邊界形成的角點位置, 顯著減少空隙, 提高打包密度. 角點占據(jù)能最大限度地利用現(xiàn)有空間, 使矩形
盡可能靠近邊界或其他矩形, 從而形成緊湊的布局. 此外, 當矩形不僅占據(jù)角點, 還與其他已放置矩形直接接觸時, 這種放置被稱為洞穴占據(jù)行為. 洞穴占據(jù)進一步優(yōu)化了矩形與
周圍矩形的貼合程度, 減少了未利用空間, 是提高空間利用率的重要策略.
凹陷度則是COA算法中的另一個關(guān)鍵指標, 用于衡量矩形放置的緊密程度. 凹陷度大小反映了矩形與其鄰近矩形或邊界的接觸程度, 值越高, 說明矩形放置越緊湊. 凹陷度Ci
的計算通過評估矩形與周圍環(huán)境的距離實現(xiàn):
Ci=1-diwi·hi,(1)
其中di為待放置矩形與最近鄰矩形或邊界的距離, wi為待放置矩形的寬, hi為待放置矩形的高. 通過凹陷度的優(yōu)化, 算法能優(yōu)先選擇使打包密度最大的角點位
置進行放置. 此外, 凹陷度還結(jié)合了矩形的形狀特性, 通過考慮長寬比等因素進一步提升算法的選擇性.
在具體實現(xiàn)中, COA算法通過一套優(yōu)先級規(guī)則指導放置決策. 在所有可行的角點中, 首先計算每個角點與所有候選矩形的凹陷度, 并選擇凹陷度最大的角點作為目標位置; 若多個
角點凹陷度相同, 則優(yōu)先選擇能提升長寬比的矩形放置方案; 若仍有多種選擇, 則根據(jù)矩形排列順序最終決定放置位置. 這一基于凹陷度和優(yōu)先級規(guī)則的決策過程, 使COA算法能
在打包過程中不斷優(yōu)化空間利用率. 通過角點占據(jù)與凹陷度優(yōu)化的結(jié)合, COA算法為高效解決二維矩形打包問題提供了一種可靠且簡潔的策略.
COA算法能顯著提高空間利用率, 減少未利用的碎片空間, 同時算法設(shè)計簡潔高效, 計算復雜度不高, 便于實現(xiàn). 該算法能優(yōu)先選擇空間利用率最高的放置方式, 從而在局部最優(yōu)驅(qū)
動下實現(xiàn)較緊湊的全局布局. 但COA算法也存在一定局限性, 其基于局部優(yōu)化的特性可能導致陷入局部最優(yōu)解, 錯失全局最優(yōu)方案; 同時, 算法對初始角點和矩形排列順序較
敏感, 初始條件選擇不當會影響最終結(jié)果. 此外, 在問題規(guī)模顯著擴大時, 計算凹陷度和更新角點列表的開銷會隨之增加, 導致運行效率下降. 這些因素在一定程度上限制了COA算
法在超大規(guī)模打包問題中的性能, 但并不削弱其在小到中規(guī)模問題中的有效性和實用價值.
2 基于分析的布圖規(guī)劃方法
分析方法通過將布局問題轉(zhuǎn)化為具有線性約束的數(shù)學規(guī)劃問題, 如二次規(guī)劃問題, 這類方法提供了一種高效且有確定性的解決方案, 將模塊的位置坐標作為自變量, 根據(jù)面積、 線
長等優(yōu)化目標建立線性或非線性(不)等式方程組進行求解, 最終獲得各模塊在版圖中的最優(yōu)位置. 這類算法因其確定性, 對特定布局問題會生成一致的結(jié)果. mPL6
(multilevel placement version 6)[10],APlace[11]和NTUplace3[12]是此類分析方法的經(jīng)典代表, 下面介紹這3種算法的工作原理、 特點、 應(yīng)用場景、 優(yōu)勢和局限性.
2.1 多層次非線性編程布局方法mPL6
多層次非線性編程的混合尺寸布局mPL6方法[10]是一種適用于復雜集成電路布局的高效算法, 其工作流程包括全局布局、 合法化和詳細布局3個階段.
在全局布局階段, 算法基于多層次優(yōu)化思想, 通過最佳選擇聚類法遞歸地聚合與細化問題規(guī)模, 并在每一層中采用力導向布局平衡線長與密度, 確保模塊分布均勻. 在合法化階段, 利
用約束圖方法處理宏觀模塊的重疊問題, 通過構(gòu)建水平和垂直鄰接圖調(diào)整模塊位置, 同時通過動態(tài)權(quán)重調(diào)整優(yōu)化關(guān)鍵路徑, 降低最終布線長度. 詳細布局階段則采用窗口交換算法, 在
局部區(qū)域內(nèi)對模塊位置進行微調(diào), 通過最佳排列進一步減少布線長度. 其核心特點是多層次優(yōu)化增強了算法的可擴展性和魯棒性, 提出了密度敏感的布局方法, 能逐步確定大型模
塊的位置, 從而降低合法化階段的計算復雜度, 并在優(yōu)化線長和密度平衡的同時滿足復雜設(shè)計約束.
該方法尤其適用于高精度要求的混合尺寸設(shè)計, 在低白空間或高密度場景下表現(xiàn)尤為出色. 但其算法復雜度較高, 在處理超大規(guī)模設(shè)計時耗時較長.
2.2 基于分析優(yōu)化的布局方法APlace
APlace[11]是一種基于分析優(yōu)化的通用布局工具, 旨在通過數(shù)學分析技術(shù)實現(xiàn)高效的集成電路布局. 這是一種通過優(yōu)化線長、 密度和平衡設(shè)計約束的數(shù)學分析技
術(shù)實現(xiàn)高效布局的工具, 具有高靈活性和廣泛的適用性, 其工作流程包括全局布局、 密度與布線優(yōu)化以及特殊問題優(yōu)化3個階段.
在全局布局階段, APlace采用平滑的線長函數(shù)如log-sum-exp[13-14]和多層次框架, 將問題分解為若干層次的松弛優(yōu)化
問題, 并通過結(jié)合梯度下降方法進行求解, 同時動態(tài)調(diào)整平滑參數(shù)以加速收斂. 在密度與布線優(yōu)化中, 提出混合使用不同線長與密度函數(shù)的策略, 結(jié)合改進的懲罰函數(shù)控制密度約束,
有效平衡布局密度和線長優(yōu)化. 針對特殊問題, 如電源退化等, APlace通過重新分布電路單元優(yōu)化供電穩(wěn)定性, 并結(jié)合模擬和時序分析進行位置感知的布局優(yōu)化. 其核心特點是靈活性
強, 可擴展至時序驅(qū)動、 混合尺寸設(shè)計等不同場景, 采用動態(tài)密度調(diào)整策略在速度和質(zhì)量之間取得良好平衡.
APlace適用于需要處理多樣化約束的布局問題, 以及對速度要求較高的中等規(guī)模問題設(shè)計. 盡管其速度較早期版本有所提升, 但在超大規(guī)模問題中仍落后于專門的快速工具.
2.3 大規(guī)?;旌铣叽绮季址椒∟TUplace3
NTUplace3[12]是一種高效的大規(guī)模混合尺寸布局工具, 專為現(xiàn)代集成電路設(shè)計中的復雜約束問題而開發(fā). 其核心思想是基于log-sum-exp函數(shù)的線長模型, 通過
動態(tài)調(diào)整密度分布和平滑技術(shù), 在優(yōu)化線長、 密度均衡和模塊位置合法性之間實現(xiàn)良好平衡.
NTUplace3的布局流程包括全局布局、 合法化和詳細布局3個階段: 在全局布局中, 采用log-sum-exp模型結(jié)合兩階段平滑技術(shù)控制模塊密度, 并通過動態(tài)可用空間分配減少擁塞;
在合法化階段, 使用基于鄰接圖的模塊調(diào)整策略, 同時引入宏塊平移和預(yù)見合法化技術(shù), 確保無重疊布局; 在詳細布局階段, 通過單元匹配和滑動優(yōu)化技術(shù)進一步優(yōu)化線長和局部密度分布.
在性能方面, NTUplace3展現(xiàn)了強大的大規(guī)模設(shè)計處理能力, 能在包含大量模塊和預(yù)放置塊的復雜場景中實現(xiàn)高效布局. 此外, 共軛梯度法結(jié)合動態(tài)步長調(diào)整的優(yōu)化方法顯著加快了
全局布局的收斂速度, 顯著提升了大規(guī)模設(shè)計的效率. 但對包含大量預(yù)放置塊的設(shè)計, 其計算復雜度增加, 且在時序或溫度等多目標優(yōu)化任務(wù)中適用性有限. NTUplace3
憑借其先進的數(shù)學模型和優(yōu)化技術(shù), 為混合尺寸和高密度集成電路設(shè)計提供了有效的解決方案.
3 基于迭代的布圖規(guī)劃方法
迭代法求解VLSI布圖規(guī)劃和布局問題時, 首先需要將布圖編碼. 根據(jù)平面圖是否可沿一條直線進行一次或多次水平或垂直切割, 將其分為可切片平面結(jié)構(gòu)和不可切片平面結(jié)構(gòu)
[15-16], 二者均需通過數(shù)據(jù)結(jié)構(gòu)進行編碼. 對于可切片平面結(jié)構(gòu), 常采用波蘭表示法處理[17];" 對于不可切片平面結(jié)構(gòu), 可采用序列對(sequence pair)[18]、 角塊列表(corner block list)
[19]、 有界切片網(wǎng)格(bounded slicing grid, BSG)[20-21]、 傳遞閉包圖(transitive closure graph, TCG)[22-23]及其改進版本TCG-S[24]、
O-Tree[15]和B*-Tree[25-27]等表示方法. 然后需要選擇一個元啟發(fā)式搜索的框架, 例如遺傳算法[28]、 模擬退火算法[29-30]、 蟻群算法[31]、 粒
子群優(yōu)化算法[32]、 模因算法[33-34]和混合算法[35-37]等.
3.1 基于遺傳算法的布圖規(guī)劃方法
遺傳算法(genetic algorithm, GA)是根據(jù)大自然中生物體進化規(guī)律而設(shè)計的, 是以達爾文生物進化論的自然選擇和遺傳學理論為基礎(chǔ)模
擬生物進化過程的計算模型, 通過模擬自然進化過程搜索最優(yōu)解. 該算法將問題的求解過程轉(zhuǎn)換成類似生物進化中染色體基因的交叉、 變異等過程.
算法首先隨機生成一組解構(gòu)成初始種群, 然后根據(jù)平面圖的各種參數(shù), 如塊的高度、 模塊的數(shù)量等, 計算出適應(yīng)度函數(shù), 根據(jù)適應(yīng)度選擇優(yōu)良個體作為父代, 通過交叉操作生成子代
以產(chǎn)生新的解, 并對子代進行隨機變異操作, 以增加種群的多樣性, 從而避免陷入局部最優(yōu)解. 最后, 通過不斷更新種群并重復該過程, 直到滿足停止條件, 從而獲得優(yōu)化結(jié)果.
遺傳算法在布局設(shè)計中的交叉算子常存在不能有效繼承父代優(yōu)良特性的問題. 因此, Lin等[38]提出了改進遺傳算法(GFA)用于優(yōu)化可切片結(jié)構(gòu)的布局面積, 該
算法融合了切片樹編碼方案的特性和遺傳算法的進化機制. GFA算法用二叉樹結(jié)構(gòu)表示可切片結(jié)構(gòu), 并提出了一種新的遺傳算子, 該算子在算法中始終繼承父代的優(yōu)良特性, 從而有效探
索解空間. 算法首先隨機生成字符串組成種群, 計算適應(yīng)度, 然后進入包括交叉和變異操作的進化階段, 設(shè)置交叉率大于變異率, 若在給定時間內(nèi)無改進則調(diào)整閾值, 當滿足停止條
件時算法結(jié)束. 該方法能避免遺傳算法在布局設(shè)計中交叉算子不能有效繼承父代優(yōu)良特性的問題, 彌補了傳統(tǒng)進化算法在布局設(shè)計上的不足.
3.2 基于模擬退火算法的布圖規(guī)劃方法
模擬退火算法來源于固體退火原理, 是一種基于概率的算法, 將固體升溫至充分高, 再將其慢慢冷卻, 升溫時, 固體內(nèi)部粒子隨升溫變?yōu)闊o序狀, 內(nèi)能增大, 而慢慢冷卻時粒子漸趨有
序, 在每個溫度都達到平衡態(tài), 最后在常溫時達到基態(tài), 內(nèi)能減為最小. 模擬退火算法從某一較高初始溫度開始, 伴隨溫度參數(shù)的不斷下降, 結(jié)合概率特性在解空間中隨機尋找目標函
數(shù)的全局最優(yōu)解, 即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu). 模擬退火算法的主要缺點是它給出了近似最優(yōu)解, 但不能保證穩(wěn)定[39]. 模擬退火算法是一
種通用的優(yōu)化算法, 理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用, 如VLSI[40]和信號處理等領(lǐng)域.
Chang等[25]提出了B*-Tree的布圖表示法并使用模擬退火算法求解, 用很短的時間得到了較優(yōu)的布圖解. Chen等[29]提出了一種基于B
*-Tree表示的快速三階段模擬退火FastSA算法, 并對面積和長度進行了優(yōu)化. FastSA算法可以通過動態(tài)調(diào)整成本函數(shù)中的權(quán)值優(yōu)化線長, 三階段溫度控
制可以有效避免陷入局部最優(yōu). 但由于FastSA算法在每一步中只能獲得一個鄰居解, 因此無法盡可能多地探索搜索空間.
3.3 基于蟻群算法的布圖規(guī)劃方法
蟻群算法是一種基于自然界螞蟻行為模式的優(yōu)化算法[41], 體現(xiàn)了了一種正反饋機制: 選擇某條路徑的螞蟻越多, 這條路徑對其他螞蟻就越有吸引力, 即更傾向于選擇吸引力高的路徑.
Hoo等[31]提出了一種針對VLSI多目標布局優(yōu)化的變量順序蟻群系統(tǒng)(VOAS). 該系統(tǒng)使用角列表模型[38]表示芯片布局, 并通過
VOAS螞蟻和偵查螞蟻兩組螞蟻進行合作, 優(yōu)化芯片區(qū)域和連線長度. 偵查螞蟻搜集局部信息, 而VOAS螞蟻則根據(jù)局部和全局信息決定模塊的放置. 這種變量順序?qū)傩允刮浵佋谶x擇
模塊位置時能根據(jù)它們在布局過程中的不同階段優(yōu)先考慮全局或局部信息. 盡管VOAS通過在路徑選擇中使用變量順序?qū)傩院托薷男畔⑺馗乱?guī)則改進傳統(tǒng)的蟻群算法, 但在算法
的早期階段, 所有螞蟻會跟隨相同的路徑并構(gòu)建相同的解決方案, 從而導致產(chǎn)生次優(yōu)解.
3.4 基于粒子群優(yōu)化的布圖規(guī)劃方法
粒子群優(yōu)化(particle swarm optimisation, PSO)算法是一種群體智能算法, 屬于元啟發(fā)式算法的一種. 靈感來源于鳥群覓食和魚群游動的社會行為[42]. 粒子群優(yōu)化
算法中每個個體稱為粒子, 粒子組成群體. 粒子群優(yōu)化算法從隨機粒子開始, 每個粒子在解空間內(nèi)以一定速度飛行, 并根據(jù)自身和鄰居的經(jīng)驗進行更新. 粒子群優(yōu)化算法在處理連續(xù)優(yōu)
化問題時特別有效, 常被用于各種工程和科學問題的求解, 如函數(shù)最小化和其他多目標優(yōu)化問題等.
Chen等[43]提出了一種基于粒子群優(yōu)化的算法處理VLSI布圖規(guī)劃問題, 采用基于模塊數(shù)的整數(shù)編碼和新的加速度系數(shù)推薦值對粒子群優(yōu)化算法進行優(yōu)
化布置. 受遺傳算法物理特性的啟發(fā), 將遺傳算法中的突變算子和交叉算子的原理融入到PSO算法中, 使該算法擺脫了局部最優(yōu), 實現(xiàn)了較好的多樣性. 由于各變量之間相互影響, 而變量
的賦值通常是主觀的, 將導致賦值困難. 因此, 為避免這些缺點, 未來的工作可側(cè)重于提高算法的效率.
3.5 基于模因算法的布圖規(guī)劃方法
模因算法(memetic algorithm, MA)[44]是一種結(jié)合了群體智能和局部搜索策略的優(yōu)化技術(shù). 它的核心思想是模擬自然和文化進化過程, 通過全局搜索和局部精細搜索相結(jié)合, 以提高搜索效
率和解的質(zhì)量. 模因算法一般是進化算法和局部搜索的結(jié)合. 進化算法用于尋找全局最優(yōu), 局部搜索有助于進化計算的收斂速度.
Tang等[33]引入了一種基于O-tree表示的模因算法MA, 通過結(jié)合混合遺傳算法和新的偏差搜索策略, 雖然在面積成本上有所優(yōu)化, 但在面積與線長之間
的權(quán)衡上存在局限. Shanavas等[45]提出的算法結(jié)合了遺傳算法等分層設(shè)計技術(shù)和模擬退火等構(gòu)造技術(shù)進行局部搜索, 以解決VLSI的分區(qū)和布局問題.
3.6 基于混合算法的布圖規(guī)劃方法
Chen等[46]提出了一種混合遺傳算法(hybrid genetic algorithm, HGA), 該算法采用有效的遺傳搜索方法對搜索空間進行探索, 并采用有效的局部搜索
方法對搜索區(qū)域內(nèi)的信息進行挖掘. Chen等[30]提出了一種采用B*-Tree表示的混合模擬退火算法(HSA)優(yōu)化布圖規(guī)劃的面積和總長度. HSA有3個主要思想: 第一個
思想是一種新的貪心方法構(gòu)造初始B*-Tree; 第二個思想是通過交換B*-Tree中的兩個子樹探索搜索空間的新操作; 第三個思想是采用一種新的搜索策略, 用于平衡全局搜索和局部搜
索, 但在搜索空間的探索上僅采用交換兩個子樹的方法仍不夠充分, 缺乏多樣性. Sivaranjani等[37]提出了一種基于粒子群優(yōu)化和遺傳算法的混合算法, 其結(jié)合了
粒子群優(yōu)化算法、 螢火蟲算法(FF)和修正角表算法(MCL)的混合粒子群優(yōu)化-螢火蟲算法(HPSOFF). 最初, 粒子群優(yōu)化算法利用MCL算法進行非切片平面圖表示和適
應(yīng)度值評估, 由粒子群優(yōu)化算法得到的解作為FF算法的初始解, 再使用MCL算法對FF算法進行適應(yīng)度函
數(shù)評估和平面圖表示, 通過從粒子群優(yōu)化子系統(tǒng)和遺傳算法子系統(tǒng)之間交換一些個體, 兩個子系統(tǒng)共享布局信息并共同進化. 文獻[36]提出了智能決策混合粒子群優(yōu)化-遺傳算法PG
HA, 通過均勻分布溫度在芯片上減少面積、 帶寬. 該算法首先利用B*-Tree生成初始平面圖, 然后利用基于PSO-GA的混合算法得到最優(yōu)布局方案. 在控制溫度方面效
果良好. Xu等[47]提出了一種結(jié)合蟻群算法和模擬退火算法的兩階段方法處理固定輪廓布圖問題. 通過采用序列對表示, 兩階段算法可以很容易地應(yīng)用于二維布
圖規(guī)劃問題, 并可獲得很好的布線效果. 受MA方法的啟發(fā), Chen等[34]在HSA工作的基礎(chǔ)上, 提出了一種自適應(yīng)混合模因算法AHMA解決該問題, 選擇遺傳算法作為全局搜索方法, 改進的模擬
退火算法作為局部搜索方法, 并采用死亡概率策略平衡全局和局部搜索. 盡管在全局和局部搜索上取得了平衡, 但其復雜的交叉操作和靜態(tài)成本函數(shù)限制了其多目標優(yōu)化能力.
在多目標優(yōu)化方面, Srinivasan等[48]提出了基于多目標螢火蟲優(yōu)化的布圖規(guī)劃技術(shù)MOFO-FP, 針對固定輪廓約束問題, 利用能量和熱感知螢火蟲
優(yōu)化(EHAFO)算法進行優(yōu)化. 在螢火蟲優(yōu)化算法中, 為在超大規(guī)模集成電路設(shè)計中進行高效的布局規(guī)劃, 計算了發(fā)熱量、 占用空間和導線長度等多目標函數(shù). 根據(jù)目標函數(shù), 計算
出每只螢火蟲的光強, 將低亮度的螢火蟲向高亮度的螢火蟲移動, 以確定最佳位置. 最后, 根據(jù)螢火蟲的強度對其進行排序, 找到最優(yōu)的VLSI平面規(guī)劃樹結(jié)構(gòu). MOFO-FP技術(shù)減少了電路
占用的空間, 并降低了產(chǎn)生的熱量, 同時縮短了導線長度. MOFO-FP具有靈活性, 可以進一步根據(jù)特殊目標或更多目標進行調(diào)整和擴展, 以適應(yīng)不同的布局規(guī)劃需求. 但在設(shè)計大
型電路時會出現(xiàn)時間復雜度問題, 隨著電路規(guī)模增大, 算法執(zhí)行所需時間也會顯著增加, 影響算法的效率和實用性.
Jiang等[49]提出了DPAHMA算法, 是一種基于AHMA算法的改進算法. 通過引入候選種群機制、 動態(tài)自適應(yīng)目標函數(shù)和改進的遺傳算子, 進一步提高算法的性能和搜索
能力, 以更有效地處理非切片VLSI布圖規(guī)劃問題. 自適應(yīng)目標函數(shù)能找到更適合用戶指定權(quán)重的解; 全局搜索階段引入候選種群輔助正常種群的主輔種群機制. 為充分利用局部
搜索方法獲得的信息, 候選種群保留其高質(zhì)量的解. 在每次迭代結(jié)束前, 候選種群中的個體與正常種群中的個體交叉, 以盡可能獲得更高質(zhì)量的解.
4 基于機器學習的布圖規(guī)劃方法
在超大規(guī)模集成電路布圖規(guī)劃領(lǐng)域, 機器學習方法展現(xiàn)出獨特的優(yōu)勢和潛力, 其中基于深度學習的布圖規(guī)劃方法已取得了一定成果. 而除深度學習外, 強化學習同樣在布圖規(guī)劃中有重
要的應(yīng)用與探索, 其通過智能體與環(huán)境的交互尋求最優(yōu)策略, 為布圖規(guī)劃提供了新的思路和方法. 此外, 將深度學習與強化學習相結(jié)合的布圖規(guī)劃方法在近年研究中也備受關(guān)注.
4.1 基于深度學習的布圖規(guī)劃方法
深度學習是基于人工神經(jīng)網(wǎng)絡(luò)的機器學習技術(shù), 其通過構(gòu)建多層神經(jīng)網(wǎng)絡(luò)模型, 使計算機從海量數(shù)據(jù)中自動學習特征與模式. 其優(yōu)勢顯著, 具有強大的自動特征學習能力, 具有準確性高
和可擴展性佳的特點, 可處理大規(guī)模數(shù)據(jù)與復雜模型結(jié)構(gòu), 能隨數(shù)據(jù)量與計算資源提升而優(yōu)化性能, 在多領(lǐng)域都有廣泛應(yīng)用.
Lin等[50]提出了稱為DREAMPlace的GPU加速布局框架, 通過將解析布局問題等效轉(zhuǎn)換為訓練神經(jīng)網(wǎng)絡(luò)實現(xiàn). 該框架基于深度學習, 將解析布局問題類
比為神經(jīng)網(wǎng)絡(luò)訓練問題, 把單元位置視為權(quán)重, 線長成本對應(yīng)預(yù)測誤差, 密度成本對應(yīng)正則化項. 在實現(xiàn)過程中, 從隨機初始布局開始, 通過高效的全局布局迭代, 結(jié)合Nesterov方法
[51]優(yōu)化, 在收斂后進行合法化操作, 最后依賴外部工具進行詳細布局, 從而實現(xiàn)了在全局布局和合法化過程中的顯著加速且保持質(zhì)量, 展現(xiàn)出良好穩(wěn)定性和擴展
性. 該框架在超大規(guī)模集成電路布局中具有重要意義, 能顯著提高布局速度并保持質(zhì)量. 但DREAMPlace的詳細布局仍依賴于外部框架, 若外部工具未進行GPU加速或與DREAMPlace
的集成不佳, 則將無法充分發(fā)揮GPU加速的潛力, 影響整個布局流程的效率. 此外, 該方法效率受硬件性能影響, 設(shè)備配置不足時無法達到最佳效果.
4.2 基于強化學習的布圖規(guī)劃方法
強化學習是一種機器學習范式, 智能體在環(huán)境中采取一系列行動, 根據(jù)環(huán)境反饋的獎勵信號學習最優(yōu)的行為策略. 智能體的目標是最大化長期累積獎勵, 環(huán)境會在智能體行動后返回
一個獎勵信號, 用于評估行動的好壞. 智能體在與環(huán)境的交互過程中通過學習策略達成回報最大化或?qū)崿F(xiàn)特定目標.
He等[52]提出了一種方法, 旨在利用強化學習獲取有效局部搜索啟發(fā)式算法, 從而解決布圖規(guī)劃問題. 該方法將布圖規(guī)劃中的局部搜索問題轉(zhuǎn)化為強化學
習問題, 詳細定義了包含狀態(tài)、 動作、 轉(zhuǎn)移和獎勵的Markov決策過程. 選取能量相關(guān)統(tǒng)計信息、 擾動影響和搜索進度等合適特征, 構(gòu)建以多層感知器為策略近似器的神經(jīng)
網(wǎng)絡(luò)作為智能體, 利用DQN(deep Q-network)算法應(yīng)對大動作空間帶來的挑戰(zhàn), 實現(xiàn)智能體的有效訓練. 該方法
具有在智能體搜索過程更平滑、 生成布圖死區(qū)空間更小等顯著優(yōu)勢. 但該方法的訓練樣本是隨機生成的網(wǎng)表, 無法保證完全覆蓋實際電路布局中的各種復雜情況, 導致訓練出的模型在面對
某些特定類型或極端情況下的電路布局時, 泛化能力不足.
4.3 基于深度強化學習的布圖規(guī)劃方法
深度強化學習是一種機器學習方法, 它將深度學習的感知能力與強化學習的決策能力相結(jié)合. 智能體通過與布局環(huán)境的交互學習最優(yōu)策略.
Yu等[53]提出了一種基于序列對的深度強化學習布局規(guī)劃算法, 該算法利用序列對表示模塊間的幾何關(guān)系, 序列對由正負序列組成, 能有效描述模塊間的
相對位置關(guān)系. 在強化學習框架中, 狀態(tài)空間定義為包含完整門序列及模塊方向的布局方案, 動作空間通過預(yù)定義的5種擾動操作生成相鄰布局方案, 狀態(tài)轉(zhuǎn)移模型根據(jù)擾動使智能體
在不同狀態(tài)間轉(zhuǎn)換, 獎勵函數(shù)則根據(jù)布局面積和線長的優(yōu)化情況給予智能體相應(yīng)獎勵, 以激勵其尋找最優(yōu)布局. 采用基于Actor-Critic架構(gòu)的策略梯度算法訓練智能體, 借助深度神
經(jīng)網(wǎng)絡(luò)學習參數(shù), 根據(jù)獎勵反饋優(yōu)化策略, 其訓練過程遵循特定步驟, 并設(shè)置了如折扣因子、 學習率等超參數(shù). 該算法在布局面積和線長優(yōu)化等方面性能優(yōu)異, 尤其在大規(guī)模電路中優(yōu)勢
更明顯. 但目前該算法存在優(yōu)化時間長的問題亟待解決.
VLSI是芯片實現(xiàn)的關(guān)鍵技術(shù), 而芯片則是VLSI技術(shù)的物理載體, 二者相互促進、 共同發(fā)展. 在芯片布局設(shè)計領(lǐng)域, Mirhoseini等[54]設(shè)計了基于深度強化學習的布局設(shè)計方
法, 該方法將芯片布局問題定義為一個強化學習問題, 采用一種新的基于邊的圖卷積神經(jīng)網(wǎng)絡(luò)(edge-based graph convolutional neural network, Edge-
GNN)架構(gòu)學習芯片的豐富表示. 在該方法中, 芯片布局被視為一個順序的決策過程, 包括狀態(tài)、 動作、 狀態(tài)轉(zhuǎn)移和獎勵4個關(guān)鍵要素. 狀態(tài)包含網(wǎng)表信息、 節(jié)點信息等; 動作
是宏模塊的合法放置位置. 通過預(yù)測獎勵訓練網(wǎng)絡(luò), 然后將其作為策略網(wǎng)絡(luò)的編碼器, 以實現(xiàn)跨芯片的泛化. 此外, 該方法使用近端策略優(yōu)化(PPO)算法[55]更新策
略網(wǎng)絡(luò)的參數(shù), 以最大化累積獎勵. 在訓練過程中, 強化學習代理依次放置宏模塊, 然后使用力導向方法放置標準單元集群. 該方法在滿足設(shè)計標準方面均表現(xiàn)優(yōu)秀, 且在面積、 功
耗和線長等指標上與手動布局相當或更優(yōu), 目前已應(yīng)用于谷歌TPU設(shè)計. 但該方法對計算資源要求很高, 在資源受限的環(huán)境下不適用.
5 常用數(shù)據(jù)集
基準數(shù)據(jù)集MCNC(http://vlsicad.eecs.umich.edu/BK/MCNCbench/)和GSRC(http://vlsicad.eecs.umich.edu/BK/GSRCbench/
)是超大規(guī)模集成電路設(shè)計領(lǐng)域中常用的兩個關(guān)鍵數(shù)據(jù)集, 用于測試和評估布圖設(shè)計算法. 布圖設(shè)計是VLSI設(shè)計中的關(guān)鍵步驟, 其中不同功能塊的芯片在硅片上進行布局,
以優(yōu)化面積和互連長度等多種目標.
5.1 基準數(shù)據(jù)集MCNC
基準數(shù)據(jù)集MCNC廣泛用于評估VLSI CAD工具. 這些基準數(shù)據(jù)集包括來自MCNC研究項目的各種實際芯片布局的集合. 芯片布局從小到大, 涵蓋了廣泛的設(shè)計類型和復雜性.
5.2 基準數(shù)據(jù)集GSRC
基準數(shù)據(jù)集GSRC為研究人員和設(shè)計師提供一組標準化的測試集, 幫助他們評估其版圖設(shè)計方法和工具的效率和有效性. 這些基準數(shù)據(jù)集包括各種合成和現(xiàn)實世界的問題,
代表了VLSI設(shè)計的不同方面, 從簡單到復雜的電路布局. 其用于模擬設(shè)計時可面臨的不同場景
, 測試算法在各種復雜度和設(shè)計約束條件下的性能.
數(shù)據(jù)集GSRC和MCNC內(nèi)各電路屬性列于表1. 通過提供標準化測試, 這些基準數(shù)據(jù)集有助于促進版圖設(shè)計技術(shù)和VLSI設(shè)計方法的進步, 從而推動更高效、 更緊湊、 功耗更低芯片的開發(fā).
6 未來研究方向
在超大規(guī)模集成電路布圖規(guī)劃領(lǐng)域, 目前研究主要集中在開發(fā)各種算法以優(yōu)化布局的質(zhì)量和效率. 研究涵蓋了直觀構(gòu)造方法、 分析方法、 迭代方法及基于機器學習的方法. 由近年的
研究成果可見, 迭代方法和基于機器學習的方法成為研究重點, 迭代方法在尋找全局最優(yōu)解
方面表現(xiàn)出強大的能力, 機器學習方法則在處理復雜數(shù)據(jù)和特征學習方面具有優(yōu)勢. 綜合本文的研究進展介紹及分析, 未來研究可以圍繞以下幾個方面進行.
多目標優(yōu)化: 當前的超大規(guī)模集成電路布圖規(guī)劃方法大多數(shù)只考慮面積和線長這兩個優(yōu)化目標, 除面積和線長這兩個關(guān)鍵指標外, 溫度、 功耗等指標也是集成電路設(shè)計中影響芯片
性能和可靠性的重要因素. 溫度可以影響芯片的性能穩(wěn)定性和壽命, 功耗是衡量其能效的關(guān)鍵指標, 尤其是在移動設(shè)備和數(shù)據(jù)中心的應(yīng)用中尤為重要. 因此未來研究可以開發(fā)出能同時
考慮面積、 線長、 溫度和功耗等多個目標的布圖規(guī)劃算法, 以滿足現(xiàn)代集成電路設(shè)計中日益復雜的需求.
更高效的算法開發(fā): 雖然目前已有算法在超大規(guī)模集成電路布圖規(guī)劃中取得了一定成效, 但隨著集成電路設(shè)計復雜性的增加, 需要更高效的算法應(yīng)對更復雜的布局挑戰(zhàn). 當開發(fā)需
要基于以往方法進行改進時, 需關(guān)注可供使用的計算資源條件, 若計算資源不足, 可考慮基于迭代方法的算法展開優(yōu)化和改進.
算法融合: 未來研究可以探索將多種布圖規(guī)劃方法進行融合, 以提高算法的效率和優(yōu)化質(zhì)量,
進一步優(yōu)化現(xiàn)有的布圖規(guī)劃算法, 例如結(jié)合機器學習技術(shù)與傳統(tǒng)的迭代法, 以發(fā)揮各自的優(yōu)勢, 提升布圖規(guī)劃的效率和效果.
新型數(shù)據(jù)集和評估方法: 盡管基準數(shù)據(jù)集GSRC和MCNC包含了對芯片塊的詳細描述, 并被廣泛用于VLSI布圖規(guī)劃等問題的測試和評估, 但超大規(guī)模集成電路的實際設(shè)計具有多樣性, 現(xiàn)有
的基準數(shù)據(jù)集和評估方法無法保證完全反映實際設(shè)計中的復雜情況. 未來可以開發(fā)新的數(shù)據(jù)集和評估方法, 以更好地測試和評估布圖規(guī)劃方法的效果和性能.
參考文獻
[1] KAHNG A B, LIENIG J, MARKOV I L, et al. Chip Planning [C]//
VLSI Physical Design: From Graph Partitioning to Timing Closure. Berlin: Springer International Publishing, 2022: 53-93.
[2] RINI D P, SHAMSUDDIN S. Minimization of Floorplannin
g Area and Wire Length Interconnection Using Particle Swarm Optimization [EB/OL]. (2013-08-01)[2024-11-20]. https://www.researchgate.net/publication/326804232.
[3] SINGH R B, BAGHEL A S, AGARWAL A. A Review on VLSI Flo
orplanning Optimization Using Metaheuristic Algorithms [C]//2016 International Conference on Electric
al, Electronics, and Optimization Techniques (ICEEOT). Piscataway, NJ: IEEE, 2016: 4198-4202.
[4] BAKER B S, COFFMAN E G, Jr, RIVEST R L. Orthogonal Packings in Two Dimensions [J]. SIAM Journal on Computing, 1980, 9(4): 846-855.
[5] CHAZELLE B. The Bottomn-Left Bin-Packing Heuristic:
An Efficient Implementation [J]. IEEE Transactions on Computers, 1983, 32(8): 697-707.
[6] LESH N, MARKS J, McMAHON A, et al. New Heuristic and Interactive Approaches
to 2D Rectangular Strip Packing [J]. ACM Journal of Exprimental Algorithmics, 2005, 10: 12-1-12-18.
[7] HOPPER E, TURTON B C H. An Empirical Investigation of Meta-Heuristic and Heu
ristic Algorithms for a 2D Packing Problem [J]. European Journal of Operational Research, 2001, 128(1): 34-57.
[8] HUANG W Q, CHEN D B, XU R C. A New Heuristic Algorit
hm for Rectangle Packing [J]. Computers amp; Operations Research, 2007, 34(11): 3270-3280.
[9] WU Y L, HUANG W, LAU S C, et al. An Effective Quasi-human Based Heuristic
for Solving the Rectangle Packing Problem [J]. European Journal of Operational Research, 2002, 141(2): 341-358.
[10] CHAN T F, CONG J, SHINNERL J R, et al. mPL6: Enhanc
ed Multilevel Mixed-Size Placement [C]//Proceedings of the 2006 International Symposium on Physical Design. New York: ACM, 2006: 212-214.
[11] KAHNG A B, WANG Q K. A Faster Implementation of APlace [C]//Proceedings of t
he 2006 International Symposium on Physical Design. New York: ACM, 2006: 218-220.
[12] CHEN T C, JIANG Z W, HSU T C, et al. NTUplace3: An Analytical Placer for La
rge-Scale Mixed-Size Designs with Preplaced Blocks and Density Constraints [J
]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(7): 1228-1240.
[13] NAYLOR W C, DONELLY R, SHA L. Non-linear Optimization System and Method for
Wire Length and Delay Optimization for an Automatic Electric Circuit Placer: US, 6301693B1 [P]. 2001-01-24.
[14] KAHNG A B, WANG Q K. Implementation and Extensibili
ty of an Analytic Placer [C]//Proceedings of the 2004 International Symposium on Physical Design. New York: ACM, 2004: 18-25.
[15] GUO P N, CHENG C K, YOSHIMURA T. An O-Tree Representation of Non-slicing Fl
oorplan and Its Applications [C]//Proceedings 1999 Design Automation Conference. Piscataway, NJ: IEEE, 1999: 268-273.
[16] JAIN L, SINGH A. Non Slicing Floorplan Representati
ons in VLSI Floorplanning: A Summary [J]. International Journal of Computer Applications, 2013, 71(15): 12-20.
[17] WONG D F, LIU C L. A New Algorithm for Floorplan De
sign [C]//23rd ACM/IEEE Design Automation Conference. New York: ACM, 1986: 101-107.
[18] MURATA H, FUJIYOSHI K, NAKATAKE S, et al. VLSI Module Placement Based on Rec
tangle-Packing by the Sequence-Pair [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, 15(12): 1518-1524.
[19] HONG X L, HUANG G, CAI Y C, et al. Corner Block List: An Effective and Efficien
t Topological Representation of Non-slicing Floorplan [C]//IEEE/ACM International Conference on Computer Aided Design. Piscataway, NJ: IEEE, 2000: 8-12.
[20] NAKATAKE S, FUJIYOSHI K, MURATA H, et al. Module Placement on BSG-Structure
and IC Layout Applications [C]//Proceedings of International Conference on Computer Aided Design. Piscataway, NJ: IEEE, 1996: 484-491.
[21] KANG M, DAI W W M. General Floorplanning with L-Shaped, T-Shaped and Soft Bl
ocks Based on Bounded Slicing Grid Structure [C]//Proceedings of Asia and South Pacific Design Automation Conference. Piscataway, NJ: IEEE, 1997: 265-270.
[22] LIN J M, CHANG Y W. TCG: A Transitive Closure Graph
-Based Representation for General Floorplans [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005, 13(2): 288-292.
[23] LIN J M, CHANG Y W. TCG: A Transitive Closure Graph-Based Representation fo
r Non-slicing Floorplans [C]//Proceedings of the 38th Annual Design Automation Conference. New York: ACM, 2001: 764-769.
[24] LIN J M, CHANG Y W. TCG-S: Orthogonal Coupling of P*-Admissible Representa
tions for General Floorplans [C]//Proceedings of the 39th Annual Design Automation Conference. New York: ACM, 2002: 842-847.
[25] CHANG Y C, CHANG Y W, WU G M, et al. B*-Trees: A N
ew Representation for Non-slicing Floorplans [C]//Proceedings of the 37th Annual Design Automation Conference. New York: ACM, 2000: 458-463.
[26] SUN T Y, HSIEH S T, WANG H M, et al. Floorplanning Ba
sed on Particle Swarm Optimization [C]//IEEE Computer Society Annual Symposium on Emerging VLSI Techn
ologies and Architectures (ISVLSI’06). Piscataway, NJ: IEEE, 2006: 1-5.
[27] LIN J M, HUNG Z X. SKB-Tree: A Fixed-Outline Driven Representation for Mode
rn Floorplanning Problems [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2012, 20(3): 473-484.
[28] LIN C T, CHEN D S, WANG Y W. An Efficient Genetic Algorithm for Slicing Flo
orplan Area Optimization [C]//2002 IEEE International Symposium on Circuits and Systems (ISCAS). Piscataway, NJ: IEEE, 2002: 879-882.
[29] CHEN T C, CHANG Y W. Modern Floorplanning Based on B*-Tree and Fast Si
mulated Annealing [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(4): 637-650.
[30] CHEN J L, ZHU W X, ALI M M. A Hybrid Simulated Annealing Algorithm for Nonslicin
g VLSI Floorplanning [J]. IEEE Transactions on Systems, Man, and Cybernetics, 2011, 41(4): 544-553.
[31] HOO C S, JEEVAN K, GANAPATHY V, et al. Variable-Order Ant System for VLSI M
ultiobjective Floorplanning [J]. Applied Soft Computing, 2013, 13(7): 3285-3297.
[32] 陳錦珠. 適用于求解VLSI布圖規(guī)劃問題的多目標PSO算法研究 [D]. 福州: 福州大學, 2
011. (CHEN J Z. Research on Multi-objective PSO Algorithm for Solving VLSI Floorplanning Problem" [D]. Fuzhou: Fuzhou University, 2011.)
[33] TANG M L, YAO X. A Memetic Algorithm for VLSI Floorplanning [J]. IEEE Transac
tions on Systems, Man, and Cybernetics, 2007, 37(1): 62-69.
[34] CHEN J L, LIU Y, ZHU Z R, et al. An Adaptive Hybrid Memetic Algorithm for Therm
al-Aware Non-slicing VLSI Floorplanning [J]. Integration, 2017, 58: 245-252.
[35] 陳建利, 朱文興. 求解VLSI不可二劃分布圖規(guī)劃問題的混合遺傳算法 [J]. 福州大學學
報(自然科學版), 2014, 42(5): 688-693. (CHEN J L, ZHU W X. Hybrid Genetic Algori
thm for Solving the Non-slicing Floorplan Problem in VLSI [J]. Journal of Fuzhou University (Natural Science Edition), 2014, 42(5): 688-693.)
[36] SIVARANJANI P, SENTHIL K A. Thermal-Aware Non-slicing VLSI Floorplannin
g Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm [J]. Circuits, Systems, and Signal Processing, 2015, 34(11): 3521-3542.
[37] SIVARANJANI P, SENTHIL K A. Hybrid Particle Swarm Optimization-Firefly Al
gorithm (HPSOFF) for Combinatorial Optimization of Non-slicing VLSI Floorplanning [J]. Journal of Intelligent amp; Fuzzy Systems, 2017, 32(1): 661-669.
[38] LIN F, HE G M. An Improved Genetic Algorithm for Multi-objective Optimization [
C]//Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT’05). Piscataway, NJ: IEEE, 2005: 938-940.
[39] KIYOTA K, FUJIYOSHI K. Simulated Annealing Search through General Structure Fl
oorplans Using Sequence-Pair [C]//2000 IEEE International Symposium on Circuits and Systems (ISCAS). Piscataway, NJ: IEEE, 2000: 77-80.
[40] 姚新, 陳國良. 模擬退火算法及其應(yīng)用 [J]. 計算機研究
與發(fā)展, 1990(7): 1-6. (YAO X, CHEN G L. Simulated Annealing Algorithm and Its Applications [J]. Journal
of Computer Research and Development, 1990(7): 1-6.)
[41] COLORNI A, DORIGO M, MANIEZZO V. Distributed Optimi
zation by Ant Colonies [C]//Proceedings of the First European Conference on Artificial Life. New York: ACM, 1990: 1-12.
[42] KENNEDY J, EBERHART R. Particle Swarm Optimization
[C]//Proceedings of International Conference on Neural Networks. Piscataway, NJ:" IEEE, 1995: 1942-1948.
[43] CHEN G L, GUO W Z, CHEN Y Z. A PSO-Based Intelligent Decision
Algorithm for VLSI Floorplanning [J]. Soft Computing, 2010, 14(12): 1329-1337.
[44] KRASNOGOR N, SMITH J. A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design Issues [J].
IEEE Transactions on Evolutionary Computation, 2005, 9(5): 474-488.
[45] SHANAVAS I H, GNANAMURTHY R K. Wirelength Minimization in Partitioning and Fl
oorplanning Using Evolutionary Algorithms [J]. VLSI Design, 2011, 2011: 10-1-10-10.
[46] CHEN J L, ZHU W X. A Hybrid Genetic Algorithm for V
LSI Floorplanning [C]//2010 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway, NJ: IEEE, 2010: 128-132.
[47] XU Q, CHEN S, LI B. Combining the Ant System Algorithm and Simulated Anneal
ing for 3D/2D Fixed-Outline Floorplanning [J]. Applied Soft Computing, 2016, 40: 150-160.
[48] SRINIVASAN B, VENKATESAN R. Multi-objective Optimization for Energy and Hea
t-Aware VLSI Floorplanning Using Enhanced Firefly Optimization [J]. Soft Computing, 2021, 25(5): 4159-4174.
[49] JIANG L Y, OUYANG D T, ZHOU H S, et al. DPAHMA: A Novel Dual-population Adaptive H
ybrid Memetic Algorithm for Non-slicing VLSI Floorplans [J]. The Journal of Supercomputing, 2023, 79(14): 15496-15534.
[50] LIN Y B, DHAR S, LI W X, et al. DREAMPlace: Deep Learning Toolkit-Enabled GPU Ac
celeration for Modern VLSI Placement [C]//Proceedings of the 56th Annual Design Automation Conference 2019. New York: ACM, 2019: 1-6.
[51] LU J W, CHEN P W, CHANG C C, et al. ePlace: Electrostatics-Based Placement Using
Fast Fourier Transform and Nesterov’s Method [J]. ACM Transactions on Design Automation of Electronic Systems, 2015, 20(2): 17-1-17-34.
[52] HE Z L, MA Y Z, ZHANG L, et al. Learn to Floorplan through Acquisition of Effec
tive Local Search Heuristics [C]//2020 IEEE 38th International Conference on Computer Design (ICCD). Piscataway, NJ: IEEE, 2020: 324-331.
[53] YU S L, DU S M. VLSI Floorplanning Algorithm Based on Reinforcement Learning wit
h Obstacles [C]//Biologically Inspired Cognitive Architectures 2023. Berlin: Springer, 2024: 1034-1043.
[54] MIRHOSEINI A, GOLDIE A, YAZGAN M, et al. A Graph Placeme
nt Methodology for Fast Chip Design [J]. Nature, 2021, 594(7862): 207-212.
[55] SCHULMAN J, WOLSKI F, DHARIWAL P, et al. Proximal Policy
Optimization Algorithms [EB/OL]. (2017-07-20)[2024-11-25]. https://arxiv.org/abs/1707.06347.
(責任編輯: 韓 嘯)