A speculative parallel simulated annealing algorithm based on Apache Spark

作者：Wang, Zhoukai; Zhao, Yinliang^*; Liu, Yang; Lv, Cuocuo

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2018, 30(14): e4429.

DOI：10.1002/cpe.4429

• Apache Spark
• parallel computing
• simulated annealing
• thread level speculation

Simulated annealing (SA) is an effective method for solving unconstrained optimization problems and has been widely used in machine learning and neural network. Nowadays, in order to optimize complex problems with big data, the SA algorithm has been implemented on big data platform and obtains a certain speedup. However, the efficiency for such implementation is still limited because the conventional SA algorithm still runs with low parallelism on new platforms and the computing resource cannot be fully utilized. For these problems, this paper raised a speculative parallel SA algorithm based on Apache Spark to expand the algorithm's parallelism and enhance its efficiency. In this paper, first, the inner dependencies, which stop conventional algorithm, run in parallel, are analyzed. Then, based on the analysis, the Software Thread-Level Speculation technique is employed to help the conventional algorithm overcome the dependencies and make it run concurrently. Finally, a new parallel SA algorithm with speculation mechanism is proposed and implemented on Apache Spark. The experiments show that, for big data problems, the proposed algorithm could achieve an optimal parallelism when comparing the traditional algorithm without speculation on Apache Spark. Moreover, the execution efficiency of simulated annealing process can be markedly enhanced by the proposed algorithm.

• 出版日期2018-7-25
• 单位西安交通大学