SIMD-Accelerated Optimization of Runs Test Performance on Binary Sequences

The runs test, as one of the basic binary sequence randomness analysis methods, has been widely adopted in various international standards and industry. However, existing runs test schemes suffer from critical performance limitations, such as large lookup tables to calculate Hamming weight, causing cache inefficiency; data loading redundancy in computing Hamming weight. We propose a SIMD-accelerated optimization scheme to enhance the runs test performance. This scheme includes: (1) replacing software lookup tables with SIMD bit-counting instructions to optimize cache efficiency; (2) designing a parallel computing algorithm that consolidates the dual traversals for computing Hamming weight into a single traversal, to eliminate redundant data loading. The proposed scheme exhibits architectural independence, as it fully achieves performance improvements on x86 and ARM architectures. Notably, the proposed scheme achieves 161,134.39[Formula: see text]Mbps detection speed, that is 16.98 times compared to the current Fast NIST STS implementation.