以SequencePair表示法處理不確定模組平面規劃問題(2005資通技術.docVIP

以Sequence Pair表示法處理不確定模組平面規劃問題 江昱麟 潘佳信 蔡宗達 程仲勝 摘要 在積體電路後端實體設計(physical design)中，平面規劃一直都是一個重要的議題。但隨著積體電路設計階層趨於複雜化，在實體設計階段時才考慮電路模組平面規劃問題無法將規劃結果立即回饋予前端系統階層設計者以便於修正其相對設計，因此我們考慮在前端系統階層設計時針對設計尚未完成之不確定模組進行平面規劃，而所得規劃結果可立即回饋予系統設計者以作為修正設計之參考。在本論文中我們採用Sequence Pair來表示不確定性模組間的拓樸關係，並利用模擬退火(simulated annealing)求得最終的面積評估。 關鍵字:實體設計、平面規劃、不確定性模組、模擬退火 一、簡介 VLSI後端實體設計階段(physical design phase)中的平面規劃(floorplanning)是整個階段的第一個步驟且是一個相當重要的步驟，其影響爾後其他步驟甚鉅，因此有許多方法被提出來解決平面規劃的問題[2-18]。平面規劃最主要的目的是放置一組電路模組(modules)於晶片上並使整體晶片面積為達到最小。平面規劃後所得之最終平面圖(floorplan)可以分成可切割(slicing)平面圖[10, 14]與不可切割(non-slicing)平面圖[2-9, 11-13, 16]兩大類，因此，平面規劃演算法可分為處理可切割[10, 14]與不可切割[2-9, 11-13, 16]平面結構兩大類。在處理可切割平面圖結構方面可用可切割樹(slicing tree)[10]和波蘭表示法(polish expression)[14]表示模組間位置的關係。而在不可切割結構方面則可用BSG (Bounded Sliceline Grid structure)表示法[8]、Sequence-Pair (SP)[7]表示法、O-Tree表示法[3]、B*-Tree[2]表示法、CBL(Corner Block List)表示法[4] 、TCG表示法[6]等來表示模組間相對位置關係。 隨著積體電路設計的複雜化，在實體設計階段時才考慮平面規劃問題已不能滿足系統設計需求，因此須在模組設計尚未完成前即考慮評估此種不確定模組對未來形成之晶片面積有何影響，進而修正系統階層之模組設計，使得整個系統設計趨於完善。然而除了文獻[1]提出以二元樹表示可切割之不確定模組平面規劃外，就我們所知以往並沒有其他關於解決不確定模組平面規劃問題之文章。因此在本論文中我們提出一個以Sequence Pair不可切割表示法[7]來處理不確定模組之平面規劃問題。在我們的方法中，首先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用Sequence Pair 表示法來記錄不確定模組間相對位置關係並在其上執行模擬退火(simulated annealing)程序以求得面積最佳化的結果。 二、傳統模組與不確定性模組 傳統後端實體設計平面規劃所處理的模組可分為：硬性模組（hard modules）與軟性模組（soft modules）兩種。每個硬性模組只有一組長、寬，硬性模組在平面規劃時藉由旋轉有兩種擺放方式。軟性模組並沒有固定的長或寬，只有固定的面積與長寬比（aspect ratio），因此並不會像硬性模組一樣只有兩種擺放可能性。但為了平面規劃處理上的方便，之前研究多使用多組長、寬來處理軟性模組的擺放問題。然而在前端系統階層平面規劃所處理的模組則稱之為不確定模組(uncertain modules)。不確定模組不但沒有固定的長寬維度，亦無固定的面積，且針對每種可能的長/寬/面積，皆有其相對的機率值以表示未來模組設計完成後維度大小之可能性。我們將不確定性模組分為兩種：高不確定性模組與低不確定性模組。其中高不確定性模組定義為每一組高或寬中相對機率最高低於70%，而低不確定性則定義為每一組高或寬中相對機率最高在70%以上。 三、Sequence Pair表示法 自從1996年 H. Murata 發表 Sequence-Pair[7] 以來，Sequence-Pair就成為不可切割平面規劃中最常被使用的表示法。顧名思義Sequence-Pair是由兩串數列所建構而成，這兩串數列的每一個元素皆代表一個模組，而每個模組在兩數列中剛好各出現一次。Sequence-Pair則透過模組在兩串數列中的相對位置，來判斷兩兩模組之間的拓樸關係。在判斷完模組之間的拓樸關係之後，可依其拓樸關係得到水平拓樸圖形（horizontal topological graph）與垂直拓樸圖形（vertical topological graph），我們分別在水平拓樸圖形的左右與垂直拓樸圖形的上下預設兩個虛擬點：原點與終點，以兩串