Estratexias de tolerancia a fallos nun algoritmo paralelo de colonia de formigas
Use este enlace para citar
http://hdl.handle.net/2183/31968
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución-NoComercial-SinDerivadas 3.0 España
Coleccións
Metadatos
Mostrar o rexistro completo do ítemTítulo
Estratexias de tolerancia a fallos nun algoritmo paralelo de colonia de formigasAutor(es)
Director(es)
González, PatriciaMartín, María J.
Data
2022Centro/Dpto/Entidade
Universidade da Coruña. Facultade de InformáticaDescrición
Traballo fin de grao (UDC.FIC). Enxeñaría Informática. Curso 2021/2022Resumo
[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 chave
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
Dereitos
Atribución-NoComercial-SinDerivadas 3.0 España