We aim to accelerate the simulated annealing algorithm by leveraging the power of GPU parallel computation among other optimization techniques. In order to verify our solution, we will implement an efficient solver for the competitive programming problem Legendary Dango Maker https://www2.ioi-jp.org/camp/2020/2020-sp-tasks/index.html, and compare its performance against a sequential baseline.
./solver > testcase/in/01.txt > result/01.txt
./checker testcase/in/01.txt score_table/01.txt result/01.txt
According to An efficient implementation of parallel simulated annealing algorithm in GPUs, parallel techniques include:
-
Dividing the searching into smaller regions,
-
Simulating the process with multiple Markov chains, and
-
Other application-wise approaches.
To come up with implementation that specifically accelerate the simulation process based on the properties of the testing scenario, we plan to explore possible methods with the following steps:
-
Establish a baseline with a sequential implementation of the simulated annealing algorithm.
-
Simulate multiple Markov chains asynchronously, where solutions are exchanged only at the end of the whole process.
-
Simulate multiple Markov chains synchronously, where solutions are exchanged for each temperature stage.
-
Divide the searching domain into multiple parts for simulation, with each processing unit focusing on its own part.
-
Other techniques that help improve performance, especially optimizations specific to the problem of interest.