Page 336 - DSP Integrated Circuits

7.6 Scheduling Algorithms 321

Figure 7.50 Rate optimal operation schedule

point of view. The resulting schedule is shown in Figure 7.50. Thus, this approach
does not contain a minimization step—for example, minimization of the amount of
resources. It only finds a feasible rate optimal schedule. However, it may be
possible in a subsequent design step to move operations in time so that the
required number of processors is minimized.

7.6.8 Simulated Annealing
In 1953, Metropolis et al. proposed an algorithm for simulation of how a solid
reaches thermal equilibrium. Almost 30 years later, Kirkpatrick et al. and Cerny
realized that there is a simple analogy between certain combinatorial optimization
problems and the slow cooling of a solid until it reaches its thermal equilibrium.
For example, an almost perfect monolithic Si crystal is grown from a seed
crystal dipped into the silicon melt and a large crystal rod is formed if the seed is
pulled out of the melt sufficiently slowly. At high temperatures, the molecules in
the crystal will move about randomly. When the temperature is slowly reduced,
the molecules tend to move to positions corresponding to a lower energy state
(perfect crystal) and it becomes less likely that they move away from these posi-
tions as the temperature decreases. However, there is a small possibility that a
molecule may temporarily move to a position with higher energy. Such moves to
unfavorable positions are important for the annealing process in order to allow
the perfect crystal to be formed. This means that the optimization algorithm
does not get stuck in local minima. This property distinguishes simulated
annealing from gradient methods which seek a solution in the direction of the
largest derivative—i.e., the latter methods try to decrease the cost function as
fast as possible.
Finally, at zero temperature, the molecules occupy states corresponding to the
global energy minimum. The process of cooling a physical system until it reaches
its low-energy ground state is called annealing. By simulating such a cooling pro-
cess, near global-optimum solutions can be found. Simulated annealing is useful
for solving large combinatorial problems with many degrees of freedom [10, 16,
21]. The simulated annealing algorithm is shown in Box 7.6.