Parallelization Strategy for the PP Algorithm

[Yusheng-Hu]

Parallelization Strategy for the PP Algorithm

1. Background and Core Concept

The Position-Pure (PP) Algorithm is driven by an auxiliary state array C, which represents a factorial-based mixed-radix number system. Since every unique state in array C corresponds deterministically to a specific permutation in array D, the algorithm possesses an inherent mathematical structure perfectly suited for multi-core parallelization.

---

2. Core Mechanism: $m!$ Slicing via the C Array

The most efficient way to parallelize the algorithm is to partition the permutation space into $m!$ blocks based on the higher-order indices of the C array.

• Logic: By fixing the most significant counters in the C array (e.g., $C_0, C_1, C_2$, etc.), the entire permutation set is divided into independent, non-overlapping sub-ranges.
• Simplicity: This approach is highly intuitive; each thread is assigned a specific range within the factorial number space and iterates through it independently.
• Task Independence: Each thread maintains its own local copy of the C and D arrays. There is zero inter-thread communication and no locking required during generation, eliminating concurrency overhead.

---

3. Performance and Scalability

• Linear Speedup: Performance gains scale directly with the number of CPU cores. Theoretically, on an 8-core processor, the execution speed can be increased by 8x through balanced slicing.
• Cache Friendliness: Because the higher-order elements in the array change very slowly within a single thread's task cycle, the corresponding data in array D remains resident in the CPU's L1/L2 cache, significantly improving memory access efficiency.
• Versatility: The algorithm supports both single-mapping (Unranking) for immediate positioning at a start point and high-speed iterative modes for bulk generation.

---

4. Implementation Roadmap

1. Workload Partitioning: Divide the total $n!$ permutations into equal chunks based on the available core count (e.g., 24 threads).
2. State Initialization: Use the high-order values of the C array to initialize each thread's starting permutation D using the PP mapping logic.
3. Local Iteration: Each thread runs its own PP iterative loop, using its assigned C index boundary as the termination condition rather than a global end-state.

---

Note: We recommend the $m!$ slicing method for its clarity, ease of implementation, and robust scalability. Code is not yet included in the repository. Please leave a comment if you would like a reference implementation template.