Optimizing the Parallel Tree-Search for Finding Shortest-Span Error-Correcting CDO Codes

Finding optimal short-span Convolution Self-Doubly Orthogonal (CDO) codes and Simplified-CDO (S-CDO) codes for a specified order J is computationally very challenging. This paper describes several optimizations that were applied to an implicitly-exhaustive search algorithm in order to reduce the time required for finding these types of codes. The resulting high-performance parallel implementation provides an impressive speedup that is greater than 16300 (CDO, J=7) and 6300 (S-CDO, J=8) over the reference implicitly-exhaustive search algorithm, and greater than 2000 (J=17) over the fastest published CDO validation function used in high-performance pseudo-random search algorithms. These speedups are achieved through enhancements in the deterministic search-space reduction, and a vastly improved validation function that makes use of a novel data structure for enabling data-reuse and incremental computations. The resulting validation function speedup is greater than 60000 (S-CDO, J=17) and 190000 (CDO, J=17) when compared to its reference implementation. The combination of optimizations and load-balancing techniques allowed us to leverage hundreds of processor cores in order to complete an exhaustive search over a search space that is some 10<sup>14<sup> times larger than what was previously possible.