e-space
Manchester Metropolitan University's Research Repository

    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: IEEE Symposium Series on Computational Intelligence, 05 December 2016 - 09 December 2016, Athens.

    [img]
    Preview
    Accepted Version
    Available under License In Copyright.

    Download (570kB) | Preview

    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 R Xeon PhiTM 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.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    148Downloads
    6 month trend
    320Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record