next up previous contents index CD CD Algorithms
Next: Neural Networks Up: Simulated Annealing Previous: Independent Set

Circuit Board Placement

In designing printed circuit boards, we are faced with the problem of positioning modules (typically integrated circuits) on the board. Desired criteria in a layout include (1) minimizing the area or aspect ratio of the board, so that it properly fits within the allotted space, and (2) minimizing the total or longest wire length in connecting the components. Circuit board placement is an example of the kind of messy, multicriterion optimization problems for which simulated annealing is ideally suited.  

Formally, we are given a collection of a rectangular modules tex2html_wrap_inline25893 , each with associated dimensions tex2html_wrap_inline25895 . Further, for each pair of modules tex2html_wrap_inline25897 , we are given the number of wires tex2html_wrap_inline25899 that must connect the two modules. We seek a placement of the rectangles that minimizes area and wire-length, subject to the constraint that no two rectangles overlap each other.

The state space for this problem must describe the positions of each rectangle. To provide a discrete representation, the rectangles can be restricted to lie on vertices of an integer grid. Reasonable transition mechanisms including moving one rectangle to a different location, or swapping the position of two rectangles. A natural cost function would be


where tex2html_wrap_inline25901 , tex2html_wrap_inline25903 , and tex2html_wrap_inline25905 are constants governing the impact of these components on the cost function. Presumably, tex2html_wrap_inline25907 should be an inverse function of temperature, so after gross placement it adjusts the rectangle positions so they are distinct.

Simulated annealing performs well on such module placement problems. Indeed, a similar application appeared in the original paper on simulated annealing [KGV83]. More details on these and other applications appear in [AK89].

Mon Jun 2 23:33:50 EDT 1997