The Effect of Speculative Computation on Combinatorial Optimization Problems
Abstract
In recent years, multicore or many-core processors have gained significant attention as they enable computation with a large degree of parallelism on desktop computers. However, conventional parallel processing methods often cannot easily achieve parallel effects due to various factors. In this study, we evaluated the effect of applying MultiStartbased speculative parallel computation to combinatorial optimization problems. Using probability theory, we performed theoretical verification to determine whether speculative computation is more effective than conventional parallel computation methods. In addition, we conducted experiments and compared the result with those of conventional parallel processing. In this paper, we report the results of the theoretical verification and experiments, and we show that speculative computation is more effective than conventional parallel processing.
References
R. B. Osborne, Speculative computation in multilisp, pp. 103–137. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990.
R. Martí, Multi-Start Methods, pp. 355–368. Boston, MA: Springer US, 2003.
Y. Iizuka, A. Hamada, and Y. Suzuki, “Stochastic speculative computation method and its application to monte carlo molecular simulation,” in Proceedings of Hawaii International Conference on System Sciences 2018, pp. 1660–1668, 2018.
Y. Suzuki, A. Hamada, and Y. Iizuka, “Stochastic speculative computation method on general purpose graphics processing units,” in 2017 6th IIAI International Congress on Advanced Applied Informatics (IIAI-AAI), pp. 1049–1050, July 2017.
G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities,” in Proceedings of the April 18-20, 1967, Spring Joint Computer Conference, AFIPS ’67 (Spring), (New York, NY, USA), pp. 483–485, ACM, 1967.
A. Sohn, Z. Wu, and X. Jin, “Parallel simulated annealing by generalized speculative computation,” in Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on, pp. 416–419, Dec 1993.
K. L. Wong and A. G. Constantinides, “Speculative parallel simulated annealing with acceptance prediction,” IEE Proceedings - Computers and Digital Techniques, vol. 143, pp. 219–223, Jul 1996.
I. D. Falco, R. D. Balio, E. Tarantino, and R. Vaccaro, “Improving search by incorporating evolution principles in parallel tabu search,” in 1994 IEEE Conference on Evolutionary Computation, pp. 823–828, 1994.
R. Shonkwiler and E. Van Vleck, “Parallel speed-up of monte carlo methods for global optimization,” Journal of Complexity, vol. 10, no. 1, pp. 64–95, 1994.
X. Hu, R. Shonkwiler, and M. C. Spruill, Random restarts in global optimization. Georgia Institute of Technology, 2009.
M. Samadi, A. Hormati, J. Lee, and S. Mahlke, “Paragon: Collaborative speculative loop execution on gpu and cpu,” in Proceedings of the 5th Annual Workshop on General Purpose Processing with Graphics Processing Units, GPGPU-5, (New York, NY, USA), pp. 64–73, ACM, 2012.
V. Krishnan and J. Torrellas, “Hardware and software support for speculative execution of sequential binaries on a chip-multiprocessor,” in Proceedings of the 12th International Conference on Supercomputing, ICS ’98, (New York, NY, USA), pp. 85–92, ACM, 1998.
Z.-H. Du, C.-C. Lim, X.-F. Li, C. Yang, Q. Zhao, and T.-F. Ngai, “A cost-driven compilation framework for speculative parallelization of sequential programs,” SIGPLAN Not., vol. 39, pp. 71–81, June 2004.
L. Yan, “Solving combinatorial optimization problems with line-up competition algorithm,” Computers & Chemical Engineering, vol. 27, no. 2, pp. 251 – 258, 2003.
C. P. Gomes and B. Selman, “Algorithm portfolios,” Artif. Intell., vol. 126, pp. 43–62, 2001.
E. Aarts and J. Korst, Simulated annealing and boltzmann machines. New York, NY; John Wiley and Sons Inc., Jan 1988.
W. Weibull et al., “A statistical distribution function of wide applicability,” Journal of applied mechanics, vol. 18, no. 3, pp. 293–297, 1951.
