Rectangular spatial decomposition methods for parallel simulated annealing

Abstract

Research on VLSI placement has extended the standard sequential simulated annealing technique to two multiprocessing variants. In one technique, processors perform moves on disjoint partitions of locally-stored circuit grids. In the other, processors perform simultaneous moves on a shared grid. Our research explores new techniques in the first category-called spatial decomposition algorithms. We describe the impact of cell mobility and cost-function errors in parallel simulated annealing. We show that changing the partition shape can affect these measures, and the quality of the final result. We also show a trade-off: execution speed vs. increased cell mobility and decreased cost-function errors. We present four rectangular decomposition methods. Using two circuit examples, we compare their convergence properties to that of a "standard" random spatial decomposition technique. Runs were performed in a simulated RP3 environment. One method we developed, "sharp random rectangles," converged better than the other techniques we studied. On one example, sharp random rectangles on 8 processors converged better than standard sequential algorithms. This promising technique allows us to increase the stream-length, and thereby reduce execution time. The authors continue their research to better quantify cell mobility and cost-function errors, and to run the rectangular algorithms on other types of multiprocessors to obtain speed-up information.