利用遞移封閉圖表示法處理超大型積體電路之平面規劃

Abstract

隨著製程技術進步，設計越來越複雜。為了處理如此複雜的線路，階層式設計和IP模組被廣泛應用於超大型積體電路設計以加速設計收斂的速度，這使得平面規劃（floorplanning）這個問題越來越重要。平面規劃和擺置(Floorplanning/placement) 最主要的目的是分配模組的位置來最佳化一些既定的目標例如面積、效能、或者是繞線成功率。要實現模組平面規劃和擺置，首先必須有一個表示法來描述模組之間相對的位置。因為表示法對於平面規劃設計的可行性和複雜度具有決定性的影響，所以發展一個有效、快速而且有彈性的表示法 變得非常重要。在這本博士論文當中，我們首先提出P*-admissible 表示法的概念，接著又提出了兩個圖形表示法分別稱為Transitive Closure Graph (TCG) 和Transitive Closure Graph-Sequence (TCG-S)，因為我們很容易從此兩種表示法觀察模組之間的相對位置，並且利用其對應的動作 (operations) 來改變模組間的相對位置，所以 TCG 和 TCG-S 非常容易處理各種形狀的模組和各式各樣的擺置問題，例如有些模組必須放在晶片的邊界，或者是有些模組已經事先被擺好了，所以其它的模組只能放在剩餘的區域，而在類比設計中，模組必須對稱放置。不像過去所提出的方法，以遞移封閉圖 (transitive closure graph) 為基礎的方法在處理這些問題的時候，不僅可以保證每次在擾動的時候皆可得到合理的解答，而且我們的方法非常簡單容易被實行。

As technology advances, the circuit size in modern VLSI design increases dramatically. To handle the increasing design complexity, hierarchical designs and IP modules are widely used for design convergence, which makes floorplaning more important than ever. The major objective of floorplanning/placement is to allocate the modules of a circuit into a chip to optimize a predefined cost metric such as area, timing, routability, etc. The realization of floorplanning/placement relies on a representation which describes geometric relations among modules. The representation has a great impact on the feasibility and complexity of floorplan designs. Thus, it is of particular significance to develop an efficient, effective, and flexible representation for floorplan/placement designs. In this dissertation, we first propose the concept of the P*-admissible representation, and then present two graph based representations, namely Transitive Closure Graph (TCG) and Transitive Closure Graph-Sequence (TCG-S) representations for general floorplans. Since the geometric relations of modules are transparent to the two representations and their operations, we can easily use TCG and TCG-S to deal with arbitrarily shaped modules and various placement constraints, such as the boundary constraint, the pre-placed constraint, and the symmetry constraint. Unlike most of previous works, our approaches can guarantee the feasibility in each perturbation in handling these problems. Also, the methods are very simple and can be implemented easily.