臺灣博碩士論文加值系統

幾年來半導體產業蓬勃發展，造就了台灣經濟的起飛，但是現今積體電路晶片之設計，慢慢趨向智慧財產權（IP, Intellectual Property）的方向來設計。所以現在大部份積體電路在設計上，都會由一種以上的IP所組成，因此平面規劃（floorplan）這方面的問題，就顯得更加地重要。
在平面規劃的問題上，基於電路設計上的需求，某些模組在最後封裝的時候，必須滿足一些限制條件。而在我們的論文中，我們是利用偶角模組列（Corner Block List）表示法，配合我們的演算法，來解決在叢聚限制下之平面規劃問題，最後實驗結果，也証明我們的演算法有很好的效能。

Since integrated circuits design are tending to intellectual property (IP) mode. Circuits are composed of IP modules. Therefore, the floorplan problems are become important.
In floorplan, some modules are required to satisfy some constraints in the final packing. In this thesis, we propose an algorithm based on Corner Block List for the floorplan with clustering constraints. Experiment results show that our algorithm is very efficient.

書名頁........................................i
授權書........................................ii
論文指導教授推薦函 ............................iii
論文口試委員審定書 ............................iv
中文摘要......................................v
英文摘要......................................vi
誌謝..........................................vii
目錄..........................................viii
表目錄........................................x
圖目錄........................................xi
第一章、前言..................................1
第二章、問題描述..............................5
第三章、CBL（CORNER BLOCK LIST）表示法........7
第一節　CBL的模組與平面規劃.................8
第二節 偶角（CORNER）模組的插入與刪除.......11
第三節 CBL的參數............................13
第四節 成本函數.............................15
第五節 平面規劃與模組擺置演算法.............15
第四章 我們的演算法...........................17
第一節 鄰近解與合理解.......................17
第二節 叢聚的限制式.........................22
第三節 模擬退火演算法之理論與流程設計.......26
第五章 實驗結果...............................31
第六章 結論與未來發展.........................46
第一節　結論................................46
第二節　未來發展............................47
參考文獻......................................48

[1]. Y.-C. Chang, Y.-W. Chang, G.-M. Wu and S.-W. Wu, “B*-trees: A New Representation for Non-Slicing Floorplans,” in Proceedings of the 37th ACM/IEEE Design Automation Conference, pp. 458-463, 2000.
[2]. K. Fujiyosi and H. Murata, “Arbitrary Convex and Concave Rectilinear Block Packing,” in Proceedings International Symposium on Physical Design, pp. 103-110, 1999.
[3]. P. N. Guo, C. K. Cheng, and T. Yoshimura, “ An O-tree Representation of Non-Slicing Floorplan and Its Applications,” in Proceedings of the 36th ACM/IEEE Design Automation Conference, pp. 268-273, 1999.
[4]. Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng and Jun Gu, “A Non-Slicing Floorplanning Algorithm Using Corner Block List Topological Representation,” in Proceedings ASP-DAC, pp. 833-836, 2000.
[5]. Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng and Jun Gu, “Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan,” in Proceedings of ACM/IEEE Design Automation Conference (DAC-2000), pp. 8-12, 2000.
[6]. M. Z. W. Kang and W. W. M. Dai, “General Floorplanning with L-Shaped, T-Shaped and Soft Blocks Based on Bounded Slicing Grid Structure,” in Proceedings ASP-DAC, pp. 265-270, 1997.
[7]. M. Z. W. Kang and W. W. M. Dai, “Topology Constrained Rectilinear Block Packing for Layout Reuse,” in Proceedings International Symposium on Physical Design, pp. 179-186, 1998.
[8]. M. Z. W. Kang and W. W. M. Dai, “Arbitrary Rectilinear Block Packing Based on Sequence-Pair,” in Proceedings International Conf. on Computer-Aided Design, pp. 259-266, 1998.
[9]. S. Kirkpatrick et al. “Optimization by simulated annealing,” Science, Vol. 220, pp. 671-680, 1983.
[10]. J.-M. Lin and Y.-W. Chang, “TCG: A Transitive Closure Graph Based Representation for Non-Slicing Floorplans,” in Proceedings of ACM/IEEE Design Automation Conference (DAC-2001), pp. 764-769, 2001.
[11]. Yuchun Ma, Sheqin Dong, Xianlong Hong, Yici Cai, Chung-Kuan Cheng and Jun Gu, ”VLSI Floorplanning with Boundary Constraints Based on Corner Block List” in Proceedings ASP-DAC, pp. 509-514, 2001.
[12]. H. Murata, K. Fujiyoshi and M. Kanedo, “VLSI/PCB Placement with Obstacles Based on Sequence-Pair,” in Proceedings International Symposium on Physical Design, pp. 26-31, 1997.
[13]. H. Murata and E. S. Kuh, “Sequence-pair Based Placement Method for Hard/Soft/Pre-Placed Modules,” in Proceedings International Symposium on Physical Design, pp. 167-172, 1998.
[14]. S. Nakatake, K. Fujiyoshi, H. Murata and Y. Kajitani, “Module Placement on BSG-Structure and IC Layout Applications,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 484-493, IEEE Computer Society Press, Nov. pp. 10-14 1996.
[15]. S. Nakatake, M. Furuya and Y. Kajitani, “Module Placement on BSG-Structure with Pre-Placed Modules and Rectilinear Modules,” in Proceedings ASP-DAC, pp. 571-576, 1998.
[16]. R. H. J. M. Otten, “Automatic Floorplan Design,” in Proceedings of the 19th IEEE/ACM International Conference on Computer-Aided Design, pp. 261-267, 1982.
[17]. D. F. Wong and C. L. Liu, “A New Algorithm for Floorplan Design,” in Proceedings of the 23rd ACM/IEEE Design Automation Conference, pp. 101-107, IEEE Computer Society Press, June 1986.
[18]. J. Xu, P. N. Guo and C. K. Cheng, “Rectilinear Block Placement Using Sequence-Pair,” in Proceedings International Symposium on Physical Design, pp. 173-178, 1998.
[19]. F. Y. Young and D. F. Wong, “Slicing Floorplans with Range Constraint,” in Proceedings International Symposium on Physical Design, pp. 97-102, 1999.
[20]. F. Y. Young and D. F. Wong, “Slicing Floorplan with Boundary Constraint,” in Proceedings ASP-DAC, pp. 17-20, 1999.
[21]. W. S. Yuen and F. Y. Young, “Slicing Floorplan with Clustering Constraints,” IEEE Asia South Pacific Design Automation Conference, pp. 503-508, 2001.