GPU-based acceleration of the Linear Complexity Test for random number generator testing.

Abstract The Linear Complexity Test is a statistical test for verifying the randomness of a binary sequence produced by a random number generator (RNG). It is the most time-consuming test in the widely used randomness testing suite that was published by the National Institute of Standards and Technology (NIST). The slow performance of the original Linear Complexity Test implementation is one of the major hurdles in the RNG testing process. In this work, we present a parallelized implementation of the Linear Complexity Test for GPU computation. We incorporate two levels of parallelism and various design optimization approaches to accelerate the test execution on modern GPU architectures. To further enhance the performance, we also create a hybrid computation approach that uses both CPU and GPU simultaneously. We achieve a speedup of more than 4000 times over the original Linear Complexity Test implementation from NIST (27 times over the previous best implementation of the test). Highlights • Parallel implementation of the Linear Complexity Test for GPU computation. • Achieved a speedup of more than several orders of magnitude. • Decision mechanism for finding the ideal workload amount per thread. • A hybrid computing approach that simultaneously utilizes CPU and GPU. [ABSTRACT FROM AUTHOR]