1、以Sequence Pair表示法處理植基於群聚策略之不確定性模 組平面規(guī)劃問題江昱麟 潘佳信 蔡宗達 程仲勝大葉大學電機工程學系彰化縣大村鄉(xiāng)山腳路 112 號摘要在積體電路後端實體設計(physical design)中，平面規(guī)劃一直都是一 個重要的議題。但隨著積體電路設計階層趨於複雜化，在實體設計階段 時才考慮電路模組平面規(guī)劃問題已無法將規(guī)劃結果立即回饋予前端系 統(tǒng)階層設計者以便於修正其相對設計 ，因此我們考慮在前端系統(tǒng)階層設 計階段模組尚未設計完成時之不確定性模組平面規(guī)劃問題 ，探討針對維 度大小不固定之模組如何進行未來平面規(guī)劃的評估 。在本論文中我們提 出一個植基於群聚(cluster

2、ing)策略之不確定模組平面規(guī)劃演算法以便 能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首先給 定每一個模組幾組不同的寬與長及其相對應之機率 ，接著採用群聚技巧 將模組聚集起來形成一些面積較大但個數(shù)較少的組合模組(supermodules)最後以SequencePair表示法來記錄組合模組間相對位 置關係並在其上執(zhí)行模擬退火(simulated ann eali ng)程序以求得不確定模組所形成的最終晶片寬、高與其面積之機率分佈圖。關鍵字:實體設計、平面規(guī)劃、不確定性模組、模擬退火、群聚1以Sequence Pair表示法處理植基於群聚策略之不確定性模組平面規(guī)劃問題一、簡介VLSI

3、後端實體設計階段(physical design phase中的平面規(guī)劃(floorplanning)是整個階段的第一個步驟且是一個相當重要的步驟，其影響爾後其他步驟甚鉅， 因此有許多方法被提出來解決後端實體設計階段平面規(guī)劃的問題2-18。平面規(guī) 劃最主要的目的是放置一組電路模組(modules)於晶片上並使整體晶片面積達到最小。平面規(guī)劃後所得之最終平面圖(floorplan)可以分成可切割(slidng)平面圖12, 15與不可切割(non-slicing)平面圖2-11,13, 14, 16, 17兩大類。因此，平面規(guī)劃演 算法亦可分為處理可切割12, 1 5與不可切割2-11, 13,

4、14, 16, 17平面結構兩大 類。在處理可切割平面結構方面可用可切割樹(slicing tree)12和波蘭表示法(polish expression)15表示模組間位置的關係。而在處理不可切割平面結構方面 則可用BSG (Bounded-Sliceline Grid)表示法11、Sequence-Pai表示法10、O-Tree表示法3、B*-Tree表示法2、CBL(Corner Block List)表示法4及TCG(TransitiveClosure Graph康示法等來表示模組間相對位置關係。隨著積體電路設計的複雜化，在實體設計階段時才考慮平面規(guī)劃問題已不能 滿足系統(tǒng)設計需求，因此

5、須在模組設計尚未完成前即考慮評估此種不確定模組對 未來形成之晶片面積有何影響，進而修正系統(tǒng)階層之模組設計，使得整個系統(tǒng)設 計趨於完善。然而除了文獻1提出以二元樹表示可切割之不確定模組平面規(guī)劃 外，就我們所知以往並沒有其他關於解決不確定模組平面規(guī)劃問題之文章。因此 在本論文中我們提出一個以SequencePair不可切割表示法10來處理不確定模 組之平面規(guī)劃問題。在我們的方法中，首先給定每一個模組幾組不同的寬與長及 其相對應之機率，接著採用群聚技巧將模組聚集起來形成一些面積較大但個數(shù)較 少的組合模組(supermodules，最後以SequencePair表示法來記錄組合模組間相 對位置關係並在

6、其上執(zhí)行模擬退火(simulated ann eali ng程序以求得面積最佳化的結果。二、SequenceSequence PairPair 表示法由於我們所提出解決平面規(guī)劃的方法是以Sequence Pair表示法10為基 礎，因此以下將簡要說明Seque nee Pair表示法如何記錄模組間相對位置關係。Sequence-Pai是由兩串數(shù)列所建構而成，這兩串數(shù)列的每一個元素皆代表一個模 組，每個模組在任一數(shù)列中恰好出現(xiàn)一次。Seque nce-Pai表示法透過模組在兩串 數(shù)列中的相對位置，來判斷模組間的拓樸關係。我們假設這兩串數(shù)列為(r +,r)，並假設任意兩模組為b1與b2，則必定滿足

7、以下式子中的其中一個：(1)+=(b2b1)，r=(b1b2)，則b2在b1的上方。(2)+=(b1b2)，r=(b2b1)，則b2在b1的下方。2(3)+=(b2bi),r=(b2bi)，則b2在bi的左邊。(4)+=(心b),r= (bb2),則b2在bi的右邊。由上可知在Sequenee Pa表示法中的任兩個模組，都有著唯一的拓撲關係。 在判斷完模組之間的拓樸關係之後，可得到兩個拓樸圖形，分別為水平拓樸圖形(horiz on taitopological graph)與垂直拓樸圖形(vertical topological graph)。圖1以(r+,卩)=(b5b4bib3b2), (

8、bib4b5b2b3)為例，其水平拓樸圖形與垂直拓樸圖形分別顯示 在圖1(a)及1(b)。(b)垂直拓樸圖形圖1: Seque nee Pai表示法所得之拓樸圖形得到模組之間的拓撲關係後，我們將模組的長、寬分別設為水平與垂直拓樸 圖形中路徑的長度，再經(jīng)過最長路徑演算法分別算出從兩拓樸圖形之圖形原點到 每一個點的最長路徑，即可計算出最終平面圖，以圖1為例，若各模組長寬分別為59, 5，b25, 3，b35, 9，b45, 4，b59, 3，則圖2為其最終平面圖。b5b3b4b1b2圖2:圖1相對應之最終平面圖(a)水平拓樸圖形b3b23二、兩階段不確定模組平面規(guī)劃在本論文中我們提出一個植基於群聚

9、(clusteri ng)策略之不確定模組平面規(guī)劃演算法以便能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首 先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用群聚技巧將模 組聚集起來形成一些面積較大但個數(shù)較少的組合模組(supermodules),最後以Seque nee Pair表示法來記錄組合模組間相對位置關係並在其上執(zhí)行模擬退火(simulatedann eali ng程序以求得不確定模組所形成的最終晶片寬、高與其面積之 機率分佈圖。3.13.1 問題描述不確定模組之平面規(guī)劃即是在模組彼此不重疊的限制下擺置一組不確定電 路模組，其中令B =bi, b2,，bn為欲擺置

10、之n個不確定寬與高之矩形模組集 合，而第i個模組bi之寬、高可能值及其相對應之機率值分別為(wii, Pwii), (wi2, Pwi2),與(hii, Phii), (hi2, Phi2),，其中Pwik(Phik)為可能寬(高)值wik(hik)相對 應之機率值，且Pwii+Pwi2+=1及Phii+Phi2+=1;經(jīng)不確定模組平面規(guī)劃處 理後可得到最終平面圖之寬與高機率分佈圖，分別為(wi, Pwi), (W2, PW2),與(hi, Phi), (h2, Ph2)，其中Pwi+Pw2+=i且Phi+Ph2+=1。3.23.2 群聚我們採取由下往上(bottom up)模組兩兩結合之階層

11、式群聚策略。假設我們所 要群聚的模組為模組bi與模組b2,則會存在四種不同的結合方式，如圖3所示分別為：(i)模組bi不旋轉(zhuǎn)，模組b2不旋轉(zhuǎn)，(2)模組bi不旋轉(zhuǎn)，模組b2旋轉(zhuǎn)，(3)模組bi旋轉(zhuǎn)，模組b2不旋轉(zhuǎn)，模組bi旋轉(zhuǎn)，模組b2旋轉(zhuǎn)，圖中的H代表模組的高，W代表模組的寬，而A則代表模組的面積。bi-1 II iIib2-W=Wi+W2Ai=WiXHiH=Hior H2A2=W2和2W=Wi+H2Ai=WiHiH=Hior W2A2=W2H2A=W H閒置空間=A-(Ai+A2)(b)Wi+W2Wi+H24圖3:模組結合的四種不同狀況我們將兩模組之間的四種狀況分別記錄下來，加以分析四種狀

12、況下的優(yōu)缺 點，而目前我們選擇閒置空間最小的一種組合來做群聚的動作。接著我們說明演 算法中由下往上階層式模組群聚的步驟： 步驟i:設f=a*W+B*W2,其中Wi及W2分別表示所形成組合模組之長寬差值 及閒置空間大小，a及B則為其權重值。(a)任找一模組bi,使其與模組b2形成一組合模組，其中模組為所有模 組中與模組bi群聚後可產(chǎn)生最小f值者。(注意：任兩模組群聚後之f值取其4種組合中f值最小者)。(b)將已群聚之模組移除，對剩下尚未群聚之模組重複步驟(a)及(b)直到所有模組皆已群聚。步驟2:將步驟i完成後之組合模組重新視為一般模組並重複步驟i及步驟2直至達到預設之群聚階層數(shù)。3.33.3

13、SequenceSequence PairPair 為主之不確定模組平面規(guī)劃以Sequenee Pair表示法為主之不確定性模組平面規(guī)劃在判斷出不確定模組 間拓樸關係之後，與確定性模組的平面規(guī)劃一樣必須使用最長路徑演算法分別計 算水平拓樸圖形與垂直拓樸圖形從圖形原點到每一個點的最長路徑，但有別於確 定性模組的平面規(guī)劃，在執(zhí)行最長路徑演算法後，不確定性模組的平面規(guī)劃所得 到的是許多可能長度與機率的組合。另外，當在計算最長路徑時，如有兩條或兩 條以上的路徑連接到某節(jié)點時，傳統(tǒng)的最長路徑演算法只要比較出那一條路徑較 長，及可找出該節(jié)點的最長路徑，但在處理不確定性模組的最長路徑時，路徑不 再只是單純的

14、長度，而是多考慮了機率，因此必須比較出所有連到該節(jié)點路徑長 度與機率組合，加入該節(jié)點模組本身長、寬機率組合，以計算出該節(jié)點可能的最 長路徑與機率組合。經(jīng)一次不確定模組平面規(guī)劃處理後可得到平面圖之寬/高/面積機率分佈圖，b2WbiH什H2W=H1+H2Ai=WiXHiH=W1or W2A2=W2XH2A=W H閒置空間=A-(Ai+A2)(c)W=Hi+W2Ai=WiXHiH=Wior H2A2=W2XH2A=W H閒置空間=A-(Ai+A2)(d)bib2HiHi+W25接著執(zhí)行模擬退火程序直至模退溫度降至預設冰點以求得較準確的寬/高/面積機率分佈圖。其中模退程序中相鄰解可由以下幾種交換Seq

15、uence Pair兩串列中的 元素來達成:方法一：在第一串數(shù)列中任意選取兩個模組交換位置 方法二：任意選取兩模組並在第一串數(shù)列與第二串數(shù)列皆交換位置 方法三：任意交換一模組的長與寬四、實驗結果在本論文中使用PC為實驗平臺，其CPU時脈為1.5GHz，記憶體為384MB, 使用編譯軟體為Microsoft Visual C+ 6.0。 實驗所用的benchmarkS取至MCNC包含 即te xerox、hp、ami33及ami49。在本次的實驗中，針對benchmarks模組的資料 做了一點修改以符合不確定模組之平面規(guī)劃問題 ，其中將有些模組原本固定維度 的資料改為具有多種可能之不固定資料，亦

16、即將固定模組改為不確定性模組。以下針對每個例子執(zhí)行所提之平面規(guī)劃演算法 ，其中程式中模擬退火之起始 溫度設為20000C，終止溫度設為C,降溫比率設為0.995。模擬退火的目標函 數(shù)設為面積期望值與面積變異數(shù)之和。由圖4至8分別得到apte、xerox、hp、ami33及ami49五個測試電路最終平面圖寬度機率分佈、高度機率分佈及面積機率分佈 之結果。表1則顯示每個電路平面規(guī)劃執(zhí)行時間，面積期望值與面積變異數(shù)。由最終平面圖寬度機率分佈圖 、高度機率分佈圖及面積機率分佈圖之結果可 以清楚的看到寬/高/面積皆分佈在一定的範圍內(nèi)且某些值具有相對較高機率值 而某些值則具有相對較低機率值 ，這說明我們可

17、採用具有較高機率值的數(shù)值結果 來預測未來在不確定模組設計完成後所擺置形成的晶片平面圖較有可能的寬度/高度/面積大小。圖4: apte寬、高、面積機率分佈圖6寬機率分佈width高機率分佈height面積機率分佈area6 5 4 3 2 104589oo o o o O aa a a a a7寬機率分佈width高機率分佈0866 2H06 4066 6206 5A&OAL 59POeeh 08562056-C6ODO0PO Z756- 4430面積機率分佈0.05yb 0.06b0.04j 0.02血一JlC04135930442nu0UHW3C6422T1232圖5: xerox寬

18、、高、面積機率分佈圖圖6: hp寬、高、面積機率分佈圖8寬機率分佈width高機率分佈height0.080.060.040.020.1面積機率分佈area圖7: ami33寬、高、面積機率分佈圖9寬機率分佈屛819帶屛0 0的屛8610.80.60.40.2width高機率分佈height面積機率分佈0.8y0.6b0.4 p0.27CMy5o20696area圖8: ami49寬、高、面積機率分佈圖10寬機率分佈P5264528653425364width高機率分佈height面積機率分佈3 5 2 5 15 0 0.200Q o o Oarea11表1:實驗結果統(tǒng)計圖aptexeroxh

19、pami33ami49Time(sec)4465253面積期望值53845888 22701164108958771584646.2559802636面積變異數(shù)948055.312317581.5199183.707440.591468529.75五、結論在本論文中我們提出一個植基於群聚策略之不確定性模組之不可切割平面 規(guī)劃演算法以便能有效的評估具有不固定維度/面積模組電路所形成平面圖之寬、高與面積之機率分佈。所提出的方法中，首先使用群聚技巧將模組兩兩聚集 起來形成一些面積較大但個數(shù)較少的組合模組，接著採用SequencePair表示法來記錄組合模組間相對位置關係並在其上執(zhí)行模擬退火程序以求得

20、面積最佳化 的結果。參考文獻1K. Bazarga n, S. Kim, and M. Sarrafzadeh (1998)“NostradaplaisnerFloof Uncertain Design ” Proceedings of the 1998 international symposium on PhysicalDesign Pages 18-23.2Yun-Chih Cha ng, Yao-We n Cha ng, Gua ng-Mi ng Wu, and Shu-Wei Wu (2000)“IB-Trees: A New Representationfor Non-Slicin

21、g Floorplans Proceedings of the37thACM/IEEE Design Automation Conference, Pages 458-463.3Pei-Ni ng Guo, Chu ng-Kuan Che ng, and Takeshi Yoshimura (1999) An O-treeRepresentationof Non-Slidng Floorplan and Its Applications”Proceedings of the36)hACM/IEEE Desig n Automation Co nferen ce, Pages 268-273.4

22、Xianlong Hong, Gang Hua ng, Yici Cai, Jia ngch un Gu, Sheq in Dong, Chu ng-Kua nChe ng, and Jun Gu (2000) Corner Block List: An Effective and Efficie nt TopologicalReprese ntati onof Non-Slici ng Floorpla n”Proceed in gsof the 2000 IEEE/ACMInternational Conference on Computer-Aided Design,Pages 8-12

23、.Jing Li, Tan Yan, Bo Yang, Juebang Yu, and Chunhui Li (2004) A Packing Algorithmfor Non-Man hatta n Hexag on /Tria ngle Placeme nt Desig n by Usi ng AnthAdaptive O-Tree Representatio6 Proceeding of the 41 ACM/IEEE DesignAutomation Conference, Pages 646-651.J. M. Lin and Y. W. Cha ng (2001)“TCGA Tra

24、n sitive Closure Graph-Basedth12Representationfor Non-Slicing Floorplans P”roceeding of the 38thACM/IEEEDesign Automation Conference, Pages 764-769.7Changbo Long, Lucanus J. Simonson, Weiping Liao, and Lei He (2004)“Floorplanning Optimization with Trajectory Piecewise-Linear Model for PipelinedInter

25、connects”Proceedings of the 41thACM/IEEE Design Automation Conference,Pages 640-645.8Yuchun Ma, Sheqin Dong, Xianlong Hong, Yici Cai, Chung-Kuan Cheng, and JunGu (2001) VL“SI Floorplanning with Boundary Constraints Based on Corner BlockList”Proceedings of Asia and South Pacific Design Automation Con

26、ference, Pages509-514.9Yuchun Ma, Xianlong Hong, Sheqin Dong, Yici Cai, Chung-Kuan Cheng, and JunGu (2001) A C“ompact Algorithm for Placement Design Using Corner Block ListRepresentation”Proceedings of the 4thASIC Conference, Pages 146-149.10 Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake,

27、and Yoji Kajitani (1996)“VLSI Module Placement Based on Rectangle-Packing by the SequencPair”EE Transactions on Computer-Aided Design of Integrated Circuits andSystems, 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-AidedDesign,Pages 484-491.12 R. H. J. M. Otten (1982)“Automatic Floorplan DPersoicgenedings”of the19thACM/IEEE Design Automation Conference, Pages 261-267.13 Peter