New Ideas in Parallel Metaheuristics on GPU: Systolic Genetic Search
This chapter presents an in-depth study of a novel parallel optimization algorithm specially designed to run on Graphic Processing Units (GPUs). The underlying operation relates to systolic computing and is inspired by the systolic contraction of the hear
- PDF / 722,485 Bytes
- 23 Pages / 439.36 x 666.15 pts Page_size
- 51 Downloads / 216 Views
Abstract This chapter presents an in-depth study of a novel parallel optimization algorithm specially designed to run on Graphic Processing Units (GPUs). The underlying operation relates to systolic computing and is inspired by the systolic contraction of the heart that makes possible blood circulation. The algorithm, called Systolic Genetic Search (SGS), is based on the synchronous circulation of solutions through a grid of processing units and tries to profit from the parallel architecture of GPUs to achieve high time performance. SGS has shown not only to numerically outperform a random search and two genetic algorithms for solving the Knapsack Problem over a set of increasingly sized instances, but also its parallel implementation can obtain a runtime reduction that, depending on the GPU technology used, can reach more than 100 times. A study of the performance of the parallel implementation of SGS on four different GPUs has been conducted to show the impact of the Nvidia’s GPU compute capabilities on the runtimes of the algorithm.
1 Introduction The design of parallel metaheuristics [1], thanks to the increasing power offered by modern hardware architectures, is a natural research line in order to reduce the execution time of the algorithms, especially when solving problems of a high dimension, highly restricted, and/or time bounded. Parallel metaheuristics are often based
M. Pedemonte () Instituto de Computaci´on, Facultad de Ingenier´ıa, Universidad de la Rep´ublica, Montevideo, Uruguay e-mail: [email protected] F. Luna E. Alba Departamento de Lenguajes y Ciencias de la Computaci´on, Universidad de M´alaga, M´alaga, Spain e-mail: [email protected]; [email protected] S. Tsutsui and P. Collet (eds.), Massively Parallel Evolutionary Computation on GPGPUs, Natural Computing Series, DOI 10.1007/978-3-642-37959-8 10, © Springer-Verlag Berlin Heidelberg 2013
203
204
M. Pedemonte et al.
on new different search patterns that are later implemented on physically parallel hardware, then improving the quality of results obtained by traditional sequential algorithms and also reducing their execution time. As a consequence, research on parallel metaheuristics has grown substantially in recent years, motivated by the excellent results obtained in their application to the resolution of problems in search, optimization, and machine learning. Among parallel metaheuristics, Parallel Evolutionary Algorithms (PEAs) have been extensively adopted and are nowadays quite popular, mainly because Evolutionary Algorithms (EAs) are naturally prone to parallelism. For this reason, the study of parallelization strategies for EAs has laid the foundations for working in parallel metaheuristics. The most usual criterion for categorizing PEAs distinguishes three categories [3, 17]: the master–slave model (functional distribution of the algorithm), the distributed or island model (the population is partitioned into a small number of subpopulations that evolve in semi-isolation) [3], and the cellular model (the population is structured in o
Data Loading...
