臺灣博碩士論文加值系統

在積體電路後端實體設計(physical design)中，平面規劃一直都是一個重要的議題。但隨著積體電路設計階層趨於複雜化，在實體設計階段時才考慮電路模組平面規劃問題已無法將規劃結果立即回饋予前端系統階層設計者以便於修正其相對設計，因此我們考慮在前端系統階層設計階段模組尚未設計完成時之不確定性模組平面規劃問題，探討針對面積及維度大小不固定之模組如何進行未來平面規劃的評估。在本論文中我們提出一個植基於群聚（clustering）策略之不確定模組平面規劃演算法以便能有效的評估不確定模組所形成之晶片面積。在我們的方法中，首先採用群聚技巧將模組聚集起來形成一些面積較大但個數較少的組合模組（supermodules），接著以Sequence-Pair表示法來記錄組合模組間相對位置關係並在最後執行模擬退火(simulated annealing)程序以求得不確定模組所形成的最終晶片面積之機率分佈圖。實驗結果證明本論文中所提出之演算法能有效且迅速處理不確定性模組平面規劃問題。

Floorplanning is an important issue in the physical design phase of the VLSI design. As VLSI design hierarchy becomes more complex, it is difficult to immediately send obtained floorplanning information back to frontend system level designer for modifying modules if floorplanning is considered until the backend physical design phase. Hence, we consider solving floorplanning of uncertain modules which are designed in frontend system level and have not been designed completely yet. In this paper, to evaluate chip area effectively and efficiently, a non-slicing uncertain floorplan algorithm based on clustering strategy is proposed. In the method, clustering strategy is first applied to group modules to form fewer supermodules of larger size, then the Sequence-Pair representation for non-slicing floorplan is used to record the relative positions among supermodules, and the simulated annealing procedure is finally executed according to Sequence-Pair for obtaining an area distributed graph. Experimental results on uncertain floorplanning demonstrate the efficiency and effectiveness of proposed algorithm.

封面內頁
簽名頁
授權書．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． iii
中文摘要．．．．．．．．．．．．．．．．．．．．．．． iv
英文摘要．．．．．．．．．．．．．．．．．．．．．．．． v
誌謝．．．．．．．．．．．．．．．．．．．．．．．．． vi
目錄．．．．．．．．．．．．．．．．．．．．．．．．． vii
圖目錄．．．．．．．．．．．．．．．．．．．．．．．． ix
表目錄．．．．．．．．．．．．．．．．．．．．．．．． xi

第一章 緒論．．．．．．．．．．．．．．．．．．．．．．．．．．． 1
1.1 研究背景與動機．．．．．．．．．．．．．．．．．．．．． 1
1.2 研究方法．．．．．．．．．．．．．．．．．．．．．．．．． 2
1.3 論文架構．．．．．．．．．．．．．．．．．．．．．．．．． 3
第二章 相關研究．．．．．．．．．．．．．．．．．．．．．．．．． 4
2.1 傳統平面規劃問題描述．．．．．．．．．．．．．．．．．．5
2.2 可切割性結構．．．．．．．．．．．．．．．．．．．．．．．5
2.2.1 Shorthand Tree表示法．．．．．．．．．．．．．．．． 5
2.2.2 Normalized Polish Expression表示法．．．．．．．．．6
2.3 不可切割性結構．．．．．．．．．．．．．．．．．．．．．．8
2.3.1 Sequence-Pair表示法．．．．．．．．．．．．．．．． 8
2.3.2 Bounded-Sliceline Grid表示法．．．．．．．．．．． 12
2.3.3 O-tree表示法．．．．．．．．．．．．．．．．．．． 13
2.3.4 B*-tree表示法．．．．．．．．．．．．．．．．．．． 15
2.3.5 Corner Block List表示法．．．．．．．．．．．．．． 16
2.3.6 Transitive Closure Graph表示法．．．．．．．．．． 17
2.3.7梯形平面規劃器．．．．．．．．．．．．．．．．．． 18
2.4 不確定性模組平面規劃．．．．．．．．．．．．．．．．． 19
第三章 不確定性模組之平面規劃．．．．．．．．．．．．．．． 21
3.1 傳統模組與不確定性模組．．．．．．．．．．．．．．．． 21
3.2 問題描述．．．．．．．．．．．．．．．．．．．．．．．． 22
3.3 資料結構．．．．．．．．．．．．．．．．．．．．．．．． 23
3.4 二階段平面規劃．．．．．．．．．．．．．．．．．．．． 24
3.5 層階群聚．．．．．．．．．．．．．．．．．．．．．．．． 25
3.6 以SP表示法處理不確定性模組平面規劃．．．．．．．． 31
3.6.1水平與垂直拓樸圖形．．．．．．．．．．．．．．． 33
3.6.2 最長路徑演算法．．．．．．．．．．．．．．．．．． 36
3.7 模擬退火演算法．．．．．．．．．．．．．．．．．．．． 43
第四章 實驗結果．．．．．．．．．．．．．．．．．．．．．．．． 45
4.1 模擬退火目標函數中β值對平面規劃結果之影響．．．． 46
4.2 不確定性模組個數多寡對平面規劃之影響．．．．．．． 49
4.3 不同平面規劃表示法所得結果之比較．．．．．．．．．． 53
第五章 結論與未來展望．．．．．．．．．．．．．．．．．．．． 74
5.1 結論．．．．．．．．．．．．．．．．．．．．．．．．．． 74
5.2 未來展望．．．．．．．．．．．．．．．．．．．． 75
參考文獻．．．．．．．．．．．．．．．．．．．．．．．．76

參考文獻

[1]K. Bazargan, S. Kim, M. Sarrafzadeh(1998)” Nostradamus: a floorplanner of uncertain design” Proceedings of the 1998 International Symposium on Physical Design Conference, Pages 18 – 23.
[2]Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu (2000) “B*-Trees: A New Representation for Non-Slicing Floorplans” Proceedings of the 37th Design Automation Conference, Pages 458–463.
[3]P. N. Guo, C. K. Cheng, and T. Yoshimura (1999) “An O-tree Representation of Non-Slicing Floorplan, and Its Applications” Proceedings of the 36th ACM/IEEE Design Automation Conference, Pages 268–273.
[4]X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C. K. Cheng, and J. Gu (2000) “Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan” Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design, Pages 8–12.
[5]P. G. Sassone and S. K. Lim (2003) “A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning” Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design, Pages 74-80.
[6]J. Li, T. Yan, B. Yang, J. Yu, and C. Li (2004) “A Packing Algorithm for Non-Manhattan Hexagon/Triangle Placement Design by Using An Adaptive O-Tree Representation” Proceeding of 41st Design Automation Conference, Pages 646–651 .
[7]J. M. Lin and Y. W. Chang (2001) “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans” Proceeding of 38th Design Automation Conference, Pages 764–769.
[8]H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. (1996) “VLSI Module Placement Based on Rectangle-Packing by the Sequence–Pair” Proceedings of IEEE Transaction on Computer Aided Design of Integrated Circuits and System, February 1996 Volume 15 Issue 2, Pages 1518–1524.
[9]S. Nakata, K. Fujuoshi, H. Murata, and Y. Kajitani (1996)“Module Placement on BSG-Structure and IC Layout Applications” Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, Pages 484–491.
[10]H. Onodera, Y. Taniguchi, and K. Tamaru (1991) “Branch-and-Bound Placement for Building Block Layout” Proceedings of 28rd ACM/IEEE Design Automation Conference, Pages 433–439.
[11]R. H. J .M. Otten (1982) “Automatic Floorplan Design” Proceedings of 19th ACM/IEEE Design Automation Conference, Pages 261–267.
[12]K. Sakanushi, Y. Kajitani, and D. P. Mehta (2003) “The Quarter-State-Sequence Floorplan Representation” Proceedings of IEEE Transaction on Circuits and Systems–I: Fundamental Theory and Applications, March 2003 Volume 50 Issue 3, Pages 376–386.
[13]X. Tang, R. Tian, and D. F. Wong (2001) “Fast Evaluation of Sequence Pair in Block Placement by Longest Common Subsequence Computation” Proceedings of IEEE Transaction on Computer Aided Design of Integrated Circuits and System, December 2001 Volume 20 Issue 12, Pages 1406–1413.
[14]X. Tang and D. F. Wong (2002) “Floorplanning with Alignment and Performance Constraints” Proceedings of 39th Design Automation Conference, Pages 848–853.
[15]D. F. Wong and C. L. Liu (1986) “A New Algorithm for Floorplan Designs” Proceedings of 23rd ACM/IEEE Design Automation Conference, Pages 101–107.
[16]H. Xiang, X. Tang, and D. F. Wong (2003) “Bus-Driven Floorplanning” Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design, Pages 66 –73.
[17]J. Xu, P. N. Guo, and C. K. Cheng (1998) “Rectilinear Block Placement Using Sequence-Pair” Proceedings of the 1998 International Symposium on Physical Design Conference, Pages 173–178.
[18]吳彬玄、程仲勝 (2002) “降低電磁干擾之後置平面規劃器”Proceedings of 2002 Taiwan ElectroMagnetic Compatibility Conference, Pages 172–175.
[19]吳彬玄、習存榮、程仲勝 (2003)“考慮電磁相容之超大型積體電路平面規劃之研究” Proceedings of 2003 Taiwan ElectroMagnetic Compatibility Conference, Pages 78–83.