(3.236.222.124) 您好!臺灣時間:2021/05/13 19:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳玟伶
研究生(外文):Wen Ling Chen
論文名稱:以三維序列表示法為基礎之空間規劃演算法
論文名稱(外文):A Spaceplan Algorithm Using Sequence-Triplet Representation
指導教授:謝財明謝財明引用關係
指導教授(外文):Tsai-Ming Hsieh
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:39
中文關鍵詞:平面規劃序列組空間規劃三維序列組
外文關鍵詞:SpaceplanFloorplanSequence tripletSequence pair
相關次數:
  • 被引用被引用:1
  • 點閱點閱:130
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
平面規劃(Floorplan)在超大型積體電路實體設計流程(VLSI Physical Design)中是相當重要的一個步驟,它的結果將會對晶片的效能造成很大的影響。
在本論文中,我們延伸平面規劃概念,並提出三維空間規劃問題。我們延伸被廣為使用的序列組(sequence pair)表示法來表示一空間規劃,稱之為三維序列組(sequence-triplet),以便來處理三維空間規劃問題。
我們發展出以模擬退火法為基礎之演算法,同時將包含所有模組之體積及模組間連線長度最小化。實驗結果顯示我們的演算法不僅成功地將平面規劃問題推展至空間規劃,更能在一定時間內達到不錯的空間使用率,同時在加入連線考量時,體積及連線長度皆可得到很大的改善。

Floorplan design is an important step in physical design of VLSI circuits. The result of the floorplan design will deeply influence performance of the chip.
In this thesis, we extended the concept of floorplan and proposed the spaceplan problem. An novel data structure, called the sequence triplet, which is an extension of the sequence pair widely used in the floorplan problem is used to deal with the 3D design problem. A simulated annealing based algorithm is proposed to minimize the volume and the total wire length among blocks.
The Experiment results show that we successfully extend the 2D floorplan problem to 3D spaceplan problem and achieve the good space untilization.

摘要I
ABSTRACTII
誌謝III
目錄IV
第一章 前言1
第二章 平面規劃問題研究3
2.1 平面規劃問題描述3
2.2 平面規劃之表示法及相關研究4
2.2.1 可分割性結構5
2.2.2 非分割性結構7
第三章 空間規劃問題17
3.1 研究動機17
3.2 三維序列表示法之定義17
3.3 問題描述18
3.4從三維序列組到一空間擺置20
3.4.1三維序列組對應之空間擺置圖20
3.4.2緊縮之空間擺置圖21
第四章 模擬退火演算法23
4.1 鄰近解23
4.2計價函數24
4.3演算法及退火過程25
第五章 實驗結果27
5.1 實驗平台27
5.2 實驗結果27
第六章 結論與展望29
參考文獻30
作者簡介34

[1]Kiarash Bazargan, Ryan Kastner and Majid Sarrafzadeh “3-D Floorplanning: Simulated Annealing and Greedy Placement Methods for Reconfigurable Computing Systems,” Rapid System Prototyping, 1999. IEEE International Workshop on 1999, Page(s): 38 —43[2]Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu and Shu-Wei Wu “B*-trees: a new representation for non-slicing floorplans,” Design Automation Conference Proceedings , pp. 458 —463, 2000.[3]K. Fujiyosi and H. Murata, “Arbitrary Convex and Concave Rectilinear Block Packing Using Sequence-Pair,” Proc. Intl. Symp. on Physical Design, pp. 103-110, 1999.[4]P.-N. Guo, C.-K. Cheng and T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and Its Application,” Proc. Design Automation Conf., pp. 268-273, 1999.[5]R. H. J. M. Otten, “ Efficient Floorplan Optimization,” Proc. Intl. Conf. on Computer Design, 1984.[6]Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng, Jun Gu “A non-slicing floorplanning algorithm using corner block list topological representation,” IEEE APCCAS, pp. 833 —836, 2000.[7]Tsai-Ming Hsieh and Tsong Chang “The Study of 3-D Block Packing Problems,” The CHUNG YUAN JOURNAL vol. XXI, Dec., 1992[8] Sakanushi K., Kajitani, Y. “The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization” IEEE APCCAS, pp. 829 -832, 2000.[9]M.Z.-W. Kang and W. W.-M. Dai, “Arbitrary Rectilinear Block Packing Based on Sequence-Pair,” Proc. Intl. Conf. on Computer-Aided Design, pp. 259-266, 1998.[10]J. Lai and T.-C. Wang, “Module Placement with Boundary Constraint Based on BSG-Structure,” Proc. 10th VLSI Design/CAD Symposium, pp.43-46, 1999.[11]D.P. Lapotin and S. W. Director, “A global floor-planning tool,” in Proc. IEEE Int. Conf. Computer-Aided Design, pp 143-145, 1985.[12]J.-M. Lin and Y.-W. Chang, “TCG: A transitive closure graph based representation for non-slicing floorplans, ” to appear in Proc. of ACM/IEEE Design Automation Conference (DAC-2001), Las Vegas, NV, June 2001.[13]H. Murata and E. S. Kuh, “Sequence-pair Based Placement Method for Hard/Soft/Pre-Placed Modules,” Proc. Intl. Symp. on Physical Design, pp. 167-172, 1998.[14]H. Murata, K. Fujiyoshi, S.Nakatake and Y.Kajitani, “Rectangle-Packing-Based Module Placement,” Proc. Intl. Conf. on Computer-Aided Design, pp. 472-479, 1995.[15]H. Murata, K,Fujiyoshi and M.Kaneko, “VLSI/PCB Placement with Obstacles Based on Sequence-Pair,” Proc. Intl. Symp. on Physical Design, pp. 26-31, 1997.[16]S. Nakatake, K. Fujiyoshi, H. Murata and Y.Kajitani, “Module Placement on BSG-Structure and IC Layout Applications,” Proc. Intl. Conf. on Computer-Aided Design, pp. 484-491, 1996.[17]R.H.J.M. Otten, “Automatic floorplan design,” in Proc. 19th ACM/IEEE Design Automation Conf., pp. 261-267, 1982.[18]Yingxin Pang, C. K. Cheng, Takeshi Yoshimura “An Enhanced Perutrbing Algorithm for Floorplan Design Using the O-tree Representation,” Proceedings of the international symposium on Physical design, San Diego, CA, USA ,pp 168 — 173, April 9 - 12, 2000.[19]L. Stockmeyer, “Optimal Orientations of Cells in Slicing Floorplan Designs,” Information and Control, pp. 91-101, 1983.[20]D.F. Wong and C. L. Liu, “A New Algorithm for Floorplan Design,” Proc. Design Automation Conf., pp. 101-107, 1986.[21]Guang-Ming Wu, Yun-Chih Chang and Yao-Wen Chang “Rectilinear Block Placement Using B*-Trees,” Design Automation Conference Proceedings, 2000.[22]J. Xu, P.-N. Guo and C.-K. Cheng, “Rectilinear Block Placement Using Sequence-Pair,” Proc. Intl. Symp. on Physical Design, pp. 173-178, 1998.[23]Takayudi Yamanouchi, Kazuo Tamakashi, and Takashi Kambe, “Hybrid Floorplanning Based on Partial Clustering and Module Restructuring,” IEEE/ACM International Conference , pp. 478 —483, 1996.[24]F.Y. Young and D.F. Wong, “Slicing Floorplans with Boundary Constraint,” Proc. ASP-DAC, pp. 17-20, 1999.[25]F.Y. Young and D.F. Wong, “Slicing Floorplans with Pre-Placed Modules,” Proc. Intl. Conf. on Computer-Aided Design, 1998, pp. 252-258.[26]F.Y. Young and D.F. Wong, “How good are slicing floorplans,” Integration VLSI J. vol. 23, pp. 61-73, 1997; also appeared in ISPD-97.[27]F.Y. Young, D.F. Wong, and Hannah H. Yang “Slicing Floorplans with Range Constraint,” IEEE Transactions on CAD of Integrated Circuits and Systems, vol. 19, NO. 2, pp. 272-278, February 2000.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔