跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/27 13:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:簡宗宇
研究生(外文):Jong-Yu Jen
論文名稱:在CUDA架構下對大量模組進行平面規劃的方法
論文名稱(外文):An Approach for Floorplanning Massive Modules Based on CUDA Architecture
指導教授:方志鵬方志鵬引用關係張陽郎張陽郎引用關係
口試委員:陳泰蓁宋國明
口試日期:2012-07-03
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:電機工程系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:60
中文關鍵詞:平面規劃模擬退火法切割法非切割法放鬆波蘭式制約最長共同子序列
外文關鍵詞:FloorplanningSimulated AnnealingSlicingNon-slicingRelaxed Polish expressionConstrained Longest Common Subsequence
相關次數:
  • 被引用被引用:0
  • 點閱點閱:180
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
用於超大型積體電路平面規劃的表示法有兩種:切割法與非切割法。切割法只能表達切割結構,而非切割法可以表達切割或非切割結構。但有幾個原因使切割法仍具有存在的價值:1、容易實作;2、以切割法得出的電路平面仍需以切割法維護;3、使用事後壓縮的方式一樣可以得出非切割結構的電路平面。
我們提出放鬆波蘭表示式,以O取代H及V來放鬆對平面切割方向的限制。另外,我們還提出局部最佳合併的演算法來搭配放鬆波蘭式,除此之外,我們更利用了GPU進行了平行運算,最後以制約式最長共同子序列進行計算,將切割結構轉換成非切割結構。
本研究以GSRC與MCNC Benchmark做為測試電路。實驗結果顯示所提出的方法的確能有效加快計算的速度,所提出的平行化模擬退火演算法,使結果更佳,而制約式最長共同子序列則可以快速將切割結構轉換成非切割結構。


The methods to represent a floorplan of VLSI can be classified as slicing and non-slicing. The non-slicing method can express slicing structure as well as non-slicing structure while the slicing method can express slicing structure only. However, there are reasons that make the slicing method survive: (1) Slicing method is simple in terms of implementation; (2) A floorplan designed with slicing method should be maintained accordingly; (3) After compression, a slicing flooplan becomes a non-slicing floorplan.
Instead of ‘H’ and ‘V’, we use ‘O’ in our relaxed Polish expression to relax the constrained on the orientation of cut. In addition, we propose a greedy merging algorithm to work with the proposed relaxed Polish expression. Further, we use GPU to perform parallel computation. Finally, we use constrained longest common subsequence to convert a slicing structure to a non-slicing structure.
GSRC and MCNC Benchmarks are used as test circuits in our experiments. The experimental results show that our approach significantly accelerated the speed of calculation, and the proposed parallel simulation annealing algorithm make the results better, while the constrained longest common subsequence can efficiently convert a slicing structure to a non-slicing structure.

摘 要 I
Abstract II
誌謝 III
目錄 Ⅳ
表目錄 Ⅵ
圖目錄 Ⅶ
第一章 緒論 1
1.1研究背景與介紹 1
1.2研究動機與目的 2
1.3論文貢獻與架構 2
第二章 相關文獻與回顧 3
2.1結構表示法 4
2.2最佳化演算法 4
2.3 CUDA架構 5
第三章 研究方法 6
3.1概述 6
3.2放鬆波蘭表示法(Relax Polish Expression) 6
3.2.1 原理與簡介 7
3.2.2 理論 8
3.3局部最佳合併 9
3.3.1原理與簡介 10
3.3.2理論 12
3.4整體演算法之流程 14
3.5選擇限定寬高比例的較佳解 15
3.5.1原理、簡介、理論 15
3.5.2演算法之流程 17
3.5.3平行架構 18
3.6模擬退火法(Simulated Annealing) 20
3.6.1原理、簡介、理論 21
3.6.2演算法之流程 22
3.6.3平行架構 23
3.7壓縮 25
3.7.1序列對與快速最長共同子序列之理論 26
3.7.2演算法之流程 29
3.7.3平行架構 32
第四章 實驗結果 33
4.1實驗環境 33
4.2實驗結果 33
第五章 結論與未來展望 35
5.1 結論 35
5.2 未來展望 35
參考文獻 36
附錄 38


[1]NaveedSherwani, Algorithms for VLSI Physical Design Automation, 3th Ed., KAP.
[2]Sadiq M. Sait, Habib Youssef, VLSI Physical Design Automation: Theory and Practice, Word Science, 2006.
[3]D. F. Wong, and C. L. Liu, “A New Algorithm for Floorplan Design,”IEEE Proc. DAC, pp.101–107, 1986.
[4]Nakaya S., Koide T. and Wakabayashi S., “An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair,” Proc. IEEE ISCAS, pp. 65 -68, 2000.
[5]Chang-Tzu Lin, De-Sheng Chen, Yi-Wen Wang., “GPE: A New Representation for VLSI Floorplan Problem,” IEEE Proc. ICCD, pp. 531 -533, 2002.
[6]Y. Pang, C.K. Cheng, and T. Yoshimura, “An enhanced perturbing algorithm for floorplan design using the O-tree representation,”IEEE Proc. ISPD, pp. 168-173, 2000.
[7]Yun-Chih Chang; Yao-Wen Chang; Guang-Ming Wu; Shu-Wei Wu,“B*-trees: A New Representation for Non-slicing Floorplans,” IEEE Proc. DAC, pp. 458 –463, 2000.
[8]X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu,“Corner block list: an effective and efficient topological representation of non-slicing floorplan,”IEEE Proc. ICCAD, pp. 8-12, 2000.
[9]Jai-Ming Lin and Yao-Wen Chang, “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,”IEEE Proc. DAC, pp.764-769, 2001.
[10]H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair,” IEEE Transaction on Computer Aided Design of Integrated Circuit and System, Vol. 15, no.2, February 1996, pp.1518-1524.
[11]X. Tang, R. Tian, D.F. Wong, "Fast Evaluation of Sequence Pair in Block Placement by Longest Common Subsequence Computation," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 20,no. 12, December 2001,pp. 1406-1413.
[12]Tung-Chieh Chen, Yao-Wen Chang, Shyh-Chang Lin, ”IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs,” IEEE Proc. ICCAD, pp. 159-164, 2005.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊