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

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

關鍵詞：大規模集成電路；布圖規劃；非光滑優化；固定輪廓；共軛次梯度法

中圖分類號：TP391 文獻標志碼：A 文章編號：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 引言

布圖規劃是超大規模集成電路（very large-scale integration circuit，VLSI）物理設計中的重要步驟，布圖結果對VLSI芯片的性能具有重要影響［1］。然而，VLSI布圖規劃需要在滿足約束條件的情況下考慮線長、面積等多個優化目標來實現模塊的最佳放置，是一個具有復雜約束的多目標優化問題［2］。隨著集成電路技術的發展，VLSI布圖規劃場景越來越復雜，為高性能布圖規劃算法的設計帶來巨大的挑戰。

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

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

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

1 布圖規劃問題的非光滑解析數學規劃模型

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

本文重點研究兩類經典的布圖規劃問題：第一類是給定布圖區域對線長指標進行優化的固定輪廓布圖規劃問題，第二類是同時對線長和面積兩個指標進行優化的無固定輪廓約束的布圖規劃問題。基于此，可以建立VLSI布圖規劃的通用約束優化模型

3 實驗結果與分析

為了驗證本文的算法的性能，在著名的測試基準GSRC上進行了實驗。對于所有測試電路，I/O焊盤固定在給定坐標處，所有電路的模塊都是硬模塊。本文的所有實驗采用基于Windows操作系統的C++語言程序，處理器為AMD Ryzen 7 5800H，主頻3.2 GHz，內存為16 GB。

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

本文在全局布圖規劃階段以及合法化階段均采用CSA作為優化引擎，為了解CSA對布圖規劃數學模型的優化效率，以GSRC測試集中的n100電路為例，分別研究了全局布圖規劃階段和合法化階段CSA的優化性能，相應目標函數值隨迭代次數變化的折線圖如圖2所示。

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

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

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

3.2 固定輪廓約束的線長優化

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

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

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

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

在固定輪廓的布圖實例中，優化模型式（3）采用了重疊面積的平方根作為重疊程度衡量指標，消除了重疊面積和線長的量綱差異；同時，CSA_FC算法的迭代過程采用了先全局布圖再合法化的優化機制，從而能夠更好地對線長（HPWL）進行優化，對所有的測試實例上均能夠得到更好的線長優化結果。

3.3 無固定輪廓約束的線長和面積優化

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

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

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

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

對于n200和n300測試例子，CSA_GSS在面積和線長方面均要優于GA+SA和GA+RL。本文算法在大規模問題上具有優勢，但對于小規模問題，兩種比較算法均優于CSA_GSS。此外，結合強化學習策略的遺傳算法相對于傳統的GA+SA算法，整體上有著突出表現，具有研究潛力。圖3給出了CSA_GSS對n100、n200、n300電路的一次實驗布圖結果。

4 結束語

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

參考文獻：

［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］杜世民，夏銀水，儲著飛，等.面向軟模塊的穩定固定邊框布圖規劃算法［J］.電子與信息學報，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］黃志鵬，李興權，朱文興.超大規模集成電路布局的優化模型與算法［J］.運籌學學報，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］劉浩洋，戶將，李勇鋒，等.最優化：建模、算法與理論［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］徐杰，魯海燕，趙金金，等.拉丁超立方抽樣的自適應高斯小孔成像蝴蝶優化算法［J］.計算機應用研究，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

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

作者簡介：孫健（1999—），男，碩士，CCF會員，主要研究方向為優化算法在電子設計自動化中的應用；徐寧（1968—），男，教授，博導，博士，主要研究方向為電子設計自動化、先進封裝EDA、圖像處理、人工智能；吳建（1999—），男，碩士研究生，主要研究方向為電子設計自動化；朱展洋（2001—），男，碩士研究生，主要研究方向為電子設計自動化；陳彧（1981—），男（通信作者），副教授，碩導，博士，主要研究方向為智能優化算法、電子設計自動化（ychen@whut.edu.cn）；胡建國（1977—），男，研究員，博導，博士，主要研究方向為高端集成電路設計、電子設計自動化、物聯網、人工智能.