Parallel algorithms with quality equivalent to the Simulated Annealing placement algorithm for Standard Cells are_presented. The first, called Heuristic Spanning, creates parallelism by investigating different areas of the combinatorial search space. It is meant to replace the high temperature portion of Simulated Annealing which, it is shown, is the part of the Algorithm that chooses the general location of each cell. The Max-Span algorithm is presented, which chooses a spanning set of seed cells for the initial partitioning step of a Min-Cut placement algorithm. The Min-Cut algorithm is run on separate processors, each using a different seed cell, after which the interim placement with the best cost function is chosen for the low temperature annealing.

The low temperature portion of Simulated Annealing is sped up by a technique called Section Annealing. The placement is geographically divided and the pieces are assigned to separate-processors. Each processor generates Simulated Annealing-style moves for the cells in its area. The processors communicate the moves they accept using one of two schemes:​ Full-Broadcast, in which all processors are informed of all moves, and on a Need-to-Know basis in which only the processors that could possibly be affected are told of other processors’ moves. Section Annealing is shown to converge to the same final cost function as regular Simulated Annealing.

Both approaches achieve significant speedup over uniprocessor Simulated Annealing, giving high quality VLSI placement of Standard-Cells in a short period of time. Section Annealing is implemented on a five processor prototype multiprocessor, and estimated speedup is given for up to ten processors.