臺灣博碩士論文加值系統

在超大型積體電路設計的領域中尤其是在平面規劃（floorplanning）方面，考慮在設計中放置一些模組（modules）在晶片或是IC的邊緣是非常實際的考量，因為在某些情況下這樣的考量與設計可以使這些模組較容易連接到相對的 輸入/輸出接腳。這類的問題我們稱之為邊緣限制（Boundary Constraint）的平面規劃。邊緣限制是在平面配置限制（placement constraints）問題中的一種，我們會放置一些模組在最終的floorplan的四邊，也就是：左邊、右邊、最上方及最下方。
隨著先進VLSI製程及設計複雜度的增加，電路的尺寸大小也逐漸增加。為了能有效處理設計複雜度的問題，階層化設計（hierarchical design）與IP reuse變得越來越熱門，也因此突顯出平面規劃與平面配置的重要性。平面規劃設計（Floorplan design）在VLSI電路的實體設計中是一個非常關鍵的步驟，他的目的就是希望能放置一組電路模組在一顆晶片上，並能使它的總面積和繞線連接的成本能達到最小。已經有很多針對平面規劃表示法的相關擴充應用及限制演算法被發展出來。在這裡我們所要討論的主題是在邊界限制問題方面。它在某些情況下非常有用，尤其是當設計者希望能放置某些模組在晶片邊緣並用來作為輸入/輸出連接用。除此之外，因為可階層化的設計，模組可被群組到不同的單元設計內且平面規劃可獨立在每個不同晶片上的單元作設計。當這些有邊界限制的模組需要與其他不同單元作結合時，這種方式可以有效的讓這些模組緊鄰在其他單元的模組旁邊。
在這篇論文中，我們以Generalized Polish Expression（GPE）為基礎發展出一個邊界限制的演算法來強化GPE處理邊界限制的能力。我們的作法首先去分析GPE的特徵與特性。Generalized Polish Expression是一各自後序表示法(Polish Expression)徹底改良的表示法，它可以很容易的處理不可分割的平面規劃（non-slicing floorplan）。然而，後序表示法之前所發展出的邊界限制演算法只能用來處理可分割的平面規劃（slicing floorplan）。我們以我們所之前所發展出的GPE為基礎，改良了原本後序表示法的邊界限制演算法。我們的方法會在每一次的Simulated Annealing過程中被使用來檢查所有邊界限制的模組的正確性，並且會在這些模組有違反限制時作修復。我們在一些benchmark上測試我們所發展出的演算法，而得到的結果也令人感到鼓舞。

In floorplanning of VLSI design, it is practical to consider placing some modules along the boundaries of the chip so that the modules can be easier to be connected to certain I/O pads. This kind of problem is called placement with boundary constraints. Boundary constraint is one kind of placement constraints to pack some modules on one of the fours sides: on the left, on the right, at the top or at the bottom of the final floorplan.
With the increase of design complexity, circuit size is getting larger in modern VLSI design. To handle the design complexity, hierarchical design and IP reuse become more and more popular, which reveals the importance of floorplanning and placement. Floorplan design is a critical step in physical design of VLSI circuits. The objective of the problem is to place a set of circuit modules on a chip to minimize total area and interconnection cost. Many extending implementations and constraints based on floorplanning representations have been developed. The placement constraint we consider here is called boundary constraint. This is useful because designers may want to place some modules along the boundary for input-output connections. Besides, floorplanning is usually done hierarchically in which modules are grouped into different units and floorplanning is done independently for each unit on the chip. It is helpful when these constrained-module units are combined with other units, they can abut with some other modules in the neighboring units.
In this paper, we implement a boundary algorithm based on Generalized Polish Expression (GPE) to enhance GPE to handle boundary constraints. The features of GPE were first analyzed. Generalized Polish Expression is a thorough refinement from Polish Expression to handle non-slicing floorplan easily. However, the original boundary constraint algorithm of polish expression can only be used to handle slicing floorplan. We improved its boundary constraint algorithm based on our GPE. Our method will be used in each iteration of simulated annealing process to check the validity of the boundary-constrained modules efficiently and fix the expression in case the constraints are violated. We tested our algorithm on some benchmark data and the experimental results were encouraged.

第一章 導論
1.1提要
1.2論文架構
第二章 相關研究及知識背景
2.1 平面規劃（Floorplan）與平面配置（Placement）簡介
2.1.1 可分割平面規劃（Slicing Floorplan）
2.1.1.1 Polish expression介紹
2.1.2不可分割平面規劃（Non-Slicing Floorplan）
2.1.2.1Sequence-Pair（SP）表示法介紹
2.1.2.2 O-tree表示法介紹
2.1.2.3B*-tree 表示法介紹
2.1.2.4Transitive Closure Graph（TCG）表示法介紹
2.1.3平面配置（placement）簡介
2.2 各類限制演算法（Constraints Algorithm）應用簡介
第三章 Boundary Constraints 演算法
3.1題描述與定義
3.2.Generalized Polish Expression（GPE）背景知識簡介
3.3.Polish Expression的邊界限制演算法實作
3.3.1檢查邊界限制情況
第四章 Boundary Constraints在GPE上的實作
4.1研究動機
4.2Generalized Polish Expression特性分析
4.3演算法流程
第五章 實驗結果
5.1 實驗結果
5.2 分析與檢討
第六章 結論與未來工作
參考文獻
感謝詞
作者簡介

[1]F.Y. Young, D.F. Wong, Hannah H. Yang, “Slicing Floorplans with Boundary Constraints,” Proc. ASP-DAC, 1999, pp.17-20.[2]D.F. Wong and C.L. Liu, “A new algorithm for floorplan design,” in Proc. 23rd ACM/IEEE Design Automation Conf., 1986, pp. 101-107.[3]R.H.J.M Otten, “Automatic floorplan design,” in Proc. DAC, pp.261-267, 1982.[4]T.-C. Wang, and D.F. Wong, “An optimal algorithm for floorplan and area optimization,” Proc. DAC, pp. 180-186, June 1990[5]H. Murata, K.Fujiyoshi, S. Nakatake and Y. Kajitani, “Rectangle-Packing-Based Module Placement,” in Proc. IEEE/ACM International Conf. on Computer-Aided Design, pp.472-479, 1995[6]S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, “Module placement on BSG-structure and IC layout applications,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, 1996, pp.484-491[7]Jai-Ming Lin, and Yao-Wen Chang, “TCG: A Transitive Closure Graph-Based representation for non-slicing floorplans,” Proc. DAC, pp. 764-769, Jun. 2001[8]X. Tang, and D.F. Wong, “FAST-SP: A Fast Algorithm for Block Placement based on Sequence Pair,” Proc. ASP-DAC, pp.521-526, Jan. 2001[9]K. Fujiyoshi and H. Murata, “Arbitrary convex and concave rectilinear block packing using sequence-pair,” in Proc. Int. Symp. Physical Design, Apr. 1999,pp. 103-110[10]M. Kang and W.W.M. Dai, “General floorplanning with L-shaped, T-shaped and soft blocks based on bounded slicing grid structure,” in Proc. IEEE Asia South Pacific Design Automation Conf., Jan. 1997, pp. 265-270[11]J. Xu, P.N. Guo, and C.K. Cheng, “Rectilinear block placement using sequence-pair,” in Proc. 1998 ACM/IEEE Int. Symp. on Physical Design, Monterey, CA, Apr. 6—8, 1998, pp. 173—178.[12]T.C. Lee, “A bounded 2D contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules,” in Proc. 30th ACM/IEEE Design Automation Conf., June 1993, pp.525-530[13]F.Y. Young, M.D.F. Wong, and Hannah H. Yang, “On extending Slicing Floorplan to Handle L/T-Shaped Modules and Abutment Constraints,” Trans on Computer-Aided Design of integrated circuits and systems, IEEE, vol. 20, no 6, June. 2001, pp. 800-807[14]Guang-Ming Wu, Yun-Chih Chang, Yao-Wen Chang, “Rectilinear block placement using B*-trees,” Proc. International Conference on Computer Design, 2000, pp. 351 —356[15]Y. Ma, S. Dong, X. Hong, Y. Cai, C.-K. Cheng, J. Gu, “VLSI floorplanning with boundary constraints based on Corner Block List,” Proc. Design Automation Conferernce, ASP-DAC, 2001, pp. 509-514[16]J. Lai, M.S. Lin, T.C. Wang, L.C. Wang, “Module placement with boundary constraints using sequence-pair,” Proc. Design Automation Conferernce, ASP-DAC, 2001, pp. 515 -520[17]E.C. Liu, M.S. Lin, J. Lai, T.C. Wang, “Slicing floorplan design with boundary-constrained modules,” Physical Design of International Symposium, April 2001, pp 124-129[18]K. Fujiyoshi, H. Murata, M. Kaneko, “VLSI/PCB placement with obstacles based on sequence pair,” International Symposium on Physical Design, pp. 26-31, 1997[19]F. Y. Young, D. F. Wong, and Hannah H. Yang, “Slicing floorplans with pre-placed modules,” in Proc. IEEE Int. Conf. Computer-Aided Design, 1998, pp252-258[20]F. Y. Young, D. F. Wong, and Hannah H. Yang, “Slicing floorplans with range constraint,” Transaction on Computer-Aided Design of Integrated Circuits and Systems IEEE, vol 19, no. 2, Feb 2000[21]Chang-Tzu Lin, D.S. Chen, Y.W. Wang, “GPE: A New Representation for VLSI Floorplan Problem,” ICCD, Sep 16-18, 2002