- author = "Martin Pedemonte",
- title = "Systolic genetic search, a parallel metaheuristic for GPUs",
- school = "Facultad de Ingenieria, Universidad de la Republica",
- year = "2017",
- address = "Uruguay",
- month = sep,
- keywords = "genetic algorithms, genetic programming, Evolutionary Algorithms, Systolic Computing, Parallel Metaheuristics, GPU, Search-Based Software Engineering, SBSE, CA, CUDA, Algoritmos evolutivos, Computacion sistolica, Metaheuristicas paralelas",
-
URL = "
https://hdl.handle.net/20.500.12008/20365",
-
URL = "
https://www.colibri.udelar.edu.uy/jspui/bitstream/20.500.12008/20365/1/td-mpedemonte.pdf",
- size = "144 pages",
-
abstract = "The use of Graphics Processing Units (GPUs) for
general purpose computing has experienced a tremendous
growth in recent years, based on its wide availability,
low economic cost and inherent parallel architecture,
as well as on the emergence of general purpose
programming languages that have eased the development
of applications onto this parallel computing platforms.
In this context, the design of new parallel algorithms
that profit from the GPUs platform is certainly a
promising and interesting research line.
Metaheuristics are stochastic algorithms which are able to provide optimization problems with very accurate (many times, optimal) solutions in a reasonable amount of time. However, as many optimization problems involve tasks demanding large computational resources, and/or problem instances in todays research are becoming very large, even metaheuristics may be highly computationally expensive. In this situation, parallelism comes out as a successful strategy for speeding up the search of those kind of algorithms. Parallel meta-heuristics do not only allow to reduce the runtime of the algorithms, but also often improve the quality of the results obtained by traditional sequential algorithms.
Although the use of GPUs has also represented an inspiring domain for the research in parallel metaheuristics, most previous works were aimed at porting existing family of algorithms onto this new kind of hardware. As a consequence, many published material is targeted to show the time savings of running different parallel types of metaheuristics on GPUs. In spite of this considerable work on the parallelisation of metaheuristics in GPUs, there are few novel ideas for designing new algorithms and/or parallel models that explicitly exploit the high degree of parallelism available in modern GPU architectures. This thesis addresses the design of an innovative proposal of a parallel optimization family of algorithms, called Systolic Genetic Search (SGS), that merges ideas from the fields of metaheuristics and systolic computing. SGS, as well as systolic computing, are inspired by the same biological phenomenon: the systolic contraction of the heart that makes possible blood circulation. In SGS, solutions circulate synchronously through a grid of processing cells. When two solutions meet in a cell, adapted evolutionary operators are applied to generate new solutions that continue moving through the grid. The implementation of this new proposal takes special advantage of the specific features of the massively parallel GPU platforms.
An extensive experimental analysis, which considers several classical benchmark problems and two real-world problems from the Software Engineering field, shows that the newly proposed algorithm is highly effective, finding optimal or near optimal solutions in short execution times. Moreover, the numerical results obtained by SGS are competitive with the state-of-the-art results for the two real-world problems also targeted in this PhD thesis. On the other hand, the parallel GPU implementation of SGS has achieved a high performance, obtaining a large runtime reduction from the sequential implementation and showing that it scales properly on instances of increasing size.
A theoretical analysis of the search capabilities of SGS has been also performed for understanding how some aspects of the behaviour of the algorithm affect the numerical results of SGS. This analysis gives an important insight in the behaviour of SGS that can be used to improve the design of future variants of the algorithm.",
-
notes = "In English. is this GP?
Director de Tesis: Prof. Enrique Alba Torres. Co-Director de Tesis: Prof. Francisco Luna Valero. Director Academico: Prof. Hector Cancela.",
