簡易檢索 / 詳目顯示

回結果列表
研究生： 吳柏勳
Wu, Po-Hsun
論文名稱： 考慮匯流排腳位效應之匯流排導向平面佈局
Bus-Pin-Aware Bus-Driven Floorplanning
指導教授： 何宗易
Ho, Tsung-Yi
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2010
畢業學年度： 98
語文別： 英文
論文頁數： 54
中文關鍵詞： 平面規劃 、匯流排規劃
外文關鍵詞： Floorplanning, Bus planning
相關次數： 點閱：87  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 由於在嵌入式系統中，匯流排的數量急劇地上升，匯流排規劃的品質好壞成為決定嵌入式系統效能與系統功率消耗的重要指標。為了不讓匯流排的問題造成晶片設計流程後期的限制，在早期平面佈局時就將匯流排的因素加入考慮是比較理想的處理方式。近年來，匯流排導向平面佈局的問題吸引了許多人的注意，並且已有相當多的方法被提出於處理相關的問題。然而，目前的演算法都採取了比較簡單的問題定義，忽略了匯流排腳位的位置和方向等相關的資訊。忽略了上述的資訊可能會造成系統效能被高估的情況。因此，我們提出了一個匯流排導向的平面佈局演算法，我們所提出的演算法在規劃匯流排時也考慮到腳位的位置與方向的資訊，讓演算法所得到的結果能夠更符合實際情況。由於在規劃匯流排的同時也考慮匯流排腳位的資訊，匯流排轉彎的地方並不局限在匯流排所連接的方塊上。因此，在處理匯流排繞線問題時也比較有彈性。随著整個匯流排拓撲的形狀變得更有彈性，匯流排繞線的成功率也相對地提高，許多較佳的結果就能被發掘出來。將我們的演算法所得到的結果與目前最佳的匯流排導向平面佈局演算法所得到的結果比較，我們演算法的執行時間相對快了3.5倍，繞線成功率提高了1.2倍，匯流排長度少了1.8倍，並且將平面佈局中空白的區域降低了1.2倍。

    As the number of buses increase substantially in multi-core SoC designs, the bus planning problem has become the dominant factor in determining the performance and power consumption of SoC designs. To cope with the bus planning problem, it is desirable to consider this issue in early floorplanning stage. Recently, bus-driven floorplanning problem has attracted much attention in the literature. However, current algorithms adopt an over-simplified formulation ignoring the position and orientation of the bus pins, the chip performance may be deteriorated. In this paper, we propose the bus-driven floorplanning algorithm that fully considers the impacts of the bus pins. By fully utilizing the position and orientation of the bus pins,
    bus bendings are not restricted to occur at the modules on the bus, then it has more flexibility during bus routing. With more flexibility on the bus shape, the size of the solution space is increased and a better bus-driven floorplanning solution can be obtained. Compared with the bus-driven floorplanner [6], the experimental results show that our algorithm performs better in runtime by 3.5X, success rate by 1.2X, wirelength by 1.8X, and reduced the deadspace by 1.2X.

    List of Tables vii List of Figures viii Chapter 1. Introduction 1 1.1 Previous Works . . . 5 1.2 Our Contributions . . . 6 Chapter 2. Problem Formulation 9 Chapter 3. Constraints and Terminologies 11 Chapter 4. Algorithm 16 4.1 Modi ed Prim's Algorithm . . . 18 4.2 Segment Creation . . . 19 4.3 Bus Ordering and Coordinate Determination . . . 20 4.3.1 Bus Ordering . . . 20 4.3.2 Coordinate Determination . . . 22 4.4 Wirelength Reduction . . . 23 4.4.1 Overlap Minimization . . . 23 4.4.2 Coordinate Adjustment . . . 25 4.5 Layer Assignment . . . 29 4.6 Orientation Determination and Deviation Minimization . . . 31 4.6.1 Deviation Minimization with Lookup Table Method . . . 31 4.6.2 Fast Deviation Update Based on Topology Comparison . . . 35 4.7 Soft Module Adjustment . . . 42 Chapter 5. Experimental results 43 5.1 Experiments on Regular Testcases for [6] and [11] . . . 43 5.2 The Comparison Between [11] and This Work . . . 46 5.3 The Comparison Between Modi ed [11] and This Work . . . 47 5.4 Experiments on Larger Testcases for [11] and This Work . . . 48 Chapter 6. Conclusions 51 Chapter 7. Acknowledge 52 Bibliography 53

    [1] F. Ra q, M. Chrzanowska-Jeske, H. H. Yang, and N. Sherwani, "Integrated floorplanning with bu er/channel insertion for bus-based microprocessor designs," Proc. of ISPD, pp. 56-61, 2002.
    [2] H. Xiang, X. Tang, and Martin D. F. Wong, "Bus-driven floorplanning," Proc. of ICCAD, pp. 66-73, 2003.
    [3] T. C. Chen and Y. W. Chang, "Modern floorplanning based on fast simulated annealing," Proc. of ISPD, pp. 104-112, 2005.
    [4] J. H. Y. Law and E. F. Y. Young, "Multi-bend bus-driven floorplanning," Proc. of ISPD, pp.113-120, 2005.
    [5] H. Xiang, L. Deng, L.D. Huang, Martin D. F. Wong, "OPC-friendly bus driven floorplanning," Proc. of ISQED, pp. 847-852, 2007.
    [6] T. Ma and E. F. Y. Young, "TCG-based multi-bend bus-driven floorplanning," Proc. of ASPDAC, pp. 192-197, 2008.
    [7] D. H. Kim and S. K. Lim, "Global bus route optimization with application to microarchitectural design exploration," Proc. of ICCD, pp. 658-663, 2008.
    [8] D. H. Kim and S. K. Lim, "Bus-aware microarchitectural floorplanning," Proc. of ASPDAC, pp. 204-208, 2008.
    [9] W. Sheng, S. Dong, Y. Wu, and S. Goto, "Fixed outline multi-bend bus driven floorplanning," Proc. of ISQED, pp. 632-637, 2010.
    [10] O. He, S. Dong, J. Bian, S. Goto, and C.K. Cheng, "Bus via reduction based on floorplan revising," Proc. of GLSVLSI, pp. 9-14, 2010.
    [11] B. S. Wu and T. Y. Ho, "Bus-pin-aware bus-driven floorplanning," Proc. of GLSVLSI, pp. 27-32, 2010.
    [12] F. Mo and R. K. Brayton, "Semi-detailed bus routing with variation reduction," Proc. of ISPD, pp. 143-150, 2007.
    [13] F. Mo and R. K. Brayton, "A simultaneous bus orientation and bused pin flipping algorithm," Proc. of ICCAD, pp. 386-389, 2007.
    [14] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packing-based module placement," Proc. of ICCAD, pp. 472-479, 1995.
    [15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 2nd ed., MIT Press and McGraw-Hill Book Co., 2001.

    下載圖示 校內：2015-08-31公開
    校外：2015-08-31公開
    QR CODE