| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Parallel self-avoiding walks for a low-autocorrelation binary sequences problem
Authors:ID Bošković, Borko (Author)
ID Herzog, Jana (Author)
ID Brest, Janez (Author)
Files:.pdf 1-s2.0-S187775032400053X-main.pdf (1,82 MB)
MD5: 9A94AE46CBF071816EAFFFEC0D3D3F3D
 
Language:English
Work type:Unknown
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:A low-autocorrelation binary sequences problem with a high figure of merit factor represents a formidable computational challenge. An efficient parallel computing algorithm is required to reach the new best-known solutions for this problem. Therefore, we developed the sokol solver for the skew-symmetric search space. The developed solver takes the advantage of parallel computing on graphics processing units. The solver organized the search process as a sequence of parallel and contiguous self-avoiding walks and achieved a speedup factor of 387 compared with lssOrel, its predecessor. The sokol solver belongs to stochastic solvers and cannot guarantee the optimality of solutions. To mitigate this problem, we established the predictive model of stopping conditions according to the small instances for which the optimal skew-symmetric solutions are known. With its help and 99% probability, the sokol solver found all the known and seven new best-known skew-symmetric sequences for odd instances from to . For larger instances, the solver cannot reach 99% probability within our limitations, but it still found several new best-known binary sequences. We also analyzed the trend of the best merit factor values, and it shows that as sequence size increases, the value of the merit factor also increases, and this trend is flatter for larger instances.
Keywords:low-autocorrelation binary sequences, self-avoiding walk, graphic processor units, high performance computing
Submitted for review:01.03.2024
Article acceptance date:04.03.2024
Publication date:07.03.2024
Publisher:ScienceDirect
Year of publishing:2024
Number of pages:9 str.
Numbering:Vol. 77, [article no.] 102260
PID:20.500.12556/DKUM-90089 New window
UDC:004.8
ISSN on article:1877-7511
COBISS.SI-ID:188486403 New window
DOI:10.1016/j.jocs.2024.102260 New window
Copyright:© 2024 The Author(s). Published by Elsevier B.V.
Publication date in DKUM:22.08.2024
Views:45
Downloads:6
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
BOŠKOVIĆ, Borko, HERZOG, Jana and BREST, Janez, 2024, Parallel self-avoiding walks for a low-autocorrelation binary sequences problem. Journal of computational science [online]. 2024. Vol. 77, no. 102260. [Accessed 14 March 2025]. DOI 10.1016/j.jocs.2024.102260. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=90089
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Journal of computational science
Publisher:Elsevier
ISSN:1877-7511
COBISS.SI-ID:175298563 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P2-0041
Name:Računalniški sistemi, metodologije in inteligentne storitve

Secondary language

Language:Slovenian
Keywords:grafično procesiranje, algoritmi, stohastični procesi


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica