65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 MPI & 性能分析进行并行快速排序。

PrasadPerera
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.33/5 (9投票s)

Sep 13, 2009

CPOL

8分钟阅读

viewsIcon

76893

这是一项通过 MPI（消息传递接口）并行化快速排序算法的个人研究成果，旨在通过共享常规抽样生成的子集来排序数据。

引言

快速排序是由 C. A. R. Hoare 开发的一种在数据排序场景中广泛使用的算法。其平均时间复杂度为 O (n log n)，最坏情况下的时间复杂度为 O (n2)。但快速排序通常被认为比一些平均时间复杂度为 O (n log n) 的排序算法更快。快速排序的基本思想是选择一个值，并将输入数据集划分为两个子集，一个子集包含小于选定值的数据，另一个子集包含大于选定值的数据。这个选定的值称为枢轴值。在每一步中，这些划分的数据集会通过从每个集合中选择枢轴来进一步细分。快速排序的实现是递归的，当不再可能进行子划分时，停止条件即满足。

背景

在本研究中，主要思想是实现一个并行化的快速排序，以在多核环境中运行并进行性能评估。通过使用 MPI API 功能在多个进程之间共享排序数据集来实现这种并行化。

基本实现步骤

  • 对数据进行初始划分，直到所有可用进程都获得一个子集以进行顺序排序
  • 每个进程并行地对接收到的数据集进行排序
  • 收集所有数据，对应精确的划分偏移量，而无需进行任何合并

初始数据划分和子数组分配

初始数据划分方案包含以下步骤

  • 如果存在任何可共享其数据集的进程，则每个进程都会使用枢轴对数据进行初始划分。
  • 将一部分数据发送给共享进程，并开始对剩余数据集进行划分（如果还有更多进程可用）。
  • 否则，对数据集执行顺序快速排序。
  • 将本地排序好的数据集发送回其原始发送者。

此方案需要在每个划分和数据共享步骤中正确分配进程。我使用的方案是根据进程的秩（rank）和一种计算模式来分配数据，该模式决定了哪些进程将共享数据集。

进程分配方案

进程使用以下方程进行分配
秩为 r 的进程 p 将与其进程秩共享其分区。

通过这个计算出的秩，每个进程会尝试找到其数据分区共享进程。如果存在该进程，则将分区进行子划分并与拥有该特定秩的进程共享。如果不存在这样的进程，则对分区进行顺序排序，并将其发送回最初共享排序集数的父进程。这些调用中的每一个都实现了递归运行。

选择要共享的分区

在大多数情况下，常规抽样产生的分区大小可能不同。因此，当进行任何划分以共享数据集时，最大的子分区保留在主进程中，而较小的集合发送给接收进程。发送较小分区的原因有两个：

  • 通过传输较小的数据集来减少通信开销。
  • 在进程分配方案中，负责划分的进程将是下一个有权在接收进程之前再次共享数据集的进程。因此，如果池中还有其他进程，发送进程比接收进程更有机会共享其数据集。

示例：对于使用三个进程排序的数据集，第 0 个进程会将较小的数据集发送到第 1 个分区。然后，剩余的进程编号 2 将被分配给进程编号 0 来共享其数据集。因此，在第 1 个进程获得数据共享进程之前，创建分区的进程编号 0 有机会让另一个进程共享其数据集。

通过对一种略微改变的并行快速排序实现进行性能比较，其中主进程始终保留数组的前半部分。该修改版本与共享较小分区的快速排序实现进行了比较。在较小的分区共享实现中，排序时间趋于小于前半部分数组共享实现。

实现

并行快速排序是使用 OpenMPI 实现的，这是可用的开源 MPI 实现之一。程序是用 C 语言编写的。

函数 sort_recursive

此函数由每个进程递归调用，以在存在共享进程时执行初始划分，或对数据集进行顺序排序。最后，它将排序好的数据集发送给其共享进程。每一步的枢轴选择为索引为 [size / 2] 的元素，即数组的中间值。此外，还使用一个特定的索引值来保持在计算下一个要递归共享数据集的进程的秩时增量的数量。

int sort_recursive(int* arr, int size, int pr_rank, int
max_rank, int rank_index){
	MPI_Status dtIn;
	int share_pr = pr_rank + pow(2, rank_index); /* Calculate the
						rank of sharing process*/
	rank_index ++; 				/*Increment the count
						index*/
	if(share_pr > max_rank){    		/*If no process to share
		sort_rec_seq(arr, size);		sequentially*/
		return 0;
	}
	int pivot = arr[size/2]; 			/* Select the pivot */
	int partition_pt = sequential_quicksort(arr, pivot, size,
				(size/2) -1);    	/* partition array */
	int offset = partition_pt + 1;

/* Send partition based on size, sort the remaining partitions,
receive sorted partition */
	
	if (offset > size - offset){
		MPI_Send((arr + offset), size - offset, MPI::INT, share_pr
					, offset, MPI_COMM_WORLD);
		sort_recursive (arr, offset, pr_rank, max_rank,
						rank_index);
		MPI_Recv((arr + offset), size - offset, MPI::INT, share_pr,
		MPI_ANY_TAG, MPI_COMM_WORLD, &dtIn);
	}
	else{
		MPI_Send(arr, offset, MPI::INT, ch_pr , tag,
		MPI_COMM_WORLD);
		sort_recursive ((arr + offset), size - offset, pr_rank,
		max_rank, rank_index);
		MPI_Recv(arr, offset, MPI::INT, ch_pr, MPI_ANY_TAG,
		MPI_COMM_WORLD, &dtIn);
	}

除了主进程，所有其他进程都将执行以下代码行

int* subarray = NULL;
MPI_Status msgSt, dtIn;
int sub_arr_size = 0;
int index_count = 0;
int pr_source = 0;
while(pow(2, index_count) <= rank) 	/* calculate the*/
    index_count ++;             	/*index_count as*/
                               	/*2 n-1 <= rank < 2n*/
                               	/* n = index_count */
MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD,
&msgSt);
MPI_Get_count(&msgSt, MPI::INT, &sub_arr_size);
pr_source = msgSt.MPI_SOURCE;      	/* Get the
                                    	sending process rank
                                    	*/
subarray = (int*)malloc(sub_arr_size * sizeof(int));
MPI_Recv(subarray, sub_arr_size, MPI::INT, MPI_ANY_SOURCE,
MPI_ANY_TAG, MPI_COMM_WORLD, &dtIn);
int pivot = subarray[(sub_arr_size / 2)]; /* Find
                                          the pivot */
sort_rec(subarray, sub_arr_size, rank, size_pool -1,
rec_count);                 	/* sort recursively */
                           		/* send sorted sub array */
MPI_Send(subarray, sub_arr_size, MPI::INT, pr_source,
tag, MPI_COMM_WORLD);
free(subarray);

实验结果

对快速排序实现进行了基准测试，与具有合并的并行快速排序实现和顺序快速排序实现进行了比较，让它们对不同大小的相同数据集进行排序。这些测试结果是通过对每种测试案例运行一批排序任务并对所有获得的結果取平均值来收集的。

  • 所有这些测试均在 7 核 Intel Xeon E5420 处理器和 16 GB 内存的 Linux 集群上进行。

进行了以下场景的基准测试

  • 使用五个进程对 5 – 100 M 的数据集进行排序，用于每种实现。
  • 对 10 M 的数据集进行排序，进程范围为 1 - 10；对 1 M 的数据集进行排序，进程范围为 5 – 70。

带合并的并行快速排序

此实现属于 Puneet C Kataria 的项目 "[Parallel Quciksort Implementation Using MPI and Pthreads]"，该项目旨在以最小的合并成本实现并行化快速排序，并使用树状合并。他目前是一名研究生，有关他实现的更多详细信息可以在他的个人主页 这里 找到。

Graph1 显示带合并的并行快速排序具有最低的运行时间，且时间增量趋于非常平滑和线性。无合并的并行快速排序在数据集大小增加时显示出波动，但仍然是线性的。

Graph2 显示两种实现的结果非常接近，但无合并的并行快速排序实现比其他并行实现显示出更多的非规律性。

这些结果表明，具有初始划分和合并的总体并行实现优于不带合并的并行快速排序实现。此外，固定划分在较少进程的情况下，随数据大小增加，时间增量显示得更平滑。但是，无合并的并行快速排序则表现相反，在更多进程的情况下会更平滑。

时间复杂度分析

基于顺序快速排序的时间复杂度一般假设为 n log n，让我们以上述实现的最佳情况排序分析为例。假设每次划分都可能产生两个相等的区域

对于两个进程运行，T (n) = (n/2) log (n/2)

对于三个进程运行，T (n) = max ((n/2) log (n/2) + (n/4) log (n/4)) = (n/2) log (n /2)

根据表 1，在 4 个进程运行后，T (n) = (n/4) log (n/4)

因此，对于 p 个进程，T (n) = (n / k) log (n / k)，其中 k 满足 = 2k-1 < p < = 2k

但是，由于该实现采用了共享最小分区策略和可变分区大小，因此这种时间分析无法证明不带合并的并行快速排序的平均运行时间。此外，通信开销也没有被计入。实验结果也证明，在平均运行时，这种时间复杂度并没有得到保持。

结论

根据性能分析，新的实现随着进程数量的增加似乎变得更有效率。它在某些进程数量下还可以优于带合并的实现。但从性能角度来看，带合并的实现对较少数量的进程显示出最低的运行时间。不带合并的实现对较少数量的进程表现效率较低。结论如下：

  • 初始划分对于使用 MPI 的并行快速排序至关重要。在实现了不带初始固定划分的并行快速排序，并将其与反向实现进行了比较后，可以明显看出初始固定划分带来的时间效率提升非常重要。如果没有，通过常规抽样执行更好的初始划分对于获得更高的性能至关重要。
  • 使用 MPI，两种并行实现对更多进程的性能表现较低，因为 MPI 通信开销。必须通过限制运行进程的数量（根据数据集大小）来弥补这种开销。
  • 此外，通过常规抽样进行的划分可能由于每次步骤中的可变划分而导致运行时间非常不规律。这也可能导致最坏情况下的高度不平衡数据分布，从而导致效率低下的时间性能。
  • 通过考虑可用进程的可变划分，某些进程可能无法被有效利用。事实上，对于小型数据集，最坏情况下使用大量进程时，某些进程可能因没有数据可供顺序排序而退出，这表明进程使用效率低下。

因此，本分析强调了初始划分结合常规抽样（可以将输入数据集划分为相等子集）对于提高并行快速排序性能的重要性。此外，更多的并行合并和常规抽样可以提高性能。

关注点

本文是尝试使用 MPI 并行化快速排序以并行排序数据的实验结果。完整的报告与本文一同提供。本文不提供任何代码或程序，因为它的目的是展示一项研究，而不是提供一个可用的应用程序代码。

历史

  • 2009年9月13日：初始发布
© . All rights reserved.