Análise de desempenho de algoritmos de enxame paralelizados em GPU

Abstract

Swarm algorithms are a combined set of heuristics that are used in the search of optimal solutions in applications where there is a large amount of possibilities for answers. They are versatile and used in a diverse array of problems such as, vehicle routing problems (BELL; MCMULLEN, 2004), predicting trends in the financial market (SHEN et al.,2011), optimal power flow problems (MOHAMED et al., 2017), and many others. In the search or optimal solutions, since its not necessary for the algorithm to comprehend or know completely the problem that is being analyzed, keeping high quality answers even in black box scenarios. By nature these algorithms are relatively simple to paralelize, since the components that compose the swarm are semi-independent, making it possible to execute using a large number of threads. Some applications that use swarm algorithms for problem solving explore paralelism in CPU. But most aplications dont use GPGPU computing to paralelyze the algortihms. GPU offer a high number of threads, and fast computation of basic functions that are used in the evaluation of fitness of an individual or swarm. In this way, this work evaluate and compare both CPU and GPU implementations of swarm algorithms. The obtained results shows that the performance in GPU is better than CPU when a larger number of swarm elements are used.