Estratexias de tolerancia a fallos nun algoritmo paralelo de colonia de formigas

Abstract

[Resumo]: A resolución de problemas combinatorios de complexidade NP aínda é un problema aberto debido ao alto tempo de computación requirido para obter solucións de boa calidade. Dentro deste conxunto, o problema do viaxante - Travel Salesman Problem (TSP) - é un dos máis estudados pola comunidade científica debido á grande cantidade de aplicacións no mundo real que podemos atopar. Co obxectivo de obter solucións óptimas de xeito eficiente, unha das estratexias máis prometedoras é o uso de algoritmos de colonia de formigas - Ant Colony Optimization (ACO) - e variacións deste baseados no uso de metaheurísticas. Non tardaron en aparecer solucións paralelas para este algoritmo para intentar acelerar a computación da solución aínda máis. Non obstante, o aumento do número de recursos utilizados nas aplicacións e sistemas paralelos, conleva ao aumento na taxa de fallos aos que están expostos estas aplicacións tan demandantes, polo que utilizar técnicas de tolerancia a fallos vólvese fundamental. O obxectivo deste proxecto é estudar diferentes estratexias de tolerancia a fallos para unha versión paralela asíncrona do ACO, utilizando as extensións de MPI que proporciona o framework User Level Failure Mitigation (ULFM). Esta proposta foi avaliada utilizando dous problemas TSP distintos extraídos da libraría TSPLib, obtendo tolerancia dende 1 a N − 1 fallos (sendo N o número de procesos MPI) cun overhead moi pequeno na maior parte dos casos.

[Abstract]: Solving combinatorial problems of NP complexity is still an open problem due to the high computational time required to obtain good quality solutions. Within this set, Travel Salesman Problem (TSP) is one of the most studied by the scientific community due to the large number of applications in the real world that we can find. With the aim of obtaining optimal solutions efficiently, one of the most promising strategies is the use of ant colony algorithms - Ant Colony Optimization (ACO) - and variations of it based on the use of metaheuristics. Parallel solutions to this algorithm soon appeared in an attempt to speed up the computation of the solution even more. However, the increase in the number of resources used in parallel applications and systems leads to an increase in the rate of failures to which these demanding applications are exposed, so using fault tolerance techniques becomes essential. The objective of this project is to study different fault tolerance strategies for an asynchronous parallel version of the ACO, using the MPI extensions provided by the User Level Failure Mitigation (ULFM) framework. This proposal was evaluated using two TSP problems taken from the TSPLib library, obtaining tolerance from 1 to N − 1 failures (being N the number of MPI processes) with a very small overhead in most cases.