资源描述
以Corner Block List表示法處理植基於群聚策略之不確定性模組平面規劃問題潘佳信 江昱麟 蔡宗達 程仲勝大葉大學電機工程學系彰化縣大村鄉山腳路112號摘要隨著VLSI/SOC的蓬勃發展，如何在電路模組尚未設計完成時評估這些面積及長寬維度皆不確定模組在未來後端實體設計階段(physical design phase)所形成晶片面積大小是相當重要的議題。對於絕大多數先前研究而言，只評估由具有固定面積甚至具有固定長寬之確定性模組所形成之晶片面積，而對於不確定模組的平面規劃問題則未有著墨。因此在本論文中我們提出一個植基於群聚(clustering)策略之不確定模組平面規劃演算法以便能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用群聚技巧將模組聚集起來形成一些面積較大但個數較少的組合模組(supermodules)，最後以Corner Block List 表示法來記錄組合模組間相對位置關係並在其上執行模擬退火(simulated annealing)程序以求得面積最佳化的結果。由實驗結果得知，對於每個例子我們可以得出不確性模組所形成的最終晶片寬、高與其面積之機率分佈圖，藉此評估尚未設計完成之電路模組在未來所形成可能之晶片面積大小。關鍵詞: 實體設計、平面規劃、群聚、模擬退火以Corner Block List表示法處理植基於群聚策略之不確定性模組平面規劃問題A Clustering-Based Approach for Floorplanning of Uncertain Modules by Using Corner Block List Representation一、簡介VLSI後端實體設計階段(physical design phase)中的平面規劃(floorplanning)是整個階段的第一個步驟且是一個相當重要的步驟，其影響爾後其他步驟甚鉅，因此有許多方法被提出來解決後端實體設計階段平面規劃的問題2-18。平面規劃最主要的目的是放置一組電路模組(modules)於晶片上並使整體晶片面積達到最小。平面規劃後所得之最終平面圖(floorplan)可以分成可切割(slicing)平面圖12, 15與不可切割(non-slicing)平面圖2-11, 13, 14, 16, 17兩大類。因此，平面規劃演算法亦可分為處理可切割12, 15與不可切割2-11, 13, 14, 16, 17平面結構兩大類。在處理可切割平面結構方面可用可切割樹(slicing tree)12和波蘭表示法(polish expression)15表示模組間位置的關係。而在處理不可切割平面結構方面則可用BSG (Bounded-Sliceline Grid)表示法11、Sequence-Pair表示法10、O-Tree表示法3、B*-Tree表示法2、CBL(Corner Block List)表示法4及TCG(Transitive Closure Graph)表示法6等來表示模組間相對位置關係。隨著積體電路設計的複雜化，在實體設計階段時才考慮平面規劃問題已不能滿足系統設計需求，因此須在模組設計尚未完成前即考慮評估此種不確定模組對未來形成之晶片面積有何影響，進而修正系統階層之模組設計，使得整個系統設計趨於完善。然而除了文獻1提出以二元樹表示可切割之不確定模組平面規劃外，就我們所知以往並沒有其他關於解決不確定模組平面規劃問題之文章。因此在本論文中我們提出一個以Corner Block List不可切割表示法4來處理不確定模組之平面規劃問題。在我們的方法中，首先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用群聚技巧將模組聚集起來形成一些面積較大但個數較少的組合模組(supermodules)，最後以Corner Block List 表示法來記錄組合模組間相對位置關係並在其上執行模擬退火(simulated annealing)程序以求得面積最佳化的結果。二、問題描述不確定模組之平面規劃即是在模組彼此不重疊的限制下擺置一組不確定電路模組，其中令B = b1, b2, , bn為欲擺置之n個不確定寬與高之矩形模組集合，而第i個模組bi之寬、高可能值及其相對應之機率值分別為(wi1, Pwi1), (wi2, Pwi2), 與(hi1, Phi1), (hi2, Phi2), ，其中Pwik(Phik)為可能寬(高)值wik(hik)相對應之機率值，且Pwi1+Pwi2+ = 1及Phi1+Phi2+ = 1；經不確定模組平面規劃處理後可得到最終平面圖之寬與高機率分佈圖，分別為(w1, Pw1), (w2, Pw2), 與(h1, Ph1), (h2, Ph2) ，其中Pw1+Pw2+ = 1且Ph1+Ph2+ = 1。由於我們所提出解決平面規劃的方法是以CBL表示法4為基礎，因此以下將簡要說明CBL表示法如何記錄模組間相對位置關係以及如何在其上執行模擬退火的程序。CBL表示法是由S、L及T三種串列所組成；其中S串列記錄各個模組的代號，L串列記錄模組的位置關係，T串列紀錄每一個模組與其他相鄰模組所形成T字形的個數，由這三個串列，可得到一個唯一的平面圖。L串列所記錄的為目前欲擺入模組與其他已擺入模組的位置關係，此關係可分為兩類；一類為L = 0，而另一類為L = 1；其中L = 0表示目前擺入模組的位置必須位於上一個擺入模組位置的上方，而L = 1則表示其位置在上一個擺入模組位置的右方，如圖1所示。另一方面T串列由0、1所組成，每次讀入T串列時以讀至0為停止條件，並計算讀入1的個數，若讀入1之個數為N，則表示目前欲擺入之模組與N + 1個已擺入模組相鄰。BAAB(a) L = 0(b) L = 1圖1：目前欲擺入模組B與上一個擺入模組A的位置關係接著我們介紹如何在S、L、T三個串列上執行模擬退火的程序：步驟 1:隨機產生一組可行的S、L、T串列並計算其所對應之初始平面圖面積。步驟 2：開始執行模擬退火程序，我們利用以下幾種改變目前平面圖結構的方式進行退火程序：(a) 隨機交換S串列中的任兩個模組。(b) 隨機選擇L串列中的一個位置，並將1變0或0變1。(c) 隨機選擇T串列中的一個位置，並將1變0或0變1。(d) 模組旋轉90、180或270步驟 3:計算改變後新平面圖的面積期望值與面積變異數之總和。設定cost為此次產生之面積期望值與面積變異數之總和減去上一次接受之面積期望值與面積變異數之總和。若cost小於零則接受新解，若大於零則隨機產生一介於0至1之間的數r並比較r與exp(-cost/k)(k為溫度參數)之大小以決定是否接受新解。步驟 4:依照遞減公式逐次減小k值。重複步驟 2到步驟 4直到k值小於預設凝固點。三、兩階段平面規劃 所提平面規劃演算法在第一階段使用群聚技巧將模組群集起來形成一些面積較大的組合模組，接著在第二階段採用CBL表示法4來記錄組合模組間相對位置關係並執行模擬退火程序以求得面積最佳化的結果。以下針對演算法中兩階段的重要步驟程序加以說明。3.1 群聚在一般的平面規劃中，並沒有強制相關之模組必須擺放在附近，但在一般的IC設計中，有許多模組有著強烈的連結關係而不能相距太遠甚至必須相鄰，在這樣的情形下，我們必須將某些模組強制擺放在一起，另一方面適當的群聚可以增加所評估平面規劃結果的準確度，因此本論文中我們提出群聚的策略將模組組合形成較大的組合模組。目前我們只考慮每兩個模組群聚成一個組合模組，如此可減少多個模組同時群聚時可能會形成較多且較分散的閒置空間(dead space)問題。而在挑選模組群聚時需考慮群聚後組合模組之閒置空間。換句話說，組合模組之閒置空間愈少愈好。另一方面，任兩個模組群聚，依其相對位置之不同，會形成八種不同組合狀況，在不考慮連線接腳位置時，其中有四種狀況是重複的，所以可以將組合的情況簡化為四種。對於這四種組合我們將選擇閒置空間少的做為兩模組群聚後之組合模組。接著我們說明演算法中所採用由下往上(bottom up)階層式(hierarchy)模組群聚的步驟：步驟 1：設，其中W1及W2分別表示兩個組合模組相接觸的邊長，P1及P2分別分別表示兩個組合模組邊長之相對應機率值。 (a)任找一模組A，使其與模組B形成一組合模組，其中模組B為所有模組中與模組A群聚後可產生最小f值者。(注意：任兩模組群聚後之f值取其4種組合中f值最小者)。 (b)將已群聚之模組移除，對剩下之模組重複步驟(a)及(b)直到所有模組皆已群聚。步驟 2：將步驟1完成後之組合模組重新視為一般模組並重複步驟1及步驟2直至達到預設之群聚階層數。3.2 CBL為主之不確定性模組平面規劃之計算利用群聚技巧形成組合模組之後，我們使用CBL表示法4來紀錄組合模組間的相對位置，並記錄每一組合模組左下角有可能的X、Y座標與其相對應之機率。我們利用以下步驟求出每一組合模組左下角X、Y座標與其相對應之機率。步驟一：讀入串列S第一個元素S0並將其所對應之組合模組左下角座標設為(0, 1),(0,1) 。步驟二：For i=1 to n-1讀入串列L中之元素Li-1與讀入串列T，若讀入的元素Li-1 = 0，則將元素Si擺在Si-1的上方，並利用目前所讀入串列T之內容判斷與多少已擺放組合模組相鄰，計算Si 所對應組合模組左下角座標時，其X座標與相對應之機率與在相鄰組合模組中最左側者之X座標與其相對應之機率相同，而Y座標則為所有相鄰組合模組之Y座標加上其高後所形成有可能之高度相同；然而若Li-1 = 1，則將Si擺在Si-1的右方，此時Si 之Y座標與相對應之機率與在相鄰組合模組中最下側者之Y座標與其相對應之機率相同，而X座標則為所有相鄰組合模組之X座標加上其寬後所形成有可能之寬度相同。每一個組合模組左下角之座標與其相對應機率計算完成後，即可計算最終平面規劃結果的寬/高/面積及其相對應機率分佈。四、實驗結果在本論文中使用PC為實驗平台，其CPU時脈為2.2GHz，記憶體為512MB，使用編譯軟體為Microsoft Visual C+ 6.0。實驗所用的benchmarks取至MCNC包含apte、xerox、hp、ami33及ami49。在本次的實驗中，針對benchmarks模組的資料做了一點修改以符合不確定模組之平面規劃問題，其中將有些模組原本固定維度的資料改為具有多種可能之不固定資料，亦即將固定模組改為不確定性模組。以下針對每個例子執行所提之平面規劃演算法，其中程式中模擬退火之起始溫度設為50000，終止溫度設為10，降溫比率設為0.99。由圖2至6分別得到apte、xerox、hp、ami33及ami49五個測試電路最終平面圖寬度機率分佈、高度機率分佈及面積機率分佈之結果。其中apte電路面積期望值為48990924.0，面積變異數為3486808，執行時間約12秒xerox電路面積期望值為21921866.0，面積變異數為455168.96875，執行時間約12秒hp電路面積期望值為10698365.0，面積變異數為688040.8125，執行時間約13秒ami33電路面積期望值為1676856.0，面積變異數為12584.123047，執行時間約41秒ami49電路面積期望值為47764405.0，面積變異數為431305.2245，執行時間約98秒。由最終平面圖寬度機率分佈圖、高度機率分佈圖及面積機率分佈圖之結果可以清楚的看到寬/高/面積皆分佈在一定的範圍內且某些值具有相對較高機率值而某些值則具有相對較低機率值，這說明我們可採用具有較高機率值的數值結果來預測未來在不確定模組設計完成後所擺置形成的晶片平面圖較有可能的寬度/高度/面積大小。(a) (b)(c)圖2: apte實驗結果(a)(b)(c)圖3：xerox實驗結果(a)(b)(c)圖4：hp實驗結果(a)(b)(c)圖5：ami33實驗結果(a)(b)(c)圖6：ami49實驗結果五、結論在本論文中我們提出一個植基於群聚策略之不確定性模組之不可切割平面規劃演算法以便能有效的評估具有不固定維度/面積模組電路所形成平面圖之寬、高與面積之機率分佈。所提出的方法中，首先使用群聚技巧將模組兩兩聚集起來形成一些面積較大但個數較少的組合模組，接著採用Corner Block List 表示法來記錄組合模組間相對位置關係並在其上執行模擬退火程序以求得面積最佳化的結果。 除了面積之外，未來我們亦將於模組群聚時考慮網列連線長度及其分佈狀況，藉以求得具有較短網列連線長度及較低繞線擁擠程度的機率分佈圖。參考文獻1 K. Bazargan, S. Kim, and M. Sarrafzadeh (1998) “Nostradamus: A Floorplanner of Uncertain Design” Proceedings of the 1998 international symposium on Physical Design, Pages 18-23.2 Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, and Shu-Wei Wu (2000) “B*-Trees: A New Representation for Non-Slicing Floorplans” Proceedings of the 37th ACM/IEEE Design Automation Conference, Pages 458-463.3 Pei-Ning Guo, Chung-Kuan Cheng, and Takeshi Yoshimura (1999) “An O-tree Representation of Non-Slicing Floorplan and Its Applications” Proceedings of the 36th ACM/IEEE Design Automation Conference, Pages 268-273.4 Xianlong Hong, Gang Huang, Yici Cai, Jiangchun Gu, Sheqin Dong, Chung-Kuan Cheng, and Jun Gu (2000) “Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan” Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design, Pages 8-12.5 Jing Li, Tan Yan, Bo Yang, Juebang Yu, and Chunhui Li (2004) “A Packing Algorithm for Non-Manhattan Hexagon/Triangle Placement Design by Using An Adaptive O-Tree Representation” Proceeding of the 41th ACM/IEEE Design Automation Conference, Pages 646-651.6 J. M. Lin and Y. W. Chang (2001) “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans” Proceeding of the 38th ACM/IEEE Design Automation Conference, Pages 764-769.7 Changbo Long, Lucanus J. Simonson, Weiping Liao, and Lei He (2004) “Floorplanning Optimization with Trajectory Piecewise-Linear Model for Pipelined Interconnects” Proceedings of the 41th ACM/IEEE Design Automation Conference, Pages 640-645.8 Yuchun Ma, Sheqin Dong, Xianlong Hong, Yici Cai, Chung-Kuan Cheng, and Jun Gu (2001) “VLSI Floorplanning with Boundary Constraints Based on Corner Block List” Proceedings of Asia and South Pacific Design Automation Conference, Pages 509-514.9 Yuchun Ma, Xianlong Hong, Sheqin Dong, Yici Cai, Chung-Kuan Cheng, and Jun Gu (2001) “A Compact Algorithm for Placement Design Using Corner Block List Representation” Proceedings of the 4th ASIC Conference, Pages 146-149.10 Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, and Yoji Kajitani (1996) “VLSI Module Placement Based on Rectangle-Packing by the SequencePair” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 15, Issue 12, Pages 1518-1524.11 Shigetoshi Nakata, Kunihiro Fujuoshi, Hiroshi Murata, and Yoji Kajitani (1996) “Module Placement Based on BSG-Structure and IC Layout Applications” Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, Pages 484-491.12 R. H. J. M. Otten (1982) “Automatic Floorplan Design” Proceedings of the 19th ACM/IEEE Design Automation Conference, Pages 261-267.13 Peter G. Sassone and Sung K. Lim (2003) “A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning” Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design, Pages 74-80.14 Xiaoping Tang and D. F. Wong (2002) “Floorplanning with Alignment and Performance Constraints” Proceedings of the 39th ACM/IEEE Design Automation Conference, Pages 848-853.15 D. F. Wong and C. L. Liu (1986) “A New Algorithm for Floorplan Designs” Proceedings of the 23th ACM/IEEE Design Automation Conference, Pages 101-107.16 Hua Xiang, Xiaoping Tang, and D. F. Wong (2003) “Bus-Driven Floorplanning” Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design, Pages 66-73.17 吳彬玄、程仲勝 (2002) “降低電磁干擾之後置平面規劃器” Proceedings of the 2002 Taiwan Electromagnetic Compatibility Conference, Pages 172-175.18 吳彬玄、習存榮、程仲勝 (2003) “考慮電磁相容之超大型積體電路平面規劃之研究” Proceedings of the 2003 Taiwan Electromagnetic Compatibility Conference, Pages 78-83.12
展开阅读全文