以CornerBlockList表示法处理植基於群聚策略之不确定性模组平面.doc

PAGE PAGE 11 以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；經不確定模組平面規劃處理後可