顏嗣鈞臺灣大學：電機工程學研究所吳國勝Wu, Kuo-ShengKuo-ShengWu2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53101超大型積體電路(VLSI)的快速發展，目前已經進展到深次微米(deep sub-micron)的程度。在深次微米的設計中，由於供應電源電壓(supply voltage)的減低，要使電路能夠正常且有效率地運作，維持穩定且充足的電源供應(power supply)成為一個首要需要考慮的議題。在傳統的設計流程中，電源供應規劃一直到最後繞線(routing)的階段才受到考慮；在最後的階段才做規劃，容易導致可變動的空間少、可修改的彈性有限，某些問題也許無法被解決，必須退回前幾個階段重新做設計，浪費時間與人力。 另外，在平面規劃(floorplaning)階段，工程師常會為了某些特殊的需求，而將某些模組區塊擺放於特定的位置，例如：將有資料相關性的區塊擺放成一排或將某些區塊靠邊擺放；這些限制即為擺放限制(placement constraints)，其中包括了：隊列限制(alignment constraint)、毗鄰限制(abutment constraint)、預先放置(pre-place)、範圍限制(range constraint)、邊界限制(boundary constraint)、及叢集限制(clustering)等。我們採用以序列配對(sequence pair)的表示方法，來處理一般的Non-slicing平面規劃問題。 本文主要探討：以擺放限制為基礎，同時考慮電路區塊功率消耗分佈之平均性的平面規劃問題。將電路區塊所需消耗的功率均勻地擺放，以期能減少因為功率需求過於擁擠，而造成供給電源不足(insufficient power supply)或區域性過熱(local hot spot)等問題，影響電路正常的運作。摘要 4 第一章 序論 5 1.1 平面規劃於超大型積體電路之實體設計 7 1.2 相關研究 10 1.3 問題定義 12 1.3.1 擺放限制 12 1.3.2 功率分佈 14 1.3.3 擺放限制+功率分佈 15 1.4 論文架構 16 第二章 理論基礎 17 2.1 SLICING/NON-SLICING平面規劃 17 2.2 序列配對 (SEQUENCE PAIR) 18 2.3 限制圖形 (CONSTRAINT GRAPHS) 19 2.4序列配對+限制圖形 20 2.5 使用限制圖形處理模組擺放限制 22 2.5.1 隊列限制 (alignment constraint) 22 2.5.2 毗鄰限制 (abutment constraint) 23 2.5.3 預先放置 (pre-place) 24 2.5.4 範圍限制 (range constraint) 25 2.5.5 邊界限制 (boundary constraint) 26 2.5.6 叢集限制 (clustering) 27 2.6 電源幫浦 28 第三章 演算法 29 3.1 BELLMAN-FORD ALGORITHM 30 3.1.1使用Bellman-Ford Algorithm找出各節點座標 31 3.2 SIMULATED ANNEALING ALGORITHM 32 3.2.1 序列配對中的移動方式(Moves) 34 3.2.2 考慮功率分佈 36 3.2.3 Multi-Stage Simulated Annealing 38 3.2.4 新的成本函數 39 3.2.5 標準化成本函數 41 3.3 程式流程圖 42 第四章 實驗結果 43 4.1 APTE 45 4.2 XEROX 46 4.3 HP 47 4.4 AMI33 48 4.4.1 ami33 (divide 4 power regions) 48 4.4.2 ami33 (divide 9 power regions) 50 4.5 AMI49 52 4.5.1 ami49 (divide 4 power regions) 52 4.5.2 ami49 (divide 9 power regions) 54 4.6 綜合比較 56 第五章 結論 58 第六章 參考文獻 591269311 bytesapplication/pdfen-US平面規劃floorplanningthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53101/1/ntu-94-R92921098-1.pdf