臺灣博碩士論文加值系統

隨著單一系統晶片(System-on-Chip , SoC)時代的來臨，晶片設計就變的越來越複雜，為了減少晶片設計的複雜性，矽智財(SIP)模組被廣泛地應用在現今的晶片設計中，導致晶片內的矽智財模組可能由許多不同公司或不同部門所提供，對於發展單一系統晶片而言，將所有矽智財模組整合至單一晶片中是一件相當重要的事情，同時也造成單一系統晶片內的板面規劃(floorplan)變的比以往更加重要，所以就單一系統晶片的整合來說，好的板面規劃應用能夠獲得更小的晶片面積和更好的時間結果，然而，好的板面規劃應用的實行取決於板面規劃的資料表示法。
本篇論文對於不可分割(non-slicing)板面規劃提出一個新的表示法稱為Double-Bound-List(DBL)，DBL表示法具有目前幾個熱門表示法(如sequence pair、O-tree、B*-tree、CBL、TCG及SCP)之優點，例如DBL表示法符合P-admissible特性的需求、可以直接從DBL表示法的架構中得知板面規劃的面積和鄰近區塊的幾何關係，另外對於不可分割板面規劃的儲存，DBL表示法只需使用少量記憶體即可完成，且也符合一對一對應之關係。
最後在論文中將會介紹如何使用DBL表示法發展模擬退火為基礎之板面規劃應用，而實驗結果也說明所提出之新方法，在較少的記憶體需求下可以獲得更好的板面規劃面積。

Due to the coming of the system-on-chip (SoC) age, the chip design become more and more complicated. To deal with the increasing complexity, SIP modules become popular for modern chip design. Since the SIP modules in the chip have provided by different companies or departments, it is very important for the development of SoC chip to integrate all the SIP modules into a single chip. At the same time, it also makes the floorplan process of the SoC chip to become more critical than even. Consider the integration of a SoC chip, a best floorplan approach can obtain smaller chip area and better timing result. However, the performance of a better floorplan approach depends on the data representation of the floorplans.
In this paper, we present a new representation, named double -bound-list (DBL), for non-slicing floorplans. The DBL representation combines the advantages of popular representation such as sequence pair, O-tree, B*-tree, CBL, TCG, and SCP. For example, DBL conforms to the requirements of P-admissible properties. From the structure of the DBL representation, the area of the floorplan result and the geometric relationship of adjacent modules can be immediately found. In addition, the DBL representation needs less memory for the storage of non-slicing floorplans and conforms the one-to-one mapping relation between non-slicing floorplans and DBL representations.
Finally, the paper introduces how to use the DBL representation to develop a simulated-annealing-based floorplan approach. The experimental results show that the proposed approach obtain better floorplan area under less memory requirement.

中文摘要..................................................I
英文摘要.................................................II
致謝.....................................................IV
目錄......................................................V
圖形目錄................................................VII
表格目錄.................................................IX
第一章 簡介...............................................1
第二章 相關研究...........................................6
2.1 可分割板面規劃...................................6
2.2 不可分割板面規劃.................................6
2.2.1 Sequence pair表示法.........................7
2.2.2 O-tree表示法................................8
2.2.3 B*-tree表示法..............................10
2.2.4 CBL表示法..................................12
2.2.5 TCG表示法..................................14
2.2.6 SCP表示法..................................15
2.2.7 資料結構上運算比較..........................17
第三章 問題定義..........................................19
第四章 不可分割板面規劃表示法－雙重界限串列
(Double-Bound List, DBL)...........................22
4.1 由不可分割板面規劃轉成DBL表示法.................24
4.2 動態運算........................................28
4.2.1 相鄰(neighborhood)..........................28
4.2.2 刪除(delete)................................29
4.2.3 插入(insert)................................32
4.3 由DBL表示法轉成不可分割板面規劃.................35
4.4 資料結構上運算比較..............................38
4.4.1 資料結構特性比較............................38
4.4.2 運算執行時間比較............................39
4.4.3 記憶體需求量之比較..........................39
第五章 模擬退火式板面規劃演算法－使用DBL演算法..........41
5.1 模擬退火演算法..................................41
5.2 模擬退火式板面規劃演算法........................42
5.2.1 INIT-PLACEMENT-初始板面規劃.................44
5.2.2 PERTURB(Place)-擾亂DBL表示法...............44
5.2.3 Cost(Place)-計算面積........................51
5.2.4 SCHEDULE(Temp)..............................51
5.3 模擬退火式板面規劃運算執行時間比較表............52
第六章 實驗結果..........................................53
第七章 結論與未來研究方向................................57
參考文獻.................................................58

[1] R. H. J. M. Otten, “Automatic floorplan design,” Proc. DAC, pp.261-267, 1982.
[2] D. F. Wong, and C. L. Liu, “A new algorithm for floorplan design,” Proc. DAC, pp.101-107, 1986.
[3] T. Ohtsuki, N. Suzigama, and H. Hawanishi, “An optimization technique for int- ergrated circuit layout design,” Proc. ICCST, Kyoto, pp.67-68, 1970.
[4] T.-C. Wang, and D. F. Wong, “An optimal algorithm for floorplan and optimiza- tion,” Proc. DAC, pp.180-186, June 1990.
[5] H. Onodera, Y. Taniquchi, and K. Tamaru, “Branch-and-bound placement for building block layout,” Proc. DAC, pp.433-439, 1991.
[6] P. Pan and C.-L. Liu, “Area minimization for floorplans,” IEEE TCAD, pp.123- 132, Jan. 1995.
[7] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing based module placement,” Proc. ICCAD, pp.472-479, 1995.
[8] S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, “Module placement on BSG-structure and IC layout applications,” Proc.ICCAD, pp.484-491, 1996.
[9] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “ An O-Tree representation of non- slicing floorplan and its applications,” Proc. DAC, pp.268-273, 1999.
[10] Y.-Pang, C.-K. Cheng, and T. Yoshimura, “An enhanced perturbing algorithm for floorplan design using the O-Tree representation,” Proc. ISPD, pp.168-173, April 2000.
[11] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-trees: A new represent- tation for non-slicing floorplans,” Proc. DAC, pp.458-463, June 2000.
[12] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, and C.-K. Cheng, and J. Gu, “Corner Block List: An effective and efficient topological representation of non-slicing floorplan,” Proc. ICCAD, pp.8-12, Nov. 2000.
[13] J.-M. Lin and Y.-W. Chang, “TCG: A transitive closure graph-based represent- tation for non-slicing floorplans,” Proc. DAC, 2001.
[14] J.-M. Lin, S.-P. Lin, and Y.-W. Chang, “A P-admissible non-slicing floorplan representation with a worst-case linear-time packing scheme,” 2001.
[15] E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976.
[16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated an- nealing,” Science, vol.220, no. 4598, May 13, 1983, pp.671-680.
[17] S. M. Sait and H. Youssef, VLSI physical design automation, IEEE Press, 1995.
[18] H. Murata, K. Fujiyoshi, and M. Kaneko, “VLSI/PCB placement with obstacles based on sequence pair,” Proc. ISPD, pp. 26-31, 1997.
[19] Y. Ma, S. Dong, X. Hong, Y. Cai, C. K. Chang, and J.Gu, “VLSI floorplanning with boundary constraints based on corner block list,” Proc. ASP-DAC, pp.509- 514, 2001.
[20] J.-L, M.-S. Lin, T.-C. Wang, and Li-C.Wang, “Module placement with boundary constraints using the sequence-pair,” Proc. ASP-DAC, pp.515-520, 2001.
[21] X. Tang and D. F. Wong, “FAST-SP: A fast algorithm for block placement based on sequence pair,” Proc. ASP-DAC, pp. 521-526, 2001.