No Cover Image

E-Thesis 405 views 1173 downloads

Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques / FILIPPOS PANTEKIS

Swansea University Author: FILIPPOS PANTEKIS

  • 2025_Pantekis_F.final.69053.pdf

    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...

Full description

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
first_indexed 2025-03-06T16:48:50Z
last_indexed 2025-03-07T05:49:40Z
id cronfa69053
recordtype RisThesis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2025-03-06T15:06:59.4484763</datestamp><bib-version>v2</bib-version><id>69053</id><entry>2025-03-06</entry><title>Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques</title><swanseaauthors><author><sid>e34468d15f5e269a81ea8c7f3fa99c2d</sid><firstname>FILIPPOS</firstname><surname>PANTEKIS</surname><name>FILIPPOS PANTEKIS</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2025-03-06</date><abstract>Serial (i.e., non-parallel) algorithms have historically been superseded by parallel equivalents which keep up with the evolution of CPUs, speci&#xFB01;cally, 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 signi&#xFB01;cant performance gains when approached in an appropriate manner. At the same time, a plethora of &#x2018;hard&#x2019; constraint satisfaction problems exist which, when approached carefully, bene&#xFB01;t from the computational power of these devices, such as the Boolean Satis&#xFB01;ability (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 speci&#xFB01;c problems, our exploration yields lessons and identi&#xFB01;es general optimisations that can be applied to a broad range of problems, both for memory- and compute-bound kernels.</abstract><type>E-Thesis</type><journal/><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher/><placeOfPublication>Swansea University, Wales, UK</placeOfPublication><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>High Performance Computing, GPGPUs, Optimisation</keywords><publishedDay>7</publishedDay><publishedMonth>2</publishedMonth><publishedYear>2025</publishedYear><publishedDate>2025-02-07</publishedDate><doi>10.23889/SUThesis.69053</doi><url/><notes>A selection of content is redacted or is partially redacted from this thesis to protect sensitive and personal information.</notes><college>COLLEGE NANME</college><CollegeCode>COLLEGE CODE</CollegeCode><institution>Swansea University</institution><supervisor>O&#x2019;Reilly, L.; James, P.; and Moller, F.</supervisor><degreelevel>Doctoral</degreelevel><degreename>Ph.D</degreename><degreesponsorsfunders>EPSRC</degreesponsorsfunders><apcterm/><funders>EPSRC</funders><projectreference/><lastEdited>2025-03-06T15:06:59.4484763</lastEdited><Created>2025-03-06T14:50:03.3219260</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>FILIPPOS</firstname><surname>PANTEKIS</surname><order>1</order></author></authors><documents><document><filename>69053__33749__f2af770661fe42b6839343e61e1082ae.pdf</filename><originalFilename>2025_Pantekis_F.final.69053.pdf</originalFilename><uploaded>2025-03-06T15:02:04.2669522</uploaded><type>Output</type><contentLength>10086807</contentLength><contentType>application/pdf</contentType><version>E-Thesis &#x2013; open access</version><cronfaStatus>true</cronfaStatus><documentNotes>Copyright: The Author, Filippos Pantekis, 2025 Distributed under the terms of a Creative Commons Attribution 4.0 License (CC BY 4.0)</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2025-03-06T15:06:59.4484763 v2 69053 2025-03-06 Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques e34468d15f5e269a81ea8c7f3fa99c2d FILIPPOS PANTEKIS FILIPPOS PANTEKIS true false 2025-03-06 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. E-Thesis Swansea University, Wales, UK High Performance Computing, GPGPUs, Optimisation 7 2 2025 2025-02-07 10.23889/SUThesis.69053 A selection of content is redacted or is partially redacted from this thesis to protect sensitive and personal information. COLLEGE NANME COLLEGE CODE Swansea University O’Reilly, L.; James, P.; and Moller, F. Doctoral Ph.D EPSRC EPSRC 2025-03-06T15:06:59.4484763 2025-03-06T14:50:03.3219260 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science FILIPPOS PANTEKIS 1 69053__33749__f2af770661fe42b6839343e61e1082ae.pdf 2025_Pantekis_F.final.69053.pdf 2025-03-06T15:02:04.2669522 Output 10086807 application/pdf E-Thesis – open access true Copyright: The Author, Filippos Pantekis, 2025 Distributed under the terms of a Creative Commons Attribution 4.0 License (CC BY 4.0) true eng https://creativecommons.org/licenses/by/4.0/
title Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
spellingShingle Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
FILIPPOS PANTEKIS
title_short Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
title_full Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
title_fullStr Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
title_full_unstemmed Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
title_sort Solving Hard Problems at Scale using Massively Parallel Manycore Processors: An Investigation of GPGPU Acceleration Techniques
author_id_str_mv e34468d15f5e269a81ea8c7f3fa99c2d
author_id_fullname_str_mv e34468d15f5e269a81ea8c7f3fa99c2d_***_FILIPPOS PANTEKIS
author FILIPPOS PANTEKIS
author2 FILIPPOS PANTEKIS
format E-Thesis
publishDate 2025
institution Swansea University
doi_str_mv 10.23889/SUThesis.69053
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description 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.
published_date 2025-02-07T05:27:10Z
_version_ 1851097801478373376
score 11.089386

Similar Items