A Parallel Simulated Annealing Algorithm Based On Fine-grained Model With GPU-Acceleration

Simulated annealing algorithm (SA), derived from the principle of solid annealing, is a general probabilistic algorithm and used to find the optimal solution of the problem in large search space. As in the settlement of large-scale optimization problems, SA algorithm usually requires a lot of computing time, parallel SA algorithm gradually becomes research hotspot. At present parallel SA algorithm is mostly run on parallel machine or simulated by multi-thread technology, however, existing the following deficiencies: The communication consumption between processes confines the population of threads; Multi-threading technology couldn't truly improve performance because it just runs on common CPU with serial-parallel simulation; Most researchers can not be accessable to above parallel machine equipments, and it also seems much more complex to use them.In recent years, GPU has a rapid development, owing to its high speed floating point operations, parallelism and programmability, provideing an ideal parallel platform for general-purpose computation. Additionally, Compute Unified Device Architecture (CUDA), launched by NVIDIA Corporation, gves researchers a more convenient way to data parallel processing.The paper, aiming at those problems in parallel SA algorithm, raises a fine-grained SA algorithm based on GPU acceleration. This method converts the process of working-out into the execution of kernels based CUDA using a thread block to simulate Markov chain, speeds up its running and provides ordinary users with a feasible SA algorithm. The excutive model of GPU using CUDA is parallel threads, and the threads in the same block can access shared memory and can synchronize rapidly. This paper, taking the parallelization of Markov chain for example, describes the algorithm's design and programming. Meanwhile, it gives many results applying to symmetric traveling salesman problems, and analyses the properties of parallel SA algorithm based on the comparison with the relevant sequential version. The analytical results demonstrate that the proposed algorithm achieves a good optimization effect and increases the population size in the fine-grained parallelism while speeding up its execution.