Simd vectorization triples performance in generating permutations efficiently
Parallelizing the Factorial Space: 3x SIMD Acceleration of the Steinhaus-Johnson-Trotter Algorithm via Dual-Lane AVX2 Execution
Data Structures and Algorithms
Summary
Generating all possible orders (permutations) of items is a common computing challenge that can be very slow for larger lists. The authors developed a new way to speed up a well-known algorithm by running two streams of computations in parallel using advanced CPU instructions called AVX2. This approach shuffles and manages data inside the processor's registers to process permutations much faster without slowing down memory access. Their method runs about three times faster than previous best-known techniques for sequences up to size 13 on typical modern processors.
What this means in practice
- •For high-performance computing teams: Increase permutation-generation speed in simulations needing many orderings by running concurrent streams on AVX2-enabled processors.
- •For cryptography engineers: Generate permutations more rapidly using SIMD acceleration for cryptographic algorithms that rely on permutation enumeration.
Authors
Serge Melnikov
Abstract
This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter permutation generation algorithm, targeted at modern x86-64 architectures using the AVX2 instruction set. By exploiting a novel combinatorial space partitioning with pre-calculated index offsets combined with single-cycle vector byte shuffling (_mm256_shuffle_epi8), our dual-lane vectorized implementation processes two independent, concurrent permutation streams within a single 256-bit YMM register under a uniform execution mask. Empirical evaluations demonstrate a 3$x$ performance throughput increase over both Donald Knuth's Algorithm P (TAOCP Vol 4A), which we previously accelerated by 3$x$ in scalar code, and the recent Ring-Cascade algorithm by Yusheng Hu. The proposed software architecture maintains cross-compiler compliance, completely avoids store-forwarding memory stalls during hot loops, and is validated up to order $n=11$ with a benchmark performance of ~1.27 billion CPU cycles for $n=13$ on native hardware.