A highly parallelized and vectorized implementation of Max-Min Ant System on Intel® Xeon Phi™

Lloyd, Huw and Amos, Martyn (2016) A highly parallelized and vectorized implementation of Max-Min Ant System on Intel® Xeon Phi™. In: 2016 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE. ISBN 978-1-5090-4241-8

Full text not available from this repository.

Abstract

The increasing trend in processor design towards many-core architectures with wide vector processing units is largely motivated by the fact that single core performance has hit a “power wall”, meaning that performance gains are currently achievable only through increasingly parallel and vectorized execution models. Consequently, applications can only exploit the full performance of modern processors if they achieve high parallel and vector efficiencies. In this paper, we illustrate how this might be achieved for the well-established Ant Colony Optimization metaheuristic. We describe a highly parallel and vectorized variant of the Max-Min Ant System algorithm applied to the Traveling Salesman Problem, and present two novel vectorized algorithms for selecting cities during the tour construction phase. We present experimental results from an implementation on the Intel® Xeon Phi™ platform, which show that very high parallel and vector efficiencies are achieved, and significant speedups are obtained compared to both the reference serial implementation and the previous best Xeon Phi implementation available in the literature.

Item Type:	Book Section
Subjects:	G400 Computer Science
Department:	Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User:	Becky Skoyles
Date Deposited:	18 Sep 2018 12:15
Last Modified:	11 Oct 2019 19:15
URI:	http://nrl.northumbria.ac.uk/id/eprint/35766

Downloads