Massive parallelism for combinatorial problems by hardware acceleration with an application to the label switching problem
Date
2016
Authors
Steere, Edward
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This dissertation proposes an approach to solving hard combinatorial problems in massively
parallel architectures using parallel metaheuristics.
Combinatorial problems are common in many scientific fields. Scientific progress is constrained
by the fact that, even using state of the art algorithms, solving hard combinatorial
problems can take days or weeks. This is the case with the Label Switching Problem (LSP)
in the field of Bioinformatics.
In this field, prior work to solve the LSP has resulted in the program CLUMPP (CLUster
Matching and Permutation Program). CLUMPP focuses solely on the use of a sequential,
classical heuristic, and has had success in smaller low complexity problems.
By contrast this dissertation proposes the Parallel Solvers model for the acceleration of
hard combinatorial problems. This model draws on the commonalities evident in algorithms
and strategies in metaheuristics.
After investigating the effectiveness of the mechanisms apparent in the Parallel Solvers
model with regards to the LSP, the author developed DePermute, an algorithm which can be
used to solve the LSP significantly faster. Results were generated from time based testing of
simulated data, as well as data freely available on the Internet as part of various projects.
An investigation into the effectiveness of DePermute was carried out on a CPU (Central
Processing Unit) based computer. The time based testing was carried out on a CPU based
computer and on a Graphics Processing Unit (GPU) attached to a CPU host computer. The
dissertation also proposes the design of an Field Programmable Gate Arrays (FGPA) based
implementation of DePermute.
Using Parallel Solvers, in the DePermute algorithm, the time taken for population group
sizes, K, ranging from K = 5 to 20 was improved by up to two orders of magnitude using the
GPU implementation and aggressive settings for CLUMPP. The CPU implementation, while
slower than the GPU implementation still outperforms CLUMPP, using aggressive settings,
marginally and usually with better quality. In addition it outperforms CLUMPP by at least
an order of magnitude when CLUMPP is set to use higher quality settings.
Combinatorial problems can be very difficult. Parallel Solvers has been effective in the
field of Bioinformatics in solving the LSP. This dissertation proposes that it might assist in
the reasoning and design of algorithms in other fields.
Description
A dissertation submitted to the Faculty of Engineering and the Built Environment, University
of the Witwatersrand, in fulfilment of the requirements for the degree of Master of Science in
Engineering.
Keywords
Citation
Steere, Edward (2016) Massive parallelism for combinatorial problems by hardware acceleration with an application to the label switching problem, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/22673>