Skip to main content
Erschienen in: The Journal of Supercomputing 11/2017

16.08.2017

Efficient exploitation of the Xeon Phi architecture for the Ant Colony Optimization (ACO) metaheuristic

verfasst von: Felipe Tirado, Ricardo J. Barrientos, Paulo González, Marco Mora

Erschienen in: The Journal of Supercomputing | Ausgabe 11/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In recent years, the use of compute-intensive coprocessors has been widely studied in the field of Parallel Computing to accelerate sequential processes through a Graphic Processing Unit (GPU). Intel has recently released a GPU-type coprocessor, the Intel Xeon Phi. It is composed up to 72 cores connected by a bidirectional ring network with a Vector Process Unit (VPU) on large vector registers. In this work, we present novel parallel algorithms of the well-known Ant Colony Optimization (ACO) on the recent many-core platform Intel Xeon Phi coprocessor. ACO is a popular metaheuristic algorithm applied to a wide range of NP-hard problems. To show the efficiency of our approaches, we test our algorithms solving the Traveling Salesman Problem. Our results confirm the potential of our proposed algorithms which led to distinct improvements of performance over previous state-of-the-art approaches in GPU. We implement and compare a set of algorithms to deal with the different steps of ACO. The matrices calculation in the proposed algorithms efficiently exploit the VPU and cache in Xeon Phi. We also show a novel implementation of the roulette wheel selection algorithm, named as UV-Roulette (unique random value roulette). We compare our results in Xeon Phi to state-of-the-art GPU methods, achieving higher performance with large size problems. We also exposed the difficulties and key hardware performance factors to deal with the ACO algorithm on a Xeon Phi coprocessor.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, CambridgeMATH Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, CambridgeMATH
4.
Zurück zum Zitat Dorigo M (1992) Optimization, learning and natural algorithms. Ph.D. thesis, Politecnico di Milano, Italy Dorigo M (1992) Optimization, learning and natural algorithms. Ph.D. thesis, Politecnico di Milano, Italy
6.
Zurück zum Zitat Hwu W (2012) Programming massively parallel processors, second edition: a hands-on approach. Morgan Kaufmann, Burlington Hwu W (2012) Programming massively parallel processors, second edition: a hands-on approach. Morgan Kaufmann, Burlington
7.
Zurück zum Zitat Jeffers J, Reinders J (2013) Intel Xeon Phi coprocessor high performance programming. Elsevier, Philadelphia. ISBN:9780124104143 Jeffers J, Reinders J (2013) Intel Xeon Phi coprocessor high performance programming. Elsevier, Philadelphia. ISBN:9780124104143
8.
Zurück zum Zitat Wang E, Zhang Q, Shen B, Zhang G, Lu X, Wu Q, Wang Y (2014) High-performance computing on the Intel Xeon Phi(TM): how to fully exploit mic architectures. Springer, Berlin Wang E, Zhang Q, Shen B, Zhang G, Lu X, Wu Q, Wang Y (2014) High-performance computing on the Intel Xeon Phi(TM): how to fully exploit mic architectures. Springer, Berlin
9.
Zurück zum Zitat Lawler EL, Lenstra JK, Kan AR, Shmoys DB (1985) The traveling salesman problem: a guided tour of combinatorial optimization, vol 3. Wiley, New YorkMATH Lawler EL, Lenstra JK, Kan AR, Shmoys DB (1985) The traveling salesman problem: a guided tour of combinatorial optimization, vol 3. Wiley, New YorkMATH
10.
Zurück zum Zitat Dorigo M, Di Caro G (1999) New ideas in optimization. Chap. The ant colony optimization meta-heuristic. McGraw-Hill Ltd., Maidenhead, pp 11–32 Dorigo M, Di Caro G (1999) New ideas in optimization. Chap. The ant colony optimization meta-heuristic. McGraw-Hill Ltd., Maidenhead, pp 11–32
15.
Zurück zum Zitat Dawson L, Stewart IA (2013) Improving ant colony optimization performance on the GPU using CUDA. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2013, Cancun, Mexico, June 20–23 pp. 1901–1908. IEEE (2013). doi:10.1109/CEC.2013.6557791 Dawson L, Stewart IA (2013) Improving ant colony optimization performance on the GPU using CUDA. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2013, Cancun, Mexico, June 20–23 pp. 1901–1908. IEEE (2013). doi:10.​1109/​CEC.​2013.​6557791
18.
Zurück zum Zitat Tirado F, Urrutia A, Barrientos R.J (2015) Using a coprocessor to solve the ant colony optimization algorithm. In: 34th International Conference of the Chilean Computer Science Society (SCCC), pp. 1–6. doi:10.1109/SCCC.2015.7416584 Tirado F, Urrutia A, Barrientos R.J (2015) Using a coprocessor to solve the ant colony optimization algorithm. In: 34th International Conference of the Chilean Computer Science Society (SCCC), pp. 1–6. doi:10.​1109/​SCCC.​2015.​7416584
20.
Metadaten
Titel
Efficient exploitation of the Xeon Phi architecture for the Ant Colony Optimization (ACO) metaheuristic
verfasst von
Felipe Tirado
Ricardo J. Barrientos
Paulo González
Marco Mora
Publikationsdatum
16.08.2017
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 11/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-017-2124-5

Weitere Artikel der Ausgabe 11/2017

The Journal of Supercomputing 11/2017 Zur Ausgabe