LAYOUT BY ANNEALING IN A PARALLEL ENVIRONMENT.

The role of performance modeling in the implementation and evaluation of annealing-based parallel-placement algorithms is examined. The statistical behavior of an annealing algorithm changes profoundly as it runs, a characteristic that suggested adaptive parallel decompositions that dynamically alter the parallel partitioning to optimize speedup over each different regime of the annealing problem. A probabilistic model is derived for a two-strategy adaptive partitioning of standard cell placement on a shared-memory multiprocessor. The model correctly predicts how to switch strategies to maximize speedup.