High-Performance Divide-and-conquer Algorithms: A Comprehensive Framework with Recursive Parallel Decomposition and Hardware-aware Optimization
TL;DR
A framework for parallel divide-and-conquer algorithms that separates the performance contributions of algorithmic structure from those of the underlying runtime, and introduces hardware-aware threshold selection for Intel’s hybrid P-core/E-core architecture.
Abstract
—We present a framework for parallel divide-and-conquer algorithms that separates the performance contributions of algorithmic structure from those of the underlying runtime. The framework implements true recursive parallel decomposition via rayon::join() at every recursion level—explicitly contrasted with wrapper approaches that delegate to opaque library routines—and introduces hardware-aware threshold selection for Intel’s hybrid P-core/E-core architecture. We formalize algorithm behavior using the work-span model and derive closed-form expressions for the serial fraction that governs scalability. On the i7-13650HX (6 P-cores + 8 E-cores), parallel merge sort achieves 6.35× speedup at 1M elements, while Amdahl’s-law analysis attributes the 39% efficiency ceiling at 14 cores to a 13% inherently sequential merge fraction—a structural bottleneck distinct from runtime overhead. Thread affinity experiments show P-core-only placement outperforms all-core Operating Systems ( OS ) scheduling by 14% for quicksort. Honest benchmarking against Rust’s standard library, Rayon, ndarray, and Intel Math Kernel Library (MKL) confirms that production libraries achieve 3–30× superior throughput through combined pdqsort, Single Instruction Multiple Data (SIMD), and Basic Linear Algebra Subprograms (BLAS) optimizations, while our framework isolates individual optimization layers for research. The complete framework is released as open-source software under the Massachusetts Institute of Technology (MIT) license to support reproducible research.