PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallelizing the Factorial Space: Multi-Core OpenMP Scaling and Scalable SIMD Acceleration of the Steinhaus-Johnson-Trotter Algorithm via Dual-Lane AVX2 Execution

Serge Melnikov

arXiv:2609.07862v3cs.DS

TL;DR

The paper addresses iterative generation of all permutations in canonical order, a task motivated by applications in cryptography and graph theory. It combines SIMD permutation generation with OpenMP parallelization, reporting near-linear scaling across physical cores and completion of the 15! space in 16 seconds.

  • Problem

    The paper asks how to generate all permutations in canonical order iteratively, avoiding recursive-call overhead in a task used in cryptography and graph theory algorithms.

    Source: §1 · p. 2

  • Method

    The framework combines dual-lane SIMD permutation generation with OpenMP parallelization and a lock-free, thread-local initialization topology.

    Source: §3 · p. 2, §4 · p. 3, §5 · p. 4

  • Results

    The 15! factorial space is exhausted in 16 seconds, and throughput scales near-linearly with the number of active physical processor cores.

    Source: §8 · p. 4, §5 · p. 4

  • Takeaways & Limitations

    The reported framework generates the 15! space on a Coffee Lake mobile CPU and demonstrates cross-platform deployment compliance across enterprise high-performance computing environments.

    Source: §8 · pp. 4–5

    The AVX2/YMM vectorized implementation is bounded to permutation lengths n ≤16 and produces a modified, non-canonical sequence.

    Source: §3.1 · p. 3, §4 · p. 3

Abstract

from arXiv · show

This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter algorithm, targeted at modern x86-64 architectures using the AVX2 instruction set. By exploiting a novel combinatorial space partitioning combined with single-cycle vector byte shuffling ($\texttt{\_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$ throughput increase over an optimized scalar baseline of Knuth's Algorithm P (accelerated by $3\times$ via isolated sweeping branches) and outperform the recent Ring-Cascade algorithm by Yusheng Hu, completely avoiding store-forwarding stalls during hot loops. To scale this engine across multi-core processors, we extend the framework into a highly concurrent environment via OpenMP using a localized mathematical state decoder and macro-period loop scheduling. The parallel performance is shown to scale strictly and linearly with the number of active physical processor cores ($\text{Speedup}(M) \approx M$) due to a lock-free thread-local accumulation pipeline that eliminates false sharing. On a 6-core processor, the multi-threaded engine delivers a $5.25\times$ throughput gain for $n=14$ ($3.25$ billion CPU cycles) and processes the massive $n=15$ space in just $16.0$ seconds, yielding a $5.25\times$ speedup over the sequential vector baseline, while Hyper-Threading virtual cores yield zero additional throughput due to physical SIMD port saturation.

1 Introduction

The section introduces an iterative way to generate permutations in canonical order, addressing the overhead of recursive calls in this task. It builds larger sequences by inserting each new element into repeated copies of the preceding sequence.

1 Introduction

  • Starting from (0), the construction duplicates the sequence and inserts each new element through a staircase cascade.For n+1 elements, each order-n permutation is repeated n+1 times before the new element is inserted.Source: §1 · p. 1
  • The resulting sequential output order is defined as the canonical permutation order.Source: §1 · p. 1
  • Permutations of order n are indexed by canonical rank from 0 through n! −1.Source: §1 · p. 2
  • Elements are ranked by seniority, with more junior elements moving more often; active swaps displace more senior elements until a boundary or more junior element is reached.At a boundary, an element reverses direction and yields the execution token to a more senior element.Source: §1 · p. 2
  • The non-recursive Steinhaus-Johnson-Trotter algorithm generates all permutations in canonical order without recursive calls.The paper motivates this approach by the importance of permutation generation in cryptography and graph theory algorithms.Source: §1 · p. 2

2 Optimized Algorithm P

This section describes an optimized iterative variant of SJT, Algorithm P, and contrasts its reported performance with Heap’s algorithm and the Ring-Cascade alternative.

2 Optimized Algorithm P

  • Branch-isolating Algorithm P’s bidirectional staircase path for the most junior element yields an approximate 3× speedup.The paper’s scalar implementation is derived from Knuth’s description and modified for canonical sequence and zero-based array indexing.Source: §2 · p. 2
  • On contemporary deeply pipelined superscalar processors, iterative Heap’s algorithm executes approximately three times as slowly as optimized Algorithm P.The paper attributes this degradation to branch mispredictions and irregular data access patterns that cause instruction-pipeline stalls.Source: §2 · p. 2
  • Hu’s Ring-Cascade Position-Pro variant is presented as a high-throughput scalar alternative that does not impose hardware-vectorization constraints.Source: §2 · p. 2

3 Microarchitectural Optimization Techniques

The section proposes two SJT optimizations: SIMD staircase interleaving and exploiting a half-space reflection invariant. The latter reconstructs the second half of the permutation space by reversal after generating only the first half.

3 Microarchitectural Optimization Techniques

  • The section proposes two architectural and combinatorial optimization mechanisms within the SJT framework.Source: §3 · p. 2

3.1 Vectorized Staircase Interleaving

  • Staircase interleaving derives order-(n+1) permutations by sweeping the new element across slots, but its SIMD implementation is bounded to n ≤16.In standard scalar execution, the technique increases L1 data-cache write traffic.Source: §3.1 · pp. 2–3

3.2 Exploitation of the Half-Space Reflection Invariant

  • Computing only the initial half-space and reconstructing the rest by right-to-left reversal cuts generation work exactly in half.The paper states that no two permutations within either half-space are mirror-image reversals of one another.Source: §3.2 · p. 3

4 Sequential Vectorized Implementation via AVX2/YMM

The AVX2/YMM implementation generates two concurrent permutation streams, while its lane scheduling changes the output from canonical order. Its reported normalized application-level throughput is 3× that of optimized Algorithm P.

4 Sequential Vectorized Implementation via AVX2/YMM

  • The 256-bit YMM register’s two 128-bit lanes limit permutation length to n ≤16.Source: §4 · p. 3
  • A single YMM register generates two concurrent permutations using the byte-shuffling intrinsic mm256_shuffle_epi8.The vectorized routines use a modified, non-canonical sequence due to parallel lane scheduling.Source: §4 · p. 3
  • The standalone benchmark isolates the generation loop by omitting external-caller overhead, while a runtime checksum guards against compiler dead-code elimination.Source: §4 · p. 3
  • 6× raw-cycle speedup over optimized Algorithm P normalizes to an exact 3× application-level throughput increase.The kernel computes only the primary half-space of the factorial domain.Source: §4 · p. 3
  • A production variant passes each vectorized permutation matrix to a user-defined callback.The demonstration callback prints each tensor in direct and reversed order.Source: §4 · p. 3

5 Multi-Threaded Parallel Implementation via OpenMP

The OpenMP engine extends the sequential lane-splitting design with per-thread state initialization and macro-period scheduling. Throughput scales near-linearly with active physical cores, while SMT virtual contexts add no performance.

5 Multi-Threaded Parallel Implementation via OpenMP

  • The parallel engine mirrors the sequential lane-splitting logic and initializes each long-lived worker’s state decoder once at thread startup.The decoder is named StructuralInitState.Source: §5 · pp. 3–4
  • Macro-periods slice the invariant combinatorial space and align the fast-sweeping element n −1 with the rightmost boundary during initial worker sweeps.Source: §5 · p. 4
  • Throughput scales near-linearly with active physical cores, while SMT virtual contexts add 0% performance.The reported result attributes the SMT limit to saturation of the physical SIMD shuffle and shift ports.Source: §5 · p. 4
  • The concurrent command format is ./ymm_final_en_mt <n> <threads>, with n ranging from 6 to 16 and the thread pool specified as a count or t-prefixed value.Source: §5 · p. 4

6 Experimental Setup

The evaluation used an Intel Core i7-8850H mini-PC with AVX2 support and a sustained 4.2 GHz frequency. Compilation and timing procedures used performance-focused settings and serializing instructions around the cycle counter.

6 Experimental Setup

  • The test node used an Intel Core i7-8850H at a sustained 4.2 GHz, with AVX2 support, DDR4 RAM at 2.67 GHz, and 64-bit Windows 10.Source: §6 · p. 4
  • The code was compiled with GCC 15.2.0 using -O3 -march=native -s -Wall; source also maintains compatibility with MSVC and Clang.Source: §6 · p. 4
  • LFENCE instructions bracketed RDTSC timing after a core-warmup phase to isolate microarchitectural state and stabilize CPU frequency scaling.Source: §6 · p. 4

7 Remarks on Further Optimizations

The paper identifies compile-time permutation order, direct YMM-register consumption, and wider SIMD as possible optimization directions.

7 Remarks on Further Optimizations

  • Compile-time permutation order n is anticipated to provide an incremental performance dividend.Source: §7 · p. 4
  • An external caller could consume generated permutation tensors directly in YMM registers, eliminating store-to-load forwarding overhead.Source: §7 · p. 4
  • The framework is described as extensible to AVX-512/ZMM and data-parallel multithreaded topologies.Source: §7 · p. 4

8 Conclusion

The framework combines dual-lane AVX2 execution with lock-free OpenMP thread-local initialization for SJT permutation generation. It reports completing 15! permutations in 16 seconds on a six-core Coffee Lake mobile CPU.

8 Conclusion

  • The framework accelerates SJT generation on modern multicore x86-64 nodes through dual-lane SIMD and decentralized, lock-free OpenMP initialization.Source: §8 · p. 4
  • The passage mentions a Coffee Lake mobile CPU and reports cross-platform deployment compliance across enterprise high-performance computing environments.Source: §8 · p. 5
  • The conclusion reports cross-platform deployment compliance across enterprise high-performance computing environments.Source: §8 · p. 5

Code Availability

Complete, cross-platform C source for the sequential and multi-threaded parallel algorithms is openly available on GitHub, with separate directories for benchmarking isolation.

  • The sequential directory contains accelerated scalar Knuth Algorithm P code, single-threaded vector benchmarks, and a vector generator with a user-defined processing interface.Source: Code Availability · p. 5
  • The parallel directory contains a multi-threaded vector benchmark engine and a production generator with a thread-safe user-callback pipeline.Source: Code Availability · p. 5
Loading 2609.07862v3…