Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-09-21
2003-06-24
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06584603
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a floor plan determination apparatus/method for the circuit, such as an LSI (Large Scale Integration) circuit, etc., and a program storage medium used to implement the apparatus, and in particular it relates to the apparatus/method for an LSI block of fixed shape and the medium used to implement such an apparatus.
Along with the recent advancement of circuit technologies, the degree of integration of an LSI (in particular a VLSI) has remarkably improved and the circuit size has also remarkably increased. Along with both the improvement in the degree of integration and the increase of the circuit size, the number of blocks and RAMs (RandomAccessMemory) included in one LSI has also increased. Therefore, if a layout of a floor plan is manually generated, an optimal layout cannot be always obtained and it also takes time. In this way, the development of a technology to enable the acquisition of an optimal floor plan in a small CPU time and to improve the turn around time is demanded.
2. Description of the Related Art
When the layout of an LSI is automatically generated, first, functions of the LSI are divided. Then, a chip area required to implement the respective functions is calculated. Finally, the LSI floor plan is determined by dividing the LSI chip area into a plurality of rectangular areas.
A floor plan optimization method by a slicing tree used in this method is widely known.
In the floor plan by a slicing tree, hierarchical partitioning is repeated and the rectangular shape and location of each LDS block are calculated. This hierarchical structure is expressed by a character string of Polish expression.
For example, if a vertical cutline and a horizontal cutline are expressed as “*” and “+”, respectively, the floor plan shown in
FIG. 1A
can be expressed by the following Polish expression, as shown in FIG.
1
B.
16+35*2+74+**
The “*” and “+” are called operators, and figures are called operands.
In the floor plan by a slicing tree, a floor plan is optimized by transforming this Polish expression, which means transforming the tree structure of a slicing tree.
As an optimization algorithm, for example, Simulated Annealing (hereinafter called “SA”) is used.
As shown in
FIG. 1C
, in this SA, the initial solution S
0
and initial temperature T
0
of Polish expression are set (step ST
1
), and Polish expression is operated at each set temperature T (step ST
8
) until the temperature reaches a stipulated termination temperature Tx (steps ST
2
, ST
3
and ST
4
). In this way, it is assumed that Polish expression is transformed from S to S′ and the cost of S Cost(S) and cost of S′ Cost(S′) at that time are calculated. Then, the following value is calculated (step ST
5
).
min(1,
e
−[Cost(S′)−Cost(S)]/T
)
If the value is larger than a random real value which is generated between 0 and 1, S is transformed to S′, and if the value is smaller than the value, S is not transformed (steps ST
6
and ST
7
). This operation is repeated and if the number of repetitions reaches a stipulated number MaxCount, temperature T is reduced toward Tx. In this way, the optimal solution of Polish expression is calculated.
As the transformation operation of Polish expression, exchanging two adjacent operands of Polish expression, or extracting a specific part of Polish expression and making a complement (transforming “*” to “+” or “+” to “*”) of an operator included in the art are prepared.
In SA, if Cost(S′)<Cost(S), the following inequality holds true.
e
−[Cost(S′)−Cost(S)]/T
>1
Therefore, the following equation holds true.
min(1,
e
−[Cost(S′)−Cost(S)]/T
)=1
In this way, if the value becomes larger than a random value which is generated between 0 and 1, S is always transformed to S′. Specifically, if the cost decreases (a high evaluation value is obtained), S is always transformed to S′.
However, if Cost(S′)>Cost(S), the following expression holds true.
e
−[Cost(S′)−Cost(S)]/T
=m<
1
In the above expression, the higher temperature T is, the closer to 1 m is. Therefore, the following inequality holds true.
min(1,
e
−[Cost(S′)−Cost(S)]/T
)<1
In this way, some time S is transformed to S′ and other times S is not transformed to S′ depending on a random value which is generated between 0 and 1. In this case, the higher the temperature, the higher a possibility that S may be transformed to S′.
Specifically, in SA, when the value is in the initial state of high temperature, S is sometimes transformed to S′ even if the cost increases. Therefore, there is a possibility of obtaining a better solution compared with another optimization algorithm, regardless of the initial solution.
In the conventional LSI floor plan by a slicing tree, division is made taking into consideration only the area of each LSI block and the shape. For example, a final cutline is drawn according to the division form specified by Polish expression and depending on the area of each LSI block. Therefore, if an LSI block the shape of which is specified must be laid out, a floor plan in which such an LSI block can be laid out cannot be prepared, which is a problem.
Specifically, a RAM of fixed shape, etc., is sometimes mounted on an LSI chip. In this case, in the conventional LSI floor plan by a slicing tree, if an LSI block of fixed shape, such as a RAM, etc., must be laid out, a floor plan cannot be prepared in such a way that an LSI block can be laid out since the shape of the LSI block is not taken into consideration, which is a problem.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an LSI floor plan determination apparatus for determining an LSI floor plan in such a way that the layout of an LSI block of fixed shape can also designated, a method there of and a program storage medium on which is recorded a program used to implement such an apparatus.
In the first aspect of the present information, the floor plan determination apparatus comprises an execution device, an assignment device and a determination device.
The execution device either inputs or generates the initial solution of layout descriptive information that describes the layout of circuit blocks, which is a circuit floor plan. The assignment device assigns the initial value of a rotation code indicating the orientation of a circuit block to a circuit block of fixed shape described in the layout descriptive information. The determination device determining a circuit floor plan by repeating a process of operating either the layout descriptive information or rotation code on a condition that a circuit block of fixed shape can be laid out, calculating the evaluation value of a floor plan obtained after the operation and judging whether either the layout descriptive information or rotation code should be modified, based on the evaluation value.
In the second aspect of the present invention, the floor plan determination apparatus comprises an execution device, an assignment device and a determination device.
The execution device executes either inputs or generates the initial solution of layout descriptive information that describes the layout of circuit blocks, which is a circuit floor plan omitting circuit blocks of fixed shape. The assignment device assigns the initial value of a circuit block of non-fixed shape, which is a parent block, including the circuit block of fixed shape, to the circuit block of fixed shape. The determination device determines a circuit floor plan by repeating a process of operating either the layout descriptive information or parent block, calculating the evaluation value of a floor plan obtained after the operation and judging whether either the layout descriptive information or rotation code should be modified, based on the evaluation value.
In the third aspect
Fujitsu Limited
Smith Matthew
Staas & Halsey , LLP
Tat Binh
LandOfFree
Apparatus and method for determining a circuit floor plan does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for determining a circuit floor plan, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for determining a circuit floor plan will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102706