A PARALLEL APPROACH FOR METAHEURISTICS SOLVING THE LABS PROBLEM USING CPU AND GPU

Abstract

The paper contributes to solving the low autocorrelation binary sequence (LABS) problem that remains an open hard-optimization problem with many applications. The current direction of research is focused on developing algorithms dedicated to parallel architectures such as GPGPU or multi-core CPUs. The paper follows this direction and proposes new heuristics developed from the steepest-descent local search algorithm that extends the notion of a neighborhood of a given sequence. The introduced algorithms utilise the parallel nature of multicore CPUs and provide an effective method of solving the LABS problem. The efficiency levels of SDSL and the new algorithm are presented; to ensure an effective comparison, they were both implemented in the same manner. The comparison shows that exploring the larger neighborhood improves the efficiency of the search method.