臺灣博碩士論文加值系統

由於IC設計的複雜度越來越高，使得電路的尺寸也越變越大，為了要處理更複雜的IC設計問題，因此階層式設計與智慧財產權的觀念在今日備受歡迎，這個趨勢也導致平面規劃在設計流程當中扮演非常具關鍵性的角色，而在平面規劃的表示法當中，序列對的表示法是非常有彈性的，因此在本篇論文當中，我們研究以非切割性結構的序列對表示法來解決叢聚限制的問題，我們提出一種以模擬退火法為基礎的演算法，可以從解空間當中辨別出能滿足叢聚限制的解。
我們以MCNC benchmark circuits 實驗，其結果顯示，使用我們發展的叢聚限制判斷方式，無叢聚限制與叢聚限制其Dead Space的差異在0~4.03 %之間，其結果算是蠻不錯的。

Due to the growth in design complexity, circuit size is getting larger. To cope with the increasing design complexity, hierarchical design and Intellectual Properties(IP) modules are widely used. This trend makes block Floorplanning/placement much more critical to the quality of a design. The Sequence Pair representation is very flexible for floorplanning. In this thesis, we consider the problem of non-slicing floorplan with clustering constraints based on the Sequence Pair. We propose an algorithm based on the simulated annealing for the problem, it could distinguish the solution which satisfied the clustering constraints from the solution space.
In our experiments, we use the MCNC benchmark circuits. The results show that the difference between the floorplans without clustering constraint and the floorplans with clustering constraint are in 0~4.03% in dead space. Experimental results are very well.

第一章 緒論 ………………………………………………………… 1
第一節 平面規劃的結構分類 ………………………………… 1
第二節 模組的形態 …………………………………………… 5
第三節 平面規劃的條件限制 ………………………………… 6
第四節 論文的架構 …………………………………………… 8
第二章 序列對表示法 ……………………………………………… 10
第一節 序列對的編碼方式 …………………………………… 10
第二節 表示法對應的平面規劃 ……………………………… 11
第三章 叢聚限制的問題定義………………………………………… 14
第四章 序列對表示法之叢聚性限制………………………………… 16
第一節 序列對表示法之叢聚限制問題………………………… 16
第二節 判斷方向的序列對表示法 …………………………… 17
第三節 叢聚性限制的條件……………………………………… 20
第四節 多組叢聚的限制 ……………………………………… 21
第五章 叢聚限制模組擺置的演算法 ……………………………… 22
第一節 模擬退火法的參數設計 ……………………………… 22
第二節 模擬退火法的流程……………………………………… 23
第六章 實驗結果……………………………………………………… 25
第一節 測試的電路與環境設備………………………………… 25
第二節 實驗結果 ………………………………………………… 25
第七章 結論與建議…………………………………………………… 36
參考文獻 ……………………………………………………………… 37

[1] F. Balasa and K.V. Lampaert, "Symmetry within the Sequence-Pair Representation in the Context of Placement for Analog design," IEEE Trans. on CAD of IC''s and Systems, Vol. 19, No. 7, pp. 721-731, July 2000.
[2] Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu and Shu-Wei Wu, "B*-Trees: A New Representation for Non-Slicing Floorplans," Proc. of ACM/IEEE Design Automation Conference（DAC-2000）, pp. 458-463, LA, CA, June 2000.
[3] K. Fujiyoshi and H. Murata, "Arbitrary Convex and Concave Rectilinear Block Packing Using Sequence-Pair," Proc. ISPD, pp. 103-110, 1999.
[4] P. N. Guo, C. K. Cheng and T. Yoshimura, "An O-Tree Representation of Non-Slicing Floorplan and Its Applications," Proc. on IEEE/ACM Design Automation Conference, pp. 268-273, 1999.
[5] 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," IEEE APCCAS, pp. 833 -836, 2000.
[6] Y.-H. Jiang, J. Lai and T.-C. Wang, "Module Placement with Pre-Placed Modules Using the B*-Tree Representation," Proc. of IEEE International Symposium on Circuits and Systems（ISCAS）, pp. 347-350, 2001.
[7] M. Z. Kang and W. Dai, "General Floorplanning with L-shaped, T-shaped and Soft Blocks Based on Bounded Slicing Grid Structure," Proc. Asia and South Pacific Physical Design Automation Conference （ASP-DAC）, pp. 265-270, 1997.
[8] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, pp. 671-680, 1983.
[9] E.-C. Liu, T.-H. Lin and T.-C. Wang, "On Accelerating Slicing Floorplan Design with Boundary Constraints," Proc. of IEEE International Symposium on Circuits and Systems （ISCAS）, pp. III399-III402, 2000.
[10] J. Lai and T.-C. Wang, "Module Placement with Boundary Constraint Based on BSG-Structure," Proc. of the 10th VLSI Design/CAD Symposium, pp. 43-46, 1999.
[11] J. Lai, M.-S. Lin, T.-C. Wang and L.-C. Wang, "Module Placement with Boundary Constraints Using the Sequence-Pair Representation, " Proc. Asia and South Pacific Physical Design Automation Conference （ASP-DAC）, pp. 515-520, 2001.
[12] J.-M. Lin and Y.-W. Chang, "TCG： A Transitive Closure Graph Based Representation for Non-Slicing Floorplans," Proc. of ACM/IEEE Design Automation Conference （DAC-2001）, pp. 764-769, Las Vegas, NV, June 2001.
[13] Rui Liu, Xianlong Hong, Sheqin Dong, Jun Gu, Chung-Kuan Cheng and Yici Cai, "Module Placement with Boundary Constraints Using O-Tree Representation," IEEE International Symposium on Circuits and Systems （ISCAS）, May 2002.
[14] H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Trans. on CAD, Vol. 15, No. 12, pp.1518-1524, Dec. 1996.
[15] H. Murata and Ernest S. Kuh, "Sequence Pair Based Placement Method for Hard/ Soft/Pre-placed Modules," Proc. Internal Symposium on Physical Design, pp. 167-172, 1998.
[16] Yuchun Ma, Sheqin Dong, Xianlong Hong, Yici Cai, C.K. Cheng and Jun Gu, "VLSI Floorplanning with Boundary Constraints Based on Corner Block List," Proc. Asia and South Pacific Physical Design Automation Conference （ASP-DAC）, pp. 509-514, 2001.
[17] S. Nakatake, M. Furuya and Y. Kajitani, "Module Placement on BSG-Structure with Pre-Placed Modules and Rectilinear Modules," Proc. Asia and South Pacific Physical Design Automation Conference （ASP-DAC）, pp. 571-576, 1998.
[18] Y.-X. Pang, F. Balasa, K.V. Lampaert and C.-K. Cheng, "Block Placement with Symmetry Constraints Based on the O-Tree Non-Slicing Representation,'''' Proc. of the 37th ACM/IEEE Design Automation Conference（DAC）, pp. 464-467, Los Angeles CA, June 2000.
[19] W. S. Yuen and F. Y. Young, "Slicing Floorplans with Clustering Constraints," IEEE Asia South Pacific Design Automation Conference, pp. 503-508, 2001.
[20] D. F. Wong and C. L. Liu, "A New Algorithm for Floorplan Design," Proc. of ACM/IEEE Design Automation Conference, pp. 101-107, 1986.
[21] D. F. Wong and C. L. Liu, "Floorplan Design for Rectangular and L-shaped Modules," Proc. ICCAD, pp. 520-523, 1987.
[22] F. Y. Young and D. F. Wong, "Slicing Floorplans with Pre-placed Modules," Proc. IEEE International Conference on Computer- Aided Design, pp. 252-258, 1998.
[23] 衣懷恩，"以B*樹處理邊界條件限制下的擺置問題之研究，"交通大學資訊科學研究所，碩士論文，2001年6月。