Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-12-02
2001-02-06
Lintz, Paul R. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06185724
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of logic mapping, placement and routing in programmable logic devices, and particularly to mapping, placement and routing in Field Programmable Gate Arrays (“FPGAs”).
BACKGROUND OF THE INVENTION
Simulated annealing (“SA”) is a method of optimizing properties of large, complex systems. Essentially, SA is optimization via random search. New states in the system are chosen at random, then compared to the current state and either accepted in place of the current state, or rejected. This random search continues until the system has converged to a final state that is acceptable based on a problem-specific cost function.
SA derives its name from a useful analogy drawn from the annealing of solids involving melting a substance, then carefully cooling it until a highly regular crystalline structure is formed. Making an analogy to the optimization of large, complex systems (such as the placement and routing of circuit elements in an FPGA), the cost function that describes the quality of a particular state of the system (implementation efficiency, or quality of the place and route solution) corresponds to the energy in the substance being annealed, variables in a system correspond to atoms in the substance being annealed, and the minimum in the cost function discovered during the optimization process corresponds to the highly regular crystalline structure that results from annealing.
The key innovation in SA was the introduction of effective temperature, T, into complex system optimization via random search. As with annealing of solids, the simulated annealing process begins with a high effective temperature and slowly reduces it. When the effective temperature has decreased such that the system being optimized has settled into a minimum in the cost function, C, the optimization process is complete.
Given an initial problem state, X
0
and an initial temperature, T
0
, a pseudo-code description of an available SA algorithm is shown in FIG.
1
.
At the core of the algorithm shown in
FIG. 1
are the two functions generate and accept. How the annealer generates a new problem state given the current state is encoded in the function generate (on line
4
of FIG.
1
). Function accept on line
5
determines whether the newly generated problem state replaces the current problem state. Using SA, new states are accepted not only when they cause a decrease (i.e., an improvement) in the cost, but, with a probability based on the temperature, also when they cause an increase in the cost. The probability of acceptance of states that increase cost lowers as temperature decreases. This behavior is codified in the accept function for SA, which is defined in Equation 1:
accept
=
TRUE
if
[
random
<
ⅇ
{
C
(
x
_
)
-
C
(
x
_
+
Δ
x
_
)
}
T
]
(
EQ
.
1
)
In Equation 1, random is a function that returns a uniform random number on the interval [0,1]. The behavior of Equation 1 is shown conceptually in
FIGS. 2A and 2B
. Downhill moves are moves to a new state with a lower cost than the present state, while uphill moves increase the cost. For a downhill move, C(x)−C(x+&Dgr;x) is positive, and the exponent in Equation 1 will be positive, so the function on the right of the inequality will yield a value larger than one. Since the range of random is [0,1], these downhill moves are accepted. The probability of accepting an uphill move depends on the ratio of the change in the cost function to the present temperature. For very hot temperatures, this ratio is small (the denominator in the exponent is far greater than the numerator) and almost all uphill moves are accepted. When the temperature has cooled such that it is only warm (FIG.
2
A), the probability of accepting a large uphill move is substantially reduced, but many smaller uphill moves are still accepted. When the temperature is reduced further to cool, the probability of accepting uphill moves also decreases, as illustrated in FIG.
2
B. This probability continues to drop until almost no uphill moves are accepted. At this point, the problem settles into the bottom of a valley in the cost surface and is considered to be frozen. Hot, warm, and cool temperatures are problem-specific; i.e., different systems will accept or reject states at different temperatures.
Returning again to
FIG. 1
, the functions frozen, update_temp, and done_at_temperature determine when annealing is finished, how the temperature is updated, and how many moves should be performed at each temperature, respectively. The initial temperature, T
0
, and these critical control functions are collectively referred to as the cooling schedule. Optimal cooling schedules have been the subject of much research and selection of an appropriate schedule is crucial to an efficient implementation. However, discussion of cooling schedules is beyond the scope of this background discussion and will be understood by one skilled in the art to which the present invention pertains without additional discussion.
Any SA solution to a specific problem can be described in terms of the four principal components of the algorithm:
x, the problem representation, which maps the problem being solved into the current state within the annealer;
generate, which implements the annealer's move-set (the set of possible perturbations referred to in Equation 1 as &Dgr;x, used by the annealer to manipulate the current state;
C(x), the cost function, which determines how the cost is calculated and what its components are;
and the cooling schedule, which controls T, directing the overall cooling process.
The most important decision to be made when designing an annealing implementation is how to handle constraints inherent in the problem being solved. For example, when trying to optimally place transistors on an integrated circuit (IC), the final solution is constrained such that none of the transistors can overlap. One way to handle these constraints within an annealing formulation is to penalize problem states that violate these constraints, by including penalty terms in the cost function. These penalty terms can be weighed against the other design objectives by using scalar weights, resulting in a weighted penalty function. However, not all constraints need be handled with a weighted penalty function; many constraints can be implemented either in the cost function or in the move-set. For example, simple bounds on the decision variables can be easily implemented in the move-set by simply not generating moves beyond the variable bounds. However, for more complex constraints, implementation is not so straightforward. In the case of optimal transistor placement on ICs, the constraint that transistors cannot overlap can be implemented by designing the move-set such that they never overlap, or by designing a cost function that penalizes illegal overlaps. Although the move-set approach is the most obvious solution, the cost function solution is easier to implement and is generally accepted as superior. The designer of any SA solution to a realistic problem will be faced with similar design trade-offs.
Annealing for FPGA Placement
The placement problem in FPGAs is often solved with SA. An FPGA is a regular, two-dimensional grid of logic blocks (“LBs”). Each LB can be programmed to perform a single, small function. Programmable routing connects the LBs.
The initial state of the user=s design and FPGA are shown conceptually in FIG.
3
. The user's design is on the left and is a collection of interconnected gates. The grid on the right shows the empty FPGA, where each square (defined by a unique coordinate pair) is an LB. The routing structure is not shown. A user's complete digital design is typically implemented on the FPGA in three steps: mapping, placement, and routing.
The mapping step comprises collecting gates into interconnected pieces called components. The results of the mapping step are shown in FIG.
4
. Each component is small enou
Cartier Lois D.
Crosby, Heafey Roach & May
Kik Phallaka
Lintz Paul R.
Tachner, Esq. Adam H.
LandOfFree
Template-based simulated annealing move-set that improves... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Template-based simulated annealing move-set that improves..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Template-based simulated annealing move-set that improves... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572912