Parallel self-avoiding walks for a low-autocorrelation binary sequences problem

Borko Bošković (Author), Jana Herzog (Author), Janez Brest (Author)

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

grafično procesiranje;algoritmi;stohastični procesi;low-autocorrelation binary sequences;self-avoiding walk;graphic processor units;high performance computing;

Data

Language:	English
Year of publishing:	2024
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	ScienceDirect
UDC:	004.8
COBISS:	188486403
ISSN:	1877-7511
Views:	6
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	grafično procesiranje;algoritmi;stohastični procesi;
Pages:	9 str.
Volume:	ǂVol. ǂ77
Issue:	[article no.] 102260
Chronology:	Apr. 2024
DOI:	10.1016/j.jocs.2024.102260
ID:	24791854