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

Finding optimal/short-span Convolutional 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 t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2014-11, Vol.25 (11), p.2992-3001
Main Authors: Kowarzyk, Gilbert, Belanger, Normand, Haccoun, David, Savaria, Yvon
Format: Article
Language:English
Subjects:
Arrays
Computation
Convolutional code
data-reuse
Encoding
Indexes
Load balancing (computing)
Mathematical analysis
Mathematical models
Microprocessors
Optimization
parallel tree-traversal
Pseudorandom
Search algorithms
Search problems
Searching
self-doubly orthogonal code
Simulation
systematic encoder
Systematics
threshold decoder
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Finding optimal/short-span Convolutional 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 16 300 (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 pseudorandom 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 60 000 (S-CDO, J = 17) and 190 000 (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 1014 times larger than what was previously possible.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2013.311