Massive parallelism for combinatorial problems by hardware acceleration with an application to the label switching problem
| dc.contributor.author | Steere, Edward | |
| dc.date.accessioned | 2017-05-22T08:42:59Z | |
| dc.date.available | 2017-05-22T08:42:59Z | |
| dc.date.issued | 2016 | |
| dc.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. | en_ZA |
| dc.description.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. | en_ZA |
| dc.description.librarian | MT2017 | en_ZA |
| dc.format.extent | Online resource (xvi, 191 leaves) | |
| dc.identifier.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> | |
| dc.identifier.uri | http://hdl.handle.net/10539/22673 | |
| dc.language.iso | en | en_ZA |
| dc.subject.lcsh | Parallel processing (Electronic computers) | |
| dc.subject.lcsh | Mathematical optimization--Data processing | |
| dc.subject.lcsh | Combinatorial optimization | |
| dc.subject.lcsh | Problem solving--Data processing | |
| dc.title | Massive parallelism for combinatorial problems by hardware acceleration with an application to the label switching problem | en_ZA |
| dc.type | Thesis | en_ZA |
Files
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: