Ottimizzazione parallela con simulated annealing e calcolo speculativo

Simulated Annealing (SA) is a Monte Carlo search technique for obtaining approximate solutions to combinatorial problems depending from independent variables with many degrees of freedom. In this paper a new parallel SA algorithm which exploits the technique of speculative computation is presented. The proposal sensibly shortens the high computational costs of traditional SA implementations without violating its serial decision sequence. Our implementation is similar to that proposed by Witte, Chamberlain e Franklin [9], althoug characterized by a higher flexibility and by an enhanced dynamic behavior which allows the efficient exploitation of more parallelism. Results achieved on a nCUBE 2 multicomputer running our parallel SA algorithm applied to a VLSI placement and routing problem are reported and analyzed.