Title :
Parallel Local Search for the Costas Array Problem
Author :
Diaz, Daniel ; Richoux, Florian ; Caniou, Yves ; Codognet, Philippe ; Abreu, Salvador
Author_Institution :
Univ. de Paris 1, Paris, France
Abstract :
The Costas Array Problem is a highly combinatorial problem linked to radar applications. We present in this paper its detailed modeling and solving by Adaptive Search, a constraint-based local search method. Experiments have been done on both sequential and parallel hardware up to several hundreds of cores. Performance evaluation of the sequential version shows results outperforming previous implementations, while the parallel version shows nearly linear speedups up to 8,192 cores.
Keywords :
combinatorial mathematics; constraint satisfaction problems; mathematics computing; parallel processing; performance evaluation; radar applications; search problems; Costas array problem; adaptive search; combinatorial problem; constraint-based local search method; parallel hardware; parallel local search; performance evaluation; radar applications; sequential hardware; Adaptation models; Arrays; Benchmark testing; Program processors; Search problems; Supercomputers; Costas array; constraint solving; implementation; local search; metaheuristics; parallelism;
Conference_Titel :
Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International
Conference_Location :
Shanghai
Print_ISBN :
978-1-4673-0974-5
DOI :
10.1109/IPDPSW.2012.222
