Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-06-18
2001-08-28
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06282694
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to an improved method for generating optimized floorplans for design blocks, using ceiling and floor contours on an O-tree structure.
2. Background Information
As the complexity of IC design continues to increase, pre-existing design hierarchies or design blocks are increasingly being “re-used” to simplify the design task. Floorplanning or building block placement is becoming critical to the performance of the hierarchical design process.
In the case of floorplan with slicing structure, it is known to use a binary tree representation to perform the building block placement operation. The leaves of the binary tree correspond to the blocks and each internal node defines a vertical or horizontal merge operation of its two descendents. The number of possible configurations for the tree, and therefore the extent of computation is in the order of O(n!2
5n−3
1.5
). There have been efforts to identify the redundancy among the possible configurations, and thereby reducing the amount of computation. See e.g. D. F. Wong, and C. L. Lin,
A New Algorithm for Floorplan Design
, DAC, pp. 101-107, 1986.
Efforts have also been made to extend the binary tree representation to floorplan with non-slicing structure. See e.g. P. Pan and C. L. Liu,
Area Minimization for Floorplans
, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp. 123-132, January, 1995; and T. C. Wang, and D. F. Wong,
An Optimal Algorithm for Floorplan Area Optimization
, DAC, pp. 180-186, 1990. However, the performance of these approaches have been less desirable.
Onodera et al. further classify topological relationship between two blocks in a floorplan with non-slicing structure into four classes, and use branch-and-bound method to solve the problem. See H. Onodera, Y. Taniguchi, K. Tamaru,
Branch
-
and
-
Bound Placement for Building Block Layout
, DAC, pp. 433-439, 1991. The disadvantage of the approach is that the solution space is still in the order of O(2
n(n+2)
), which is too complicated even for today's high performance computers.
Sequence pair and bounded slicing grid have been introduced the reduce the solution space for the floorplan with non-slicing structure problem. See e.g. H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajatani,
Rectangular
-
Packing-Based Module Placement
, ICCAD, pp. 472-479, 1995; and S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajatani,
Module Placement on BSG
-
Structure and IC Layout Application
, ICCAD, pp. 484-491, 1996. The two approaches are different representations, but they are all basically based on constraint graph to manipulate the transformation between the representation and their placement, which unfortunately also requires intensive amount of computation. When using the sequence pair representation, two sets of permutations are employed to present the geometric relations of the blocks. The possible configurations are in the order of O((n!)
2
). From sequence pair to its placement, the transformation operation takes O(n log n) time. See e.g. T. Takahasi,
An Algorithm for Finding a Maximum
-
Weight Decreasing in a Permutation, Motivated by Rectangle Packing Problem
, IEICE, vol. VLD96, pp. 31-35, 1996. When using the bounded slicing grid approach, an n by n grid plane is used for placement of n blocks. The representation itself has much dependency, one floorplan could have several choices of representations, resulting inefficient and wasteful computation.
An iterative approach employing cluster refinement has also been proposed to optimize area and interconnection. See e.g. J. Xu, P.N. Guo, and C.K. Cheng,
Cluster Refinement for Block Placement
, DAC, pp. 762-765, 1997. For small cluster sizes (k), the run time complexity for each iteration is in the order of O(n
2+k/2
). However, for larger cluster sizes, the approach is too CPU-intensive and difficult to handle.
Finally, most recently, Guo and Cheng have devised an ordered tree (O-tree) structure to represent placement of design blocks. A deterministic approach was developed to search for an O-tree representation that corresponds to an optimal placement. Under te deterministic approach, design blocks and candidate “reinsertion” points are systematically analyzed with respect to a cost function to find the optimal placement. Experience has shown the deterministic approach to be still too time consuming.
Thus, an improved approach to design block placement and floorplan generation is desired.
Note: The concept of O-tree and the deterministic approach to seeking the optimal placement will be the subject of a presentation in the upcoming Design Automation Conference, Jun. 21-25, 1999, accordingly published as part of the Proceedings of the conference in a future day. The concept of O-tree and the deterministic approach is thus also explained as foundational materials in the description of the improved approach of the present invention to follow.
SUMMARY OF THE INVENTION
An EDA tool is provided with a floorplan generator to automatically generate an optimized floorplan for an IC design having a number of design blocks. The floorplanner generates an initial O-tree representation for the design blocks. The floorplanner then perturbs the O-tree representation to seek an alternate O-tree representation that represents an optimized placement of the design blocks in accordance with a cost function. The floorplanner performs the perturbation systematically for all design blocks, traversing the O-tree representation in a depth-first manner and removing one design block at a time. For each removed design block, the floorplanner also seeks an appropriate re-insertion point for the removed design block systematically, by traversing a reduced version of the O-tree representation augmented with candidate insertion points in a depth-first manner. Under the present invention, ceiling and floor contours as well as contour pointers are employed to improve the efficiency of the traversing iterations.
REFERENCES:
patent: 4554625 (1985-11-01), Otten
patent: 5657239 (1997-08-01), Grodstein et al.
patent: 5748486 (1998-05-01), Ashar et al.
patent: 5818729 (1998-10-01), Wang et al.
patent: 6009250 (1998-10-01), Ho et al.
patent: 6086626 (2000-07-01), Jain et al.
Cai et al., “Conflict-free channel definition in building-block layout”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, No. 9, pp. 981-988. Sep. 1989.*
Herrigel, “GRCA: a global approach for floorplanning synthesis in VLSI macrocell design”, 1990 IEEE International Conference on Computer-Aided Design, Nov. 1990, ICCAD-90, pp. 152-155, Nov. 1990.*
Song et al., “A new model for general connectivity and its application to placement”, proceedings of Sixth Great Lakes Symposium on VLSI, Mar. 1996, pp. 60-63.*
Cai, “On Empty Rooms in Floorplan Graphs: Comments on a deficiency in Two Papers”, IEEE Transactions on Computer-Aided Design, vol. 8, No. 7, pp. 795-797, Jul. 1989.*
Xu et al. (“Cluster refinement for block placement”, Proceedings of the 34th Annual ACM IEEE Design Automation Conference, pp. 762-765), Jun. 1997.
Cheng Chung-Kuan
Guo Pei-Ning
Columbia IP Law Group, PC
Kik Phallaka
Smith Matthew
LandOfFree
IC design floorplan generation using ceiling and floor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with IC design floorplan generation using ceiling and floor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IC design floorplan generation using ceiling and floor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546653