Document Type

Technical Report

Publication Date

1988-04-01

Filename

WUCS-88-12.pdf

DOI:

10.7936/K73N21Q9

Technical Report Number

WUCS-88-12

Abstract

Since the paper by Kirkpatrick, Gelatt and Vecchi in 1983, the use of Simulated Annealing (SA) in solving combinatoric optimization problems has increased substantially. The SA algorithm has been applied to difficult problems in the difficult problems in the digital design automation such as cell placement and wire routing. While these studies have yielded good or near optimum solutions, they have required very long computer execution times (hours and days). These long times, coupled with the recent availability of the number of commercial parallel processors, has prompted the search for parallel implementations of the SA algorithm. The goal ahs been to obtain algorithmic speedup through the exploitation of parallelism. This paper presents a method for mapping the SA algorithm onto a dynamically structured tree of processors. Such a tree of processors can be mapped onto both shared memory and message based styles of parallel processors. The parallel SA (PSA) algorithm is discussed and its performance evaluated using simulation techniques. An important property of the PSA algorithm presented is that it maintains the same move decision sequence as the Serial SA (SSA) algorithm this avoiding problems associated with move conflicts, erroneous move acceptance/rejection decisions and oscillations which have been associated with other PSA algorithm proposals. The PSA algorithm presented fully preserves the convergence properties of the SSA algorithm with speedups varying roughly as log2N where N is the number of processors in the parallel processor.

Comments

Permanent URL: http://dx.doi.org/10.7936/K73N21Q9

Download

Share

COinS