Estratexias de tolerancia a fallos nun algoritmo paralelo de colonia de formigas
![Thumbnail](/dspace/bitstream/handle/2183/31968/BlancoGodon_Miguel_TFG_2022.pdf.jpg?sequence=5&isAllowed=y)
Use este enlace para citar
http://hdl.handle.net/2183/31968
Excepto si se señala otra cosa, la licencia del ítem se describe como Atribución-NoComercial-SinDerivadas 3.0 España
Colecciones
Metadatos
Mostrar el registro completo del ítemTítulo
Estratexias de tolerancia a fallos nun algoritmo paralelo de colonia de formigasAutor(es)
Directores
González, PatriciaMartín, María J.
Fecha
2022Centro/Dpto/Entidad
Universidade da Coruña. Facultade de InformáticaDescripción
Traballo fin de grao (UDC.FIC). Enxeñaría Informática. Curso 2021/2022Resumen
[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.
Palabras clave
ACO
MPI
ULFM
Tolerancia a fallos
Computación paralela
Fault tolerance
Parallel computing
MPI
ULFM
Tolerancia a fallos
Computación paralela
Fault tolerance
Parallel computing
Derechos
Atribución-NoComercial-SinDerivadas 3.0 España