No Cover Image

Journal article 269 views 56 downloads

Optimized massively parallel solving of N‐Queens on GPGPUs

Filippos Pantekis Orcid Logo, Phillip James Orcid Logo, Oliver Kullmann Orcid Logo, Liam O'Reilly Orcid Logo, Phillip James

Concurrency and Computation: Practice and Experience

Swansea University Authors: Filippos Pantekis Orcid Logo, Oliver Kullmann Orcid Logo, Liam O'Reilly Orcid Logo, Phillip James

  • Fili P VOR.pdf

    PDF | Version of Record

    © 2024 The Authors. This is an open access article under the terms of the Creative Commons Attribution License.

    Download (1.93MB)

Check full text

DOI (Published version): 10.1002/cpe.8004

Abstract

Continuous evolution and improvement of GPGPUs has significantly broadened areas of application. The massively parallel platform they offer, paired with the high efficiency of performing certain operations, opens many questions on the development of suitable techniques and algorithms. In this work,...

Full description

Published in: Concurrency and Computation: Practice and Experience
ISSN: 1532-0626 1532-0634
Published: Wiley 2024
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa65385
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2023-12-28T14:17:46Z
last_indexed 2023-12-28T14:17:46Z
id cronfa65385
recordtype SURis
fullrecord <?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>65385</id><entry>2023-12-28</entry><title>Optimized massively parallel solving of N‐Queens on GPGPUs</title><swanseaauthors><author><sid>7e3976bc926b363ee1346c423ba74d11</sid><ORCID>0000-0001-7817-6450</ORCID><firstname>Filippos</firstname><surname>Pantekis</surname><name>Filippos Pantekis</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>2b410f26f9324d6b06c2b98f67362d05</sid><ORCID>0000-0003-3021-0095</ORCID><firstname>Oliver</firstname><surname>Kullmann</surname><name>Oliver Kullmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>5eca7cf79b7384130a1feef384d90508</sid><ORCID>0000-0002-4894-2158</ORCID><firstname>Liam</firstname><surname>O'Reilly</surname><name>Liam O'Reilly</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>fd3b15ff96c5ea91a100131abac558b6</sid><firstname>Phillip</firstname><surname>James</surname><name>Phillip James</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2023-12-28</date><deptcode>SCS</deptcode><abstract>Continuous evolution and improvement of GPGPUs has significantly broadened areas of application. The massively parallel platform they offer, paired with the high efficiency of performing certain operations, opens many questions on the development of suitable techniques and algorithms. In this work, we present a novel algorithm and create a massively parallel, GPGPU-based solver for enumerating solutions of the N-Queens problem. We discuss two implementations of our algorithm for GPGPUs and provide insights on the optimizations we applied. We also evaluate the performance of our approach and compare our work to existing literature, showing a clear reduction in computational time.</abstract><type>Journal Article</type><journal>Concurrency and Computation: Practice and Experience</journal><volume>0</volume><journalNumber/><paginationStart/><paginationEnd/><publisher>Wiley</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1532-0626</issnPrint><issnElectronic>1532-0634</issnElectronic><keywords>GPGPUs, GPGPU optimization, massively parallel, N-Queens</keywords><publishedDay>3</publishedDay><publishedMonth>1</publishedMonth><publishedYear>2024</publishedYear><publishedDate>2024-01-03</publishedDate><doi>10.1002/cpe.8004</doi><url>http://dx.doi.org/10.1002/cpe.8004</url><notes>Data Availability Statement:The data that support the findings of this study are available from the corresponding author upon reasonable request.</notes><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>SU Library paid the OA fee (TA Institutional Deal)</apcterm><funders>Engineering and Physical Sciences ResearchCouncil, Grant/Award Number: EP/S015523/1;Swansea University</funders><projectreference/><lastEdited>2024-03-27T03:14:58.0210908</lastEdited><Created>2023-12-28T14:13:55.1367180</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><orcid>0000-0001-7817-6450</orcid><order>1</order></author><author><firstname>Phillip</firstname><surname>James</surname><orcid>0000-0002-4307-649x</orcid><order>2</order></author><author><firstname>Oliver</firstname><surname>Kullmann</surname><orcid>0000-0003-3021-0095</orcid><order>3</order></author><author><firstname>Liam</firstname><surname>O'Reilly</surname><orcid>0000-0002-4894-2158</orcid><order>4</order></author><author><firstname>Phillip</firstname><surname>James</surname><order>5</order></author></authors><documents><document><filename>65385__29467__50ce7f7a3ca44fd08a1528a1d8dbe4b8.pdf</filename><originalFilename>Fili P VOR.pdf</originalFilename><uploaded>2024-01-24T13:04:59.6479015</uploaded><type>Output</type><contentLength>2021307</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>© 2024 The Authors. This is an open access article under the terms of the Creative Commons Attribution License.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling v2 65385 2023-12-28 Optimized massively parallel solving of N‐Queens on GPGPUs 7e3976bc926b363ee1346c423ba74d11 0000-0001-7817-6450 Filippos Pantekis Filippos Pantekis true false 2b410f26f9324d6b06c2b98f67362d05 0000-0003-3021-0095 Oliver Kullmann Oliver Kullmann true false 5eca7cf79b7384130a1feef384d90508 0000-0002-4894-2158 Liam O'Reilly Liam O'Reilly true false fd3b15ff96c5ea91a100131abac558b6 Phillip James Phillip James true false 2023-12-28 SCS Continuous evolution and improvement of GPGPUs has significantly broadened areas of application. The massively parallel platform they offer, paired with the high efficiency of performing certain operations, opens many questions on the development of suitable techniques and algorithms. In this work, we present a novel algorithm and create a massively parallel, GPGPU-based solver for enumerating solutions of the N-Queens problem. We discuss two implementations of our algorithm for GPGPUs and provide insights on the optimizations we applied. We also evaluate the performance of our approach and compare our work to existing literature, showing a clear reduction in computational time. Journal Article Concurrency and Computation: Practice and Experience 0 Wiley 1532-0626 1532-0634 GPGPUs, GPGPU optimization, massively parallel, N-Queens 3 1 2024 2024-01-03 10.1002/cpe.8004 http://dx.doi.org/10.1002/cpe.8004 Data Availability Statement:The data that support the findings of this study are available from the corresponding author upon reasonable request. COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University SU Library paid the OA fee (TA Institutional Deal) Engineering and Physical Sciences ResearchCouncil, Grant/Award Number: EP/S015523/1;Swansea University 2024-03-27T03:14:58.0210908 2023-12-28T14:13:55.1367180 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Filippos Pantekis 0000-0001-7817-6450 1 Phillip James 0000-0002-4307-649x 2 Oliver Kullmann 0000-0003-3021-0095 3 Liam O'Reilly 0000-0002-4894-2158 4 Phillip James 5 65385__29467__50ce7f7a3ca44fd08a1528a1d8dbe4b8.pdf Fili P VOR.pdf 2024-01-24T13:04:59.6479015 Output 2021307 application/pdf Version of Record true © 2024 The Authors. This is an open access article under the terms of the Creative Commons Attribution License. true eng https://creativecommons.org/licenses/by/4.0/
title Optimized massively parallel solving of N‐Queens on GPGPUs
spellingShingle Optimized massively parallel solving of N‐Queens on GPGPUs
Filippos Pantekis
Oliver Kullmann
Liam O'Reilly
Phillip James
title_short Optimized massively parallel solving of N‐Queens on GPGPUs
title_full Optimized massively parallel solving of N‐Queens on GPGPUs
title_fullStr Optimized massively parallel solving of N‐Queens on GPGPUs
title_full_unstemmed Optimized massively parallel solving of N‐Queens on GPGPUs
title_sort Optimized massively parallel solving of N‐Queens on GPGPUs
author_id_str_mv 7e3976bc926b363ee1346c423ba74d11
2b410f26f9324d6b06c2b98f67362d05
5eca7cf79b7384130a1feef384d90508
fd3b15ff96c5ea91a100131abac558b6
author_id_fullname_str_mv 7e3976bc926b363ee1346c423ba74d11_***_Filippos Pantekis
2b410f26f9324d6b06c2b98f67362d05_***_Oliver Kullmann
5eca7cf79b7384130a1feef384d90508_***_Liam O'Reilly
fd3b15ff96c5ea91a100131abac558b6_***_Phillip James
author Filippos Pantekis
Oliver Kullmann
Liam O'Reilly
Phillip James
author2 Filippos Pantekis
Phillip James
Oliver Kullmann
Liam O'Reilly
Phillip James
format Journal article
container_title Concurrency and Computation: Practice and Experience
container_volume 0
publishDate 2024
institution Swansea University
issn 1532-0626
1532-0634
doi_str_mv 10.1002/cpe.8004
publisher Wiley
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
url http://dx.doi.org/10.1002/cpe.8004
document_store_str 1
active_str 0
description Continuous evolution and improvement of GPGPUs has significantly broadened areas of application. The massively parallel platform they offer, paired with the high efficiency of performing certain operations, opens many questions on the development of suitable techniques and algorithms. In this work, we present a novel algorithm and create a massively parallel, GPGPU-based solver for enumerating solutions of the N-Queens problem. We discuss two implementations of our algorithm for GPGPUs and provide insights on the optimizations we applied. We also evaluate the performance of our approach and compare our work to existing literature, showing a clear reduction in computational time.
published_date 2024-01-03T03:14:57Z
_version_ 1794647573570519040
score 11.035634

Similar Items