Summary
Generating all possible orderings of a list, called permutations, can take a long time as the list gets bigger. The authors show how to speed up a classic method for making permutations by running two streams of the process at the same time inside one processor register. They use special instructions available on modern Intel and AMD processors to shuffle data efficiently and avoid common slowdowns. Their approach runs about three times faster than previous well-known methods for the same task, and it works reliably up to lists of length 11 or 13. This helps computers handle permutation problems more quickly in practice.
permutationsSIMDSteinhaus-Johnson-Trotter algorithmAVX2x86-64 architecturevectorizationpermutation generationinstruction setstore-forwarding stallalgorithm acceleration
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.