On the Enumeration of Three-Dimensional Costas Arrays Using GPUs

Due to its applications in optical communications and digital watermarking for different media, multidimensional Costas arrays merit study. Regardless there are algebraic constructions that generates this type of permutations, their existence for every given size has not been proved. Exhaustive search is required to enumerate all the permutations for a size: a task with factorial complexity. In this research, different techniques has been implemented to optimize the enumeration of such arrays. Those include the implementation of a backtracking algorithm and the use of its algebraic symmetries to reduce the search space. Both approaches has an initial serial implementation and a parallelized version using a CUDA-enabled GPU computer architecture. GPUs can carry up to a teraflop of computing power using a small fraction of power per calculation. That means we can achieve high performance for a lower cost, consuming less power and compute Costas of bigger sizes that are practically impossible to do in CPU time. Comparison of results between our implementations show that significant optimization is achieved by exploiting their algebraic symmetries,  the addition of bits hash tables that serve as memory of previous computations, and the parallelization of the problem. Further studies include the assessment of Costas arrays of higher dimensions using the best approach.