Parallel implementations of the statistical cooling algorithm

Statistical Cooling is an optimization technique based on Monte-Carlo techniques. Here we propose two parallel formulations of the statistical cooling algorithm, i.e. a systolic algorithm and a clustered algorithm. Both algorithms are based on the requirement that quasi-equilibrium is preserved throughout the optimization process. It is shown that the parallel algorithms can be executed with a polynomial-time complexity. Performance of the algorithms is discussed by means of implementations on an experimental multi-processor architecture. It is concluded that substantial reduction of computation time can be achieved by both parallel algorithms compared to the sequential algorithm.