Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-11-22
2001-09-18
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06292929
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuit layout, and more specifically to the art of placement and routing of cells on integrated circuit chips.
2. Description of Related Art
a. Introduction
Microelectronic integrated circuits consist of a large number of electronic components which are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in the various layers of the silicon chip.
The process of converting the specifications of an electrical circuit into a layout is called the physical design. Physical design requires arranging elements, wires, and predefined cells on a fixed area, and the process can be tedious, time consuming, and prone to many errors due to tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. Feature size may be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 10 million transistors or approximately 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This feature size decrease/transistor increase trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit. Larger chip sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The object of physical chip design is to determine an optimal arrangement of devices in a plane and to find an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on the chip surface is at a premium, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including genetic algorithms such as simulated evolution, force directed placement or simulated annealing, described hereinbelow, and comparing the resulting placements using a cost criteria.
Depending on the input, placement algorithms are classified into two major groups, constructive placement and iterative improvement methods. The input to the constructive placement algorithms consists of a set of blocks along with the netlist. The algorithm provides locations for the blocks. Iterative improvement algorithms start with an initial placement. These algorithms modify the initial placement in search of a better placement. The algorithms are applied in a recursive or an iterative manner until no further improvement is possible, or the solution is considered to be satisfactory based on a predetermined criteria.
Iterative algorithms can be divided into three general classifications: simulated annealing, simulated evolution and force directed placement. The simulated annealing algorithm simulates the annealing process that is used to temper metals. Simulated evolution simulates the biological process of evolution, while the force directed placement simulates a system of bodies attached by springs.
Assuming that a number N of cells are to be optimally arranged and routed on an integrated circuit chip, the number of different ways that the cells can be arranged on the chip, or the number of permutations, is equal to N! (N factorial). In the following description, each arrangement of cells will be referred to as a placement. In a practical integrated circuit chip, the number of cells can be hundreds of thousands or millions. Thus, the number of possible placements is extremely large.
Interactive algorithms function by generating large numbers of possible placements and comparing them in accordance with some criteria which is generally referred to as fitness. The fitness of a placement can be measured in a number of different ways, for example, overall chip size. A small size is associated with a high fitness and vice versa. Another measure of fitness is the total wire length of the integrated circuit. A high total wire length indicates low fitness and vice versa.
The relative desirability of various placement configurations can alternatively be expressed in terms of cost, which can be considered as the inverse of fitness, with high cost corresponding to low fitness and vice versa.
b. Simulated Annealing
Basic simulated annealing per se is well known in the art and has been successfully used in many phases of VLSI physical design such as circuit partitioning. Simulated annealing is used in placement as an iterative improvement algorithm. Given a placement configuration, a change to that configuration is made by moving a component or interchanging locations of two components. Such interchange can be alternatively expressed as transposition or swapping.
In the case of a simple pairwise interchange algorithm, it is possible that a configuration achieved has a cost higher than that of the optimum, but no single interchange can cause further cost reduction. In such a situation, the algorithm is trapped at a local optimum and cannot proceed further. This happens quite often when the algorithm is used in practical applications. Simulated annealing helps to avoid getting achieving and maintaining a local optima by occasionally accepting moves that result in a cost increase.
In simulated annealing, all moves that result in a decrease in cost are accepted. Moves that result in an increase in cost are accepted with a probability that decreases over time as the iterations proceed. The analogy to the actual annealing process is heightened with the use of a parameter called temperature T. This parameter controls the probability of accepting moves that result in increased cost.
More of such moves are accepted at higher values of temperature than at lower values. The algorithm starts with a very high value of temperature that gradually decreases so that moves that increase cost have a progressively lower probability of being accepted. Finally, the temperature reduces to a very low value which requires that only moves that reduce costs are to be accepted. In this way, the algorithm converges to an optimal or near optimal configuration.
In each stage, the placement is shuffled randomly to get a new placement. This random shuffling could be achieved by transposing a cell to a random location, a transposition of two cells, or any other move that can change the wire length or other cost criteria. After the shuffle, the change in cost is evaluated. If there is a decrease in cost, the configuration is accepted. Otherwise, the new configuration is accepted with a probability that depends on the temperature.
The temperature is then lowered using some function which, for example, could be exponential in nature. The process is stopped when the temperature is dropped to a certain level. A number of variations and improvements on the basic simulated annealing algorithm have been developed. An example is described
Andreev Alexander E.
Jones Edwin
Koford James S.
Pavisic Ivan
Scepanovic Ranko
Do Thuan
LSI Logic Corporation
Smith Matthew
LandOfFree
Advanced modular cell placement system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Advanced modular cell placement system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Advanced modular cell placement system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2526261