arXiv preprint ·
Parallelizing the Factorial Space: 3x SIMD Acceleration of the Steinhaus-Johnson-Trotter Algorithm via Dual-Lane AVX2 Execution
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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$\times$ performance throughput increase over Donald Knuth's Algorithm P (TAOCP Vol 4A) (which we previously accelerated by 3$\times$ in scalar code) and also outperform 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 \(\sim \)1.27 billion CPU cycles for $n=13$ on native hardware.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Smoothed Picard Hamiltonian Monte Carlo
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Frequency Moments Beyond Equality: Streaming Cosine Density Moments
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.