学位论文简介

本论文题为《面向多核架构的高效并行原地洗牌与归并算法研究》，旨在应对现代多核处理器环境中大规模数据处理对高效原地操作的迫切需求，提出了多种创新的并行算法及其高性能实现。主要研究内容与贡献如下：

(1) 论文提出了 PI-sqrt，一组适用于多核系统的并行原地序列旋转算法。文中设计了一种融合型旋转算法（blend rotation），结合三类经典旋转算法的优点，在保持原地特性的前提下实现性能提升。实验结果显示，该融合旋转及其反转实现平均性能分别优于 Intel 并行 STL 中的旋转函数 7.85 倍和 5.52 倍，显著提升了处理大数据量场景下的运行效率和空间利用率。

(2) 论文提出了用于并行 k 路归并的创新性原地算法 PS-merge。该算法基于共享内存多核 CPU 架构，结合序列分区与原地完美洗牌操作，实现高效的多路归并过程。与现有主流方法（如 bitonic merge、并行二叉归并树和 lazy-merge）相比，PS-merge 在执行效率上具有显著优势，同时弥补了 Intel 并行 STL 缺乏原地归并功能的缺陷。

(3) 论文推出了 ParaShuf，首个基于循环领袖（cycle leader）技术的并行、严格原地（仅 O(1) 辅助空间）通用 k 路完美洗牌算法的完整 C++/OpenMP 实现与系统性性能评估。研究揭示了 OpenMP 静态调度在循环长度不均引发负载失衡时的扩展性瓶颈，并通过动态调度与经验调整的 chunk 大小（约为 2048 次迭代）显著改善了可扩展性。在大规模问题实例上，ParaShuf 在 16 核上可达 10 倍以上加速，而静态调度仅达 2 倍，为内存受限的科学计算与数据处理提供了实用高效的算法原语。

主要学术成果

[1] Hashem M, Li K, Salah A. PI-sqrt: novel parallel implementations of in-place sequence rotation on multicore systems[J]. Cluster Computing, 2023, 26(1): 539-557.(SCI 3区, 第一作者)