- -

Re-engineering the ant colony optimization for CMP architectures

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Re-engineering the ant colony optimization for CMP architectures

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Cecilia-Canales;GARCÍA ...
Tamaño: 803.0Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: Cecilia-García202 ...
Tamaño: 1.098Mb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Cecilia-Canales, José María es_ES
dc.contributor.author GARCÍA CARRASCO, JOSE MANUEL es_ES
dc.date.accessioned 2021-02-05T04:31:24Z
dc.date.available 2021-02-05T04:31:24Z
dc.date.issued 2020-06 es_ES
dc.identifier.uri http://hdl.handle.net/10251/160762
dc.description.abstract [EN] The ant colony optimization (ACO) is inspired by the behavior of real ants, and as a bioinspired method, its underlying computation is massively parallel by definition. This paper shows re-engineering strategies to migrate the ACO algorithm applied to the Traveling Salesman Problem to modern Intel-based multi- and many-core architectures in a step-by-step methodology. The paper provides detailed guidelines on how to optimize the algorithm for the intra-node (thread and vector) parallelization, showing the performance scalability along with the number of cores on different Intel architectures, reporting up to 5.5x speedup factor between the Intel Xeon Phi Knights Landing and Intel Xeon v2. Moreover, parallel efficiency is provided for all targeted architectures, finding that core load imbalance, memory bandwidth limitations, and NUMA effects on data placement are some of the key factors limiting performance. Finally, a distributed implementation is also presented, reaching up to 2.96x speedup factor when running the code on 3 nodes over the single-node counterpart version. In the latter case, the parallel efficiency is affected by the synchronization frequency, which also affects the quality of the solution found by the distributed implementation. es_ES
dc.description.sponsorship This work was partially supported by the Fundación Séneca, Agencia de Ciencia y Tecnología de la Región de Murcia under Project 20813/PI/18, and by Spanish Ministry of Science, Innovation and Universities as well as European Commission FEDER funds under Grants TIN2015-66972-C5-3-R, RTI2018-098156-B-C53, TIN2016-78799-P (AEI/FEDER, UE), and RTC-2017-6389-5. We acknowledge the excellent work done by Victor Montesinos while he was doing a research internship supported by the University of Murcia. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof The Journal of Supercomputing (Online) es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Parallel and distributed ACO es_ES
dc.subject CMP code redesign es_ES
dc.subject Intel Xeon Phi es_ES
dc.subject Performance evaluation es_ES
dc.subject Ant colony optimization es_ES
dc.subject TSP es_ES
dc.subject.classification ARQUITECTURA Y TECNOLOGIA DE COMPUTADORES es_ES
dc.title Re-engineering the ant colony optimization for CMP architectures es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s11227-019-02869-8 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/f SéNeCa//20813%2FPI%2F18/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//TIN2015-66972-C5-3-R/ES/TECNICAS PARA LA MEJORA DE LAS PRESTACIONES, FIABILIDAD Y CONSUMO DE ENERGIA DE LOS SERVIDORES. OPTIMIZACION DE APLICACIONES CIENTIFICAS, MEDICAS Y DE VISION ARTIFICIAL/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/RTI2018-098156-B-C53/ES/TECNICAS INNOVADORAS EN COMPUTACION ESPECIALIZADA Y DE ALTAS PRESTACIONES/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//TIN2016-78799-P/ES/DESARROLLO HOLISTICO DE APLICACIONES EMERGENTES EN SISTEMAS HETEROGENEOS/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/AEI//RTC-2017-6389-5/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Informática de Sistemas y Computadores - Departament d'Informàtica de Sistemes i Computadors es_ES
dc.description.bibliographicCitation Cecilia-Canales, JM.; García Carrasco, JM. (2020). Re-engineering the ant colony optimization for CMP architectures. The Journal of Supercomputing (Online). 76(6):4581-4602. https://doi.org/10.1007/s11227-019-02869-8 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s11227-019-02869-8 es_ES
dc.description.upvformatpinicio 4581 es_ES
dc.description.upvformatpfin 4602 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 76 es_ES
dc.description.issue 6 es_ES
dc.identifier.eissn 1573-0484 es_ES
dc.relation.pasarela S\404483 es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder Fundación Séneca-Agencia de Ciencia y Tecnología de la Región de Murcia es_ES
dc.contributor.funder Agencia Estatal de Investigación es_ES
dc.description.references Yang XS (2010) Nature-inspired metaheuristic algorithms. Luniver Press, Lebanon es_ES
dc.description.references Akila M, Anusha P, Sindhu M, Selvan Krishnasamy T (2017) Examination of PSO, GA-PSO and ACO algorithms for the design optimization of printed antennas. In: IEEE Applied Electromagnetics Conference (AEMC) es_ES
dc.description.references Dorigo M, Stützle T (2004) Ant colony optimization. A bradford book. The MIT Press, Cambridge es_ES
dc.description.references Cecilia JM, García JM, Nisbet A, Amos M, Ujaldón M (2013) Enhancing data parallelism for ant colony optimization on GPUs. J Parallel Distrib Comput 73(1):42–51 es_ES
dc.description.references Dawson L, Stewart I (2013) Improving ant colony optimization performance on the GPU using CUDA. In: IEEE Conference on Evolutionary Computation, pp 1901–1908 es_ES
dc.description.references Llanes A, Cecilia JM, Sánchez A, García JM, Amos M, Ujaldón M (2016) Dynamic load balancing on heterogeneous clusters for parallel ant colony optimization. Cluster Comput 19(1):1–11 es_ES
dc.description.references Cecilia JM, Llanes A, Abellán JL, Gómez-Luna J, Chang L, Hwu WW (2018) High-throughput ant colony optimization on graphics processing units. J Parallel Distrib Comput 113:261–274 es_ES
dc.description.references Lloyd H, Amos M (2016) A Highly Parallelized and Vectorized Implementation of Max–Min Ant System on Intel Xeon Phi. In: IEEE computational intelligence es_ES
dc.description.references Tirado F, Barrientos RJ, González P, Mora M (2017) Efficient exploitation of the Xeon Phi architecture for the ant colony optimization (ACO) metaheuristic. J Supercomput 73(11):5053–5070 es_ES
dc.description.references Montesinos V, García JM (2018) Vectorization strategies for ant colony optimization on intel architectures. Parallel Computing is Everywhere. IOS Press, Amsterdam, pp 400–409 es_ES
dc.description.references Lawler E, Lenstra J, Kan A, Shmoys D (1987) The Traveling salesman problem. Wiley, New York es_ES
dc.description.references Montesinos V (June 2018) Performance analysis of ant colony optimization on intel architectures. Master’s Thesis, University of Murcia (Spain) es_ES
dc.description.references Lloyd H, Amos M (2017) Analysis of independent roulette selection in parallel ant colony optimization. In: Genetic and Evolutionary Computation Conference, ACM, pp 19–26 es_ES
dc.description.references Dorigo M (1992) Optimization, learning and natural algorithms. Ph.D. Thesis, Politecnico di Milano, Italy es_ES
dc.description.references Duran A, Klemm M (2012) The intel many integrated core architecture. In: Internal Conference on High Performance Computing and Simulation (HPCS), pp 365–366 es_ES
dc.description.references The OpenMP API specification for parallel programming. URL: https://www.openmp.org . [Last accessed 14 June 2018] es_ES
dc.description.references The Message Passing Interface (MPI) standard. URL: http://www.mcs.anl.gov/research/projects/mpi/ . [Last accessed 15 June 2018] es_ES
dc.description.references Vladimirov A, Asai R (2016) Clustering modes in Knights landing processors: developer’s guide. Colfax international. URL: https://colfaxresearch.com/knl-numa/ . [Last accessed: 16 June 2018] es_ES
dc.description.references Intel Developer Zone. URL: https://software.intel.com/en-us/modern-code . [Last accessed 02 Oct 2018] es_ES
dc.description.references Pearce M (2018) What is code modernization? Intel developer zone. URL: http://software.intel.com/en-us/articles/what-is-code-modernization . [Last accessed 15 Feb 2018] es_ES
dc.description.references Stützle T ACOTSP v1.03. Last accessed 15 Feb 2018. URL: http://iridia.ulb.ac.be/~mdorigo/ACO/downloads/ACOTSP-1.03.tgz es_ES
dc.description.references Reinelt G (1991) TSPLIB—a traveling salesman problem library. ORSA J Comput 3:376–384 es_ES
dc.description.references Crainic TG, Toulouse M (2003) Parallel strategies for meta-heuristics. State-of-the-art handbook in metaheuristics. Kluwer Academic Publishers, Dordrecht, pp 475–513 es_ES
dc.description.references Delévacq A, Delisle P, Gravel M, Krajecki M (2013) Parallel ant colony optimization on graphics processing units. J Parallel Distrib Comput 73(1):52–61 es_ES
dc.description.references Skinderowicz R (2016) The GPU-based parallel ant colony system. J Parallel Distrib Comput 98:48–60 es_ES
dc.description.references Zhou Y, He F, Hou N, Qiu Y (2018) Parallel ant colony optimization on multi-core SIMD CPUs. Future Gener Comput Syst 79:473–487 es_ES
dc.description.references Peake J, Amos M, Yiapanis P, Lloyd H (2018) Vectorized candidate set selection for parallel ant colony optimization. In: Genetic and Evolutionary Computation Conference, ACM, pp 1300–1306 es_ES
dc.description.references Stützle T (1998) Parallelization strategies for ant colony optimization. In: Eiben AE, Bäck T, Schoenauer M, Schwefel HP (eds) Parallel problem solving from nature—PPSN V. PPSN. Lecture Notes in Computer Science, vol 1498. Springer, Berlin, Heidelberg es_ES
dc.description.references Abdelkafi O, Lepagnot J, Idoumghar L (2014) Multi-level parallelization for hybrid ACO. In: Siarry P, Idoumghar L, Lepagnot J (eds) Swarm Intelligence Based Optimization. ICSIBO 2014. Lecture Notes in Computer Science, vol 8472. Springer, Cham es_ES
dc.description.references Michel R, Middendorf M (1998) An island model based ant system with lookahead for the shortest super sequence problem. In: Eiben AE, Bäck T, Schoenauer M, Schwefel HP (eds) Parallel problem solving from nature— PPSN V. PPSN. Lecture Notes in Computer Science, vol 1498. Springer, Berlin, Heidelberg es_ES
dc.description.references Chen L, Sun H, Wang S (2008) Parallel implementation of ant colony optimization on MPP. In: International Conference on Machine Learning and Cybernetics es_ES
dc.description.references Lin Y, Cai H, Xiao J, Zhang J (2007) Pseudo parallel ant colony optimization for continuous functions. In: International Conference on Natural Computation es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem