臺灣博碩士論文加值系統

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