论文标题
共享和分布式内存MIMD的高性能并行排序
High Performance Parallel Sort for Shared and Distributed Memory MIMD
论文作者
论文摘要
我们提出了针对各种并行平台开发的四种高性能混合排序方法：共享内存多处理器，分布式多处理器以及群集利用共享和分布式内存的存在。以稳定性闻名的合并排序用于设计我们的几种算法。我们通过将其与QuickSort结合使用来提高其并行性能。我们提供了两个用于共享内存MIMD（OpenMP）的模型：（a）非收集合并排序和（b）混合QuickSort和合并排序。提出的第三个模型是为分布式内存MIMD（MPI）设计的，并使用混合QuickSort和合并排序设计。我们的第四个模型旨在利用当今群集系统各个节点中的共享内存，并消除在不同节点之间的所有内部数据传输，我们的模型实现了一个单步MSD-Radix，以十个数据包（MPI）分配数据（MPI），而每个节点的平行核心则使用QuickSort将数据分配给他们的数据分配，然后将其分配给他们，然后将其分类为“公开”，然后将其分类为“公开”。所有开发模型的性能都优于基线性能。在对小尺寸数据进行排序时，混合QuickSort和合并分类使用混合MSD-Radix和QuickSort在集群平台中的QuickSort胜过分类，但是使用较大的数据，混合记忆并行合并的加速使用混合存储器的速度使用混合MSD-Radix和QuickSort在群集平台中的QuickSort进行了更大的速度，并且不断改善。分布式内存并行混合QuickSort和合并排序的加速是最好的。
We present four high performance hybrid sorting methods developed for various parallel platforms: shared memory multiprocessors, distributed multiprocessors, and clusters taking advantage of existence of both shared and distributed memory. Merge sort, known for its stability, is used to design several of our algorithms. We improve its parallel performance by combining it with Quicksort. We present two models designed for shared memory MIMD (OpenMP): (a) a non-recursive Merge sort and (b) a hybrid Quicksort and Merge sort. The third model presented is designed for distributed memory MIMD (MPI) using a hybrid Quicksort and Merge sort. Our fourth model is designed to take advantage of the shared memory within individual nodes of todays cluster systems, and to eliminate all internal data transfers between different nodes, Our model implements a one-step MSD-Radix to distribute data in ten packets (MPI) while parallel cores of each node use Quicksort to sort their data partitions sequentially then merge and sort them in parallel employing the OpenMp. The performances of all developed models outperform the baseline performance. Hybrid Quicksort and Merge sort outperformed Hybrid Memory Parallel Merge Sort using Hybrid MSD-Radix and Quicksort in Cluster Platforms when sorting small size data, but with larger data the speedup of Hybrid Memory Parallel Merge Sort Using Hybrid MSD-Radix and Quicksort in Cluster Platforms becomes bigger and it keeps improving. The speedup of Distributed Memory Parallel Hybrid Quicksort and Merge Sort is the best.
