頁籤選單縮合
題 名 | A Block Placement Algorithm for VLSI Cricuits=超大型積體電路之區塊擺置方法 |
---|---|
作 者 | 紀俊呈; 陳美麗; | 書刊名 | 中原學報 |
卷 期 | 31:1 2003.03[民92.03] |
頁 次 | 頁69-75 |
分類號 | 471.64 |
關鍵詞 | 平面規劃; 區塊擺置; 模組擺置; 序列對; 模擬退火法; Floorplan; Block placement; Module placement; Sequence pair; Simulated annealing; |
語 文 | 英文(English) |
中文摘要 | 本論文提出一個超大型積體電路之區塊(b1ock)擺 置(p1acement)方法。在超大型積體電路上通常包含定 形(hard)和不定形(soft)的模組(modu1e),本演算法使用 序列組(sequencepair)的表示法表示模組間的擺置關 係,並用模擬退火法(simu1atedannealing)得到一個最佳 的擺置。因為一個不定形的模組有許多可能的外形 (shape) ,所以在使用模擬退火法時必須花費較多的時 間才能找到一個好的解。我們提出了一個方法,在模 擬退火的過程中,對每個不定形模組找出四個可供選 擇的外形。這些候選的外形(candidateshape)提供了較 佳的機會可以得到區域最佳解(loca1optima1)。我們結 合了我們的方法及一個快速的序列組評估(sequence pair eva1uation)演算法[1] ,並且維持序列組評估演算法 的時間複雜度和原來的n10gn相同。在模擬退火的過 程中,我們可能會將一個定形的模組旋轉(rotate)、改 變一個不定形的模組的外形,或是交換序列組中兩個 模組的位置。本演算法已經被實現。應用於所有的 MCNC不定形模組擺置的測試範例(benchmark)上, ~目 較於先前的研究[2],我們可以在較短的執行時間內, 得到一組更為緊密(compact)的擺置。舉例而言,對 MCNC的測試範例ami49 '我們的演算法在440MHZ的 UltralO工作站上,花了142秒的時間,得到-~且具有 0.48%空白區域的擺置。而先前的研究使用Lagrangian re1axation的方式,在Pentium III 600MHZ的平台上, 花了2354秒的時間,得到一組具有7.7%空白區域的 擺置。 |
英文摘要 | A block placement algorithm for VLSI circuits is proposed. The circuits may contain both hard and soft modules. The algorithm uses simulated annealing framework based on the se quence pair representation. Because a 80ft module may have many possible shapes, so it will take long time to find a good solution in simulated annealing method. We proposed a method which finds four candidates of module shape to be chosen in a simulated annealing process for each module. These candidates provide a better choice toward local optimal packing. We combine our method with a fast sequence pair evaluation algorithm [1] and keep the same time complexity O(nlogn) of a sequence pair evaluation. During the simulated annealing process, it either chooses to rotate/change the shape of one module or to swap the modules in the sequence pair. We have implemented this algorithm. For all MCNC benchmark soft module floorplanning problems, we have obtained more compact floorplan with much less run time compared to a previous work [2]. For example, the MCNC benchmark ami49, our algorithm obtained 0.48% of dead space in 142 seconds using a 440 MHZ UltralO workstation. The previous work based on Lagrangian relaxation approach obtained 7.7% of dead space and 2354 seconds using a 600MHZ Pentium III processor. |
本系統中英文摘要資訊取自各篇刊載內容。