(3.236.175.108) 您好!臺灣時間:2021/03/01 11:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林益廣
研究生(外文):Yi-Kuang Lin
論文名稱:以直交退火演算法解VLSI之平面規劃問題
論文名稱(外文):Orthogonal Simulated Annealing for Floorplanning
指導教授:何信瑩
指導教授(外文):Shinn-Ying Ho
學位類別:碩士
校院名稱:逢甲大學
系所名稱:資訊工程所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:50
中文關鍵詞:平面規劃退火演算法直交實驗設計
外文關鍵詞:orthogonal experimental designFloorplanningsimulated annealing algorithm
相關次數:
  • 被引用被引用:4
  • 點閱點閱:139
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:0
摘 要
平面規劃在超大型積體電路實體設計中是一個重要的步驟。平面規劃問題在於如何擺設一組給定電路模組,使其組合出的晶片面積達到最小。現有的方法中以序對表示法描述模組的放置加上使用退火演算法來找尋最佳解,所得答案最好。其所用的退火演算法,每一迭代只對現有解產生一個擾亂運算,係採用亂數隨機產生與測試的方法產生新解。本文提出直交退火演算法,它可系統化地對現有的解產生一組含有多個擾亂運算的可能解,藉由直交實驗的因素分析,從這一組可能解中推理出含有多個擾亂運算的一個更佳的新解。直交實驗對於交互性較小的實驗因子會有較佳的系統化推理能力,因此本文分析各種擾亂運算的特性,設計出適合直交實驗的擾亂運算。實驗MCNC與GSRC的標準測試問題,結果顯示本論文所提出方法可以有效提升現有方法之效能,尤其是在解大型的平面規劃問題。
Abstract
Floorplanning is an essential step in physical design of VLSI. The floorplanning is how to place a set of circuit modules on a chip such that the resulting area is minimized. The best solutions are obtained using simulated annealing based on sequence pair representing the planning of modules. The used simulated annealing conducts a random perturbation operation on the current to generate a candidate solution for each iteration. This paper proposes an orthogonal simulated annealing algorithm which systematically generate a set of candidates containing a number of perturbation operations and consequently reason a good solution bases on orthogonal experimental design. Between experimental factors have lower interaction in an orthogonal experimental design, that have higher perform to consequently reason. So we analyze perturbation operations and design the appropriate perturbation operation for using an orthogonal simulated annealing algorithm. Results of experiments in the MCNC and GSRC benchmark show that our method can effective improve efficacy of current methods, especially in the lager floorplaning.
目錄
中文摘要.………………………………………………………………………………I
英文摘要.………………………………………………………………………………II
圖目錄.…………………………………………………………………………………V
表目錄.………………………………………………………………………………VII
第 一 章 導 論.…………………………………………………………………………1
1.1 研究背景與動機.……………………………………………………………………1
1.2 研究目的.……………………………………….…………………………………1
1.3 論文架構.…………………………………………………………………………2
第二章 平面規劃的表示法的文獻回顧.………………………………………………3
2.1 Slicing Tree.………………………………………………………………………3
2.2 O-tree表示法.………………………………………………………………………5
2.3 B*-tree表示法.………………………………………………………………………5
2.4 序對(sequence pair)表示法.…………………………………………………………6
第三章 直交退火演算法( Orthogonal Simulated Annealing ,OSA) .………9
3.1 退火演算法.…………………………………………………………9
3.1.1 梯度搜尋法.………………………………………………………………9
3.1.2 機率函數.…………………………………………………………………9
3.1.3 退火演算法之流程…………………………………………………..…10
3.2 直交實驗設計.………………………………………………………………12
3.2.1 因素分析.……………………………………………………………………15
3.3直交退火演算法.……………………………….………………………………16
3.3.1 影響退火演算法效能之因素.………………………………………………16
3.3.2 直交退火演算法搜尋能力分析……………………………………………17
3.3.3 智慧型新解產生步驟.………………………………………………………20
3.3.4 直交退火演算法步驟.………………………………………………………20
第四章 以直交退火演算法解平面規劃問題.…………………………………………23
4.1 擾亂的機制.……………………………………………………………………21
4.1.1 序對(Sequence pair)的擾亂方式.…………..……………………………24
4.1.2 設計合適的擾亂方式.…………………….………………………………27
4.1.3 使用IGM的交會擾亂例子………….………………………..……………30
4.2 平面規劃演算法…………………….…………………………………………32
第五章 實驗結果與分析.………………………………………………………………34
5.1實驗一:考慮旋轉角度與差異度的交換擾亂的實驗……………….……………34
5.2實驗二:各擾亂機制與 OSA結合實驗…………………………….……………36
5.3實驗三:實驗驗證推理解的效能..…….…………………………….……………38
5.4實驗四:直交實驗與三種擾亂運算對解的影響….………………….……………38
5.5實驗五:實驗變異因數的設定…………………...………………….……………41
5.6實驗六:benchmark實驗數據….…………………………………….……………43
第六章 結論.…………………………………………………………………………46
參考文獻.……………………………………………………………………………….47
[1] D. F. Wong and C. L. Liu, “A new algorithm for floorplan design,” in Proc. ACM/IEEE Design Automation Conf., pp. 101—107 , 1986.[2] M. Lai and D.F. Wong, “Slicing tree is a complete floorplan representation,” in Proc. Design, Automation and Test in Europe Conf., pp. 228—232, 2001.[3] Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu, “B*-trees: a new representation for nonslicing floorplans,” in Proc. Design Automation Conf., pp. 458—463, 2000.[4] P. N. Guo, C. K. Cheng, and T. Yoshimura, “An O-tree representation of nonslicing floorplans and its applications,” in Proc. Design Automation Conf., pp. 268—273, 1999.[5] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence pair,” IEEE Trans. Computer-Aided Design, vol. 15, pp. 1518—1524, 1996.[6]. M. Rebaudengo and M. S. Reorda, “Floorplan area optimization using genetic algorithms, ” in proc. Design Automation of High Performance VLSI Systems, pp. 22-25, 1994.[7] N. Mani and B. Srinivasan, “Using genetic algorithm for slicing floorplan area optimization in circuit design,” in Proc. Int. Conf. Computational Cybernetics and Simulation, pp. 2888-2892, 1997.[8] M. Rebaudengo and M.S. Reorda, “GALLO: a genetic algorithm for floorplan area optimization,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 8, pp. 943—951, 1996.[9] J.P. Cohoon, S.U. Hegde, W.N. Martin, and D.S. Richards, “Distributed genetic algorithms for the floorplan design problem,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 4, pp. 483—492, 1991.[10] D.F. Wong and T. Xiaoping, “FAST-SP: a fast algorithm for block placement based on sequence pair,” in Proc. Design Automation Conf., pp. 521—526, 2001.[11] T. Xiaoping, T. Ruiqi, and D.F. Wong, “Fast evaluation of sequence pair in block placement by longest common subsequence computation,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 12, pp. 1406—1413, 2001.[12] L.P.P.P. van Ginneken and R.H.J.M. Otten, “Optimal slicing of plane point placements,” in Proc. Design Automation Conf., pp. 322-326, 1990.[13] S.N. Adya and I.L. Markov, “Fixed-outline floorplanning through better local search Computer Design, ” in Proc. Int. Conf. Computer Design, pp. 328—334, 2001.[14] T. Ohmura, K. Fujiyoshi, and C. Kodama, “Area optimization of packing represented by sequence-pair,” in Proc. Circuits and Systems Conf., pp. 813—816, 2000.[15] C. Lin, “A more efficient sequence pair perturbation scheme,” in Proc. ProRISC99, pp. 295-300, 1999.[16] K. Kiyota and K. Fujiyoshi, “Simulated annealing search through general structure floorplans using sequence-pair,” in Proc. Circuits and Systems, vol.3, pp. 77 -80, 2000.[17] S. H. Park, Robust Design and Analysis for Quality Engineering. Chapman & Hall, 1996[18] M. S. Phadke, Quality Engineering Using Robust Design. Englewood Cliffs. NJ: Prentice-Hall, 1989[19] http://www.cse.ucsc.edu/research/surf/GSRC/progress.html
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔