以CornerBlockList表示法处理不确定模组之平面规划问题潘佳信[1.docVIP

以Corner Block List表示法處理不確定模組 之平面規劃問題 潘佳信 江昱麟 蔡宗達 程仲勝 大葉大學電機工程學系 彰化縣大村鄉山腳路112號 摘要 隨著VLSI/SOC的蓬勃發展，如何在電路模組尚未設計完成時評估這些面積及長寬維度皆不確定模組在未來後端實體設計階段(physical design phase)所形成晶片面積大小是相當重要的議題。對於絕大多數先前研究而言，只評估由具有固定面積甚至具有固定長寬之確定性模組所形成之晶片面積，而對於不確定模組的平面規劃問題則未有著墨。因此在本論文中我們提出一個不確定模組平面規劃演算法以便能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用Corner Block List 表示法來記錄不確定模組間相對位置關係並在其上執行模擬退火(simulated annealing)程序以求得面積最佳化的結果。由實驗結果得知，對於每個例子我們可以得出不確性模組所形成的最終晶片寬、高與其面積之機率分佈圖，藉此評估尚未設計完成之電路模組在未來所形成可能之晶片面積大小。 關鍵詞: 實體設計、不確定模組、平面規劃、模擬退火 以Corner Block List表示法處理不確定模組 之平面規劃問題 一、簡介 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]來處理不確定模組之平面規劃問題。在我們的方法中，首先給定每一個模組幾組不同的寬與長及其相對應之機率，接著採用Corner Block List 表示法來記錄不確定模組間相對位置關係並在其上執行模擬退火(simulated annealing)程序以求得面積最佳化的結果。 二、問題描述與CBL表示法 不確定模組之平面規劃即是在模組彼此不重疊的限制下擺置一組不確定電路模組，其中令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串列紀錄每一個模組與其他相