Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-03-16
2003-06-03
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06574783
ABSTRACT:
The present invention relates to a chip planning method, and a chip planning tool and system.
One of the aspects of integrated circuit design is the determination of a floor plan for the circuit on a semiconductor chip. Once the functional blocks of the circuit and their interrelationship has been determined, an optimum floor plan needs to be determined and the objective is to find a solution that arranges and interconnects the blocks on a chip so as to satisfy a number of competing criteria. The criteria includes minimising layout area, routing congestion, path delay, and a target aspect ratio for the chip.
The difficulties associated with finding a satisfactory floor plan solution become more acute as the transistor count on a circuit increases, such as for a deep sub-micron or very deep sub-micron (DSM/VDSM) chip where the circuit may include over 10 million transistors and have an operating frequency exceeding 500 MHz. The transistors all need to be interconnected whilst meeting strict operation and performance criteria. Issues such as power dissipation, thermal distribution, electromagnetic compatibility (EMC), electromagnetic interference (EMI), signal integrity, clock skew/slow and metal electro-migration risk need to be catered for. The floor plan accordingly needs to be optimised with these criteria in mind to produce a successful DSM/VDSM design. Electronic design automation (EDA) tools are used by most chip designers, such as Intel and Lucent Technologies, to assist in producing a chip plan solution and reduce development cost.
Given the various competing criteria involved in producing a satisfactory chip plan, chip planning can be viewed as a multidimensional optimisation problem. The complexity of the problem is simplified by applying a block structure representation and hierarchical design methodology to the problem. The problem can be specified by:
1) A set of blocks, each of which has k≧1 alternative implementations. Each implementation is rectangular and either fixed or flexible. For a fixed block, the dimensions and exact pin locations are known. For a flexible or float block, the area is given but the aspect ratio and exact pin locations are unknown.
2) A specification of all nets and a set of paths. The nets are the interconnections of a set of pins of the circuit. Capacitances of sink pins, driver resistances of source pins, internal block delays and capacity and resistance of the interconnects is also specified to calculate path delays.
3) Technology information, such as the number of routing layers available on top of blocks and between blocks, wirepitch for interconnection and input/output pads information etc.
A solution to the problem may then specify the following:
1) A selected implementation for each block.
2) For each selected flexible implementation i, its dimensions w
i
and h
i
such that w
i
h
i
=A
i
and I
i
≦h
i
/w
i
≦u
i
, where A
i
is the given area of implementation i and I
i
and u
i
are given bounds on the aspect ratio of i, which is assumed to be continuous.
3) An absolute position of each block so that no pair of blocks are closer than a specified minimum distance. For multi-layer designs, it can be assumed that a significant part of the routing is performed on top of the blocks.
4) An orientation and reflection of each block. The term orientation of a block refers to a possible 90° rotation, while reflection refers to the possibility of mirroring the block around a horizontal and/or vertical axis.
5) A pin assignment for each flexible block so that the exact pin locations are fixed.
The complexity of the problem, or the amount of feasible solutions, is of the order:
O
(
k
N
*2
M−1
*(2M−3)!) (1)
where M is the number of blocks, N is the number of flexible blocks (N≦M) and k represents a potential aspect ratio grade for the flexible blocks. Finding an optimal solution for a problem with such a large multidimensional possible solution space has proved extremely difficult, and in particular, it has proved extremely difficult to develop a chip planning method which is computationally efficient for DSM/VDSM chip planning.
One chip planning method for finding and evaluating the possible solutions involves the use of the Genetic Algorithm (GA), such as the method described in H. Esbensen and E. S. Kuh, “Explorer: an interactive floorplanner for design space exploration”, Proc. of EuroDAC, 1986, which is herein incorporated by reference. The Genetic Algorithm is an evolutionary process developed by John Holland in 1992 which uses fixed length character strings to represent genetic information defining a set or population of individual solutions that can undergo evolutionary changes to produce optimal solutions. The algorithm begins by initially operating on a random population of possible solutions which are represented by respective gene strings. Each string can be evaluated by a decoder and a “fitness” score or rank assigned to it representing how good a solution it provides to the problem. The strings with the lower scores can then be discarded and the higher scoring strings can be continued by the algorithm. The remaining strings are then used to generate a new set of strings for evaluation. New strings are created by “crossover” which involves exchanging parts of a string between two parent strings of the previous generation. Also new strings are generated by the process of “mutation”, which involves making small random adjustments to the strings. After many generations, the population is then dominated by strings which represent the best possible solution to the problem.
The problem with existing genetic algorithm chip planning methods is that they are time consuming and computationally inefficient. They also have a low probability of reaching satisfactory solutions. For example, the work of the University of California, Berkeley, discussed in the article mentioned above adopts a sequential methodology with static optimisation processes and cannot ensure that an optimal solution for a DSM/VDSM chip is obtained.
In accordance with the present invention there is provided a chip planning method, including:
generating a population of gene strings representing floor plans for an integrated circuit;
executing crossover on said strings to generate crossover child strings;
executing mutation on said strings to generate mutated child strings;
applying operators to said strings to generate further child strings; and
evaluating said child strings for inclusion in said population.
Advantageously the further child strings may be generated by peristalsis operators based on a speckle model.
The present invention also provides a chip planning system, including:
means for generating a population of gene strings representing floor plans for an integrated circuit;
means for executing crossover on said strings to generate crossover child strings;
means for executing mutation on said strings to generate mutated child strings;
means for applying operators to said strings to generate further child strings; and
means for evaluating said child strings for inclusion in said population.
The present invention also provides a chip planning tool stored on computer readable storage media, including:
code for generating a population of gene strings representing floor plans for an integrated circuit;
code for executing crossover on said strings to generate crossover child strings;
code for executing mutation on said strings to generate mutated child strings;
code for applying operators to said strings to generate further child strings; and
code for evaluating said child strings for inclusion in said population.
Advantageously the tool may include code for executing dynamic control, dynamic ranking, block sizing and pin assignment.
REFERENCES:
patent: 5815403 (1998-09-01), Jones et al.
patent: 5875117 (1999-02-01), Jones et al.
patent: 6155725 (2000-12-01), Scepanovic et al.
Foo Han Yang
Zhuang Wen Jun
Institute of High Performance Computing
Renner Otto Boisselle & Sklar
Siek Vuthe
LandOfFree
IC chip planning method based on dynamic parallel genetic... 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 chip planning method based on dynamic parallel genetic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IC chip planning method based on dynamic parallel genetic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146237