VLSI Floorplanning / Simulated Annealing
This applet illustrates the application of Simulated Annealing to VLSI Floorplanning. Simulated Annealing is a general approach to optimization in which small transformations called moves are randomly applied to a configuration (in our case, floorplanning). Moves that decrease the cost of the configuration are always accepted, while moves that increase the cost function are accepted probabilistically under the control of a temperature parameter. As annealing proceeds, the temperature is slowly lowered.
The applet displays two panels. On the left, it displays a diagram of a floorplan and its estimated cost. On the right, it displays annealing status information, controls, and a plot of maximum (red), average (black), and minimum (green) accepted configuration costs at each temperature.
An options panel allows the user to set initial temperature, moves per temperature, and annealing speed. In addition, individual moves can be displayed, or only summary information at the end of each temperature.
NOTE:This applet requires the Sun Java Plugin to run under Windows.
If you're interested, here is the source code
For more information about Placement, see a VLSI CAD textbook such as M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996.
For an introduction to Simulated Annealing, see R. Rutenbar, "Simulated Annealing Algorithms: an Overview", IEEE Circuits and Devices Magazine, January 1989.