E-Thesis 82 views 56 downloads
Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques / FILIPPOS PANTEKIS
Swansea University Author: FILIPPOS PANTEKIS
-
PDF | E-Thesis – open access
Copyright: The Author, Filippos Pantekis, 2025 Distributed under the terms of a Creative Commons Attribution 4.0 License (CC BY 4.0)
Download (9.62MB)
DOI (Published version): 10.23889/SUThesis.69053
Abstract
Serial (i.e., non-parallel) algorithms have historically been superseded by parallel equivalents which keep up with the evolution of CPUs, specifically, from single-core to the modern-day multi-core. This is a non-trivial transition, typically involving complex analysis and adjustment of code to expl...
| Published: |
Swansea University, Wales, UK
2025
|
|---|---|
| Institution: | Swansea University |
| Degree level: | Doctoral |
| Degree name: | Ph.D |
| Supervisor: | O’Reilly, L.; James, P.; and Moller, F. |
| URI: | https://cronfa.swan.ac.uk/Record/cronfa69053 |
| Abstract: |
Serial (i.e., non-parallel) algorithms have historically been superseded by parallel equivalents which keep up with the evolution of CPUs, specifically, from single-core to the modern-day multi-core. This is a non-trivial transition, typically involving complex analysis and adjustment of code to exploit the architecture. Furthermore, the need for such development has increased due to the emergence and widespread availability of massively parallel manycore (co)processors over recent years that have offered access to increased computational performance relative to conventional processors (CPUs). However, this has come with the cost of developing bespoke algorithms which exploit the specialities and requirements of such hardware.Graphics Processing Units (GPUs) are a prime example of commercially available massively parallel co-processors that have been shown to offer significant performance gains when approached in an appropriate manner. At the same time, a plethora of ‘hard’ constraint satisfaction problems exist which, when approached carefully, benefit from the computational power of these devices, such as the Boolean Satisfiability (SAT) and the N-Queens problems.In this work, we explore the applicability of current GPU technology to the SAT andN-Queens problems. We present our design of a hybrid solver for SAT, which utilises a fast implementation of a scalable, loosely coupled GPU-based checker. Furthermore, we present a fully GPU-based, and fully scalable N-Queens solver that is state-of- the-art, built around our DoubleSweep-Light algorithm, which surpasses results of other solvers. Beyond algorithms and approaches for these specific problems, our exploration yields lessons and identifies general optimisations that can be applied to a broad range of problems, both for memory- and compute-bound kernels. |
|---|---|
| Item Description: |
A selection of content is redacted or is partially redacted from this thesis to protect sensitive and personal information. |
| Keywords: |
High Performance Computing, GPGPUs, Optimisation |
| College: |
Faculty of Science and Engineering |
| Funders: |
EPSRC |