Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-06-02
2002-07-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06415426
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the placement of functional cells during integrated circuit design, and more particularly, to the use of timing information in the course of cell placement during computer automated circuit design.
2. Description of the Related Art
There is a burgeoning demand for smaller, faster, more versatile and more powerful integrated circuits (ICs) in a wide range of fields such as computing, communications, instrumentation, and control systems, for example. Advances in semiconductor technology have made it possible to construct transistors with dimensions that are so small that a single tiny IC chip can contain upwards of millions of transistors. The tremendous complexity of ICs requires the use of automated design tools to permit circuit designers to specify circuit functionality, to place the functional cells (e.g., transistors, circuit elements, objects or logic gates) on a floorplan of an IC chip, to route interconnecting wires between the placed cells and to test the resulting design to ensure that it meets requirements such as timing constraints.
Modern circuit design has evolved into a specialized field often referred to as electronic design automation in which computers and computer aided design (CAD) techniques are used to automate the IC chip design process. Computers can be programmed to reduce or decompose large, complicated circuit designs into a multitude of much simpler circuit design components. Computers can be programmed to develop an overall circuit design through a process of iterative solution of a multiplicity of smaller design problems that relate to the circuit design components. The computers can be programmed so that the design problems that relate to the circuit design components are solved so that design constraints for the overall circuit design are satisfied and the solution of the many smaller design problems results in convergence upon an acceptable overall circuit design.
Generally, an IC circuit design process begins with an engineer specifying the input/output signals, functionality and performance characteristics of the circuit. This information is provided to a computer that runs a logic synthesis program that generates a specification defining the integrated circuit in terms of a particular technology (e.g., very large scale integration). More specifically, the specification may include a netlist that specifies the interconnection of functional cells in the circuit. The specification serves as a template for the design of a physical embodiment of the circuit in terms of transistors, routing input and output pins, wiring and other features involved in the layout of the chip. The layout is a geometric or physical description of the IC that may consist of a set of geometric shapes in several layers.
An IC chip layout is designed by providing the specification to a computer that runs computer aided design programs that determine an optimal placement of functional cells and an efficient interconnection or routing scheme between cells to achieve the specified functionality. Computer implemented placement algorithms assign locations to the functional cells so that they do not overlap, so that chip area usage is optimized and so that interconnect distances are minimized. Chip area optimization permits more functional cells to fit into a given chip area. Wire length minimization reduces capacitive delays associated with longer nets so as to speed up the operation of the chip. Routing generally follows placement. Computer implemented routing algorithms determine the physical distribution of wire interconnects through the available space.
There are a number of different procedures for achieving optimal placement. The paper entitled, “A Procedure for Placement of Standard-Cell VLSI Circuits,” published in IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 1, January 1985, by Alfred E. Dunlop and Brian W. Kernighan, proposes one such placement procedure. The method is based on graph partitioning to identify groups of modules that should be close to each other, and a technique for properly accounting for external connections at each level of partitioning.
The paper entitled, “PROUD: A Fast Sea-of-Gates Placement Algorithm,” published in the 25
th
ACM/IEEE Design Automation Conference (1988), Paper 22.3, by Ren-Song Tsay, Ernest S. Kuh and Chin-Ping Hsu, describes a placement process that takes advantage of the inherent scarcity in the connectivity specification of an integrated circuit design. The method solves repeatedly sparse linear equations by the successive over-relation process in a top-down hierarchy. More specifically, the technique uses a quadratic placement formulation. It takes I/O pad specification as input and solves successive linear sparse equations. It depends upon the concept of resistive network optimization.
The paper entitled, “GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization,” published in IEEE Transactions on Computer-Aided Design, Vol. 10, No. 3, March 1991, by Jurgen M. Kleinhans, Georg Sigl, Frank M. Johannes, and Kurt Antreich, describes look-ahead methods incorporated in quadratic programs to hierarchically resolve routing congestion and reduce overall design area. The acronym GORDION stands for the two main parts of the method: global optimization and rectangle dissection, which is based on improved partitioning schemes.
FIG. 1
, taken from the paper by Kleinhans et al., shows overall data flow in the placement procedure of GORDION. The placement problem is formulated as a sequence of quadratic programming problems derived from the entire connectivity information of the circuit. Partitioning is employed to recursively create smaller and smaller placement subproblems. An increasing number of constraints restricting freedom of movement of the cells are imposed, reflecting successively refined partitioning. In this way, at each level of refinement, a global placement of cells is obtained simultaneously for all subproblems, avoiding any dependence on processing sequence.
U.S. Pat. No. 5,267,176 entitled, Method of Placing Modules on a Carrier, which issued on Nov. 30, 1993, to Antreich et al., describes a method that employs quadratic optimization. The method involves repetition of a global placement of cells on a placement region and subsequent partitioning. The global placement and partitioning steps are repeated until every sub-region contains at most a prescribed number of cells. The global placement ensues by arranging cells in the sub-regions such that the cells assigned to the sub-regions have their centers of gravity falling onto center coordinates of these sub-regions. The arrangement of all cells in all sub-regions is thereby simultaneously calculated. The sub-regions are defined by partitioning the placement region or, respectively, sub-regions, whereby a selectable number of cells are allocated to the sub-regions defined by partitioning.
U.S. Pat. No. 5,818,729 entitled, Method and System for Placing Cells using Quadratic Placement and a Spanning Tree Model, which issued on Oct. 6, 1998 to Chi-Hung Wang and Dwight D. Hill, discloses a placement method that uses a conjugate-gradient quadratic formula based placement system (e.g., GORDION) which inputs an integrated circuit design in a netlist form and generates a connectivity matrix for each multi-pin net within the design. The GORDION placement system performs global optimization using a conjugate gradient process to minimize wire lengths of circuit elements in nets. Partitioning also is performed. The clique model of a multi-pin net is used to generate first (or initial) connectivity matrices for the multi-pin nets which run through the global connectivity process. This first run provides a rough placement of the elements of the multi-pin nets. A spanning tree process is then run on the initial rough placement data and subsequent connectivity matrices are constructed using the spanning tree model, not the clique model, for multi-pin nets of within a defined siz
Chang Shing-Chong
Chen Ihao
Huang Shiang-Tang
Xiang Xuequn
Dinh Paul
Incentia Design Systems, Inc.
Morrison & Foerster / LLP
Smith Matthew
LandOfFree
Dynamic weighting and/or target zone analysis in timing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic weighting and/or target zone analysis in timing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic weighting and/or target zone analysis in timing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2863796