|
本文记录了使用MPI与OpenMP两种并行计算方法实现快速排序算法，题目是专业实验课上老师给的，主要分享一下自己的做法，希望大家不吝赐教（使用的语言是C语言，有例子+图阐述原理，代码注释很全）。
目录
快速排序算法并行实现1. 快速排序算法2. 并行快速排序原理2.1 MPI快排并行原理2.1.1 进程数为2的整数次方2.1.2 进程数为2的非整数次方
2.2 OpenMP快排并行原理
3. 完整代码与结果（含注释）3.1 MPI3.2 OpenMP
快速排序算法并行实现
1. 快速排序算法
本篇文章主要针对快排算法的并行实现，所以大家如果有忘记快排算法的，可以参考一下这篇文章（快速排序算法原理及实现（单轴快速排序、三向切分快速排序、双轴快速排序）），这篇文章里面有动图，感觉还是挺不错的，有需要的朋友可以看看，其次再贴一个C语言实现串行快速排序算法的程序（快速排序算法（QSort，快排）及C语言实现），并行算法的实现核心还是围绕这个方法进行的。
核心功能代码 实现方式有挺多种的，我使用的是把数据data的第一个元素作为基准进行快排的，代码如下：
int Partition(int* data, int start, int end) //划分数据
{
int temp = data[start]; //以第一个元素为基准
while (start
if (start
#pragma omp section //该区域对前部分数据进行排序
quickSort(data, start, pos - 1);
#pragma omp section //该区域对后部分数据进行排序
quickSort(data, pos + 1, end);
}
}
}
3. 完整代码与结果（含注释）
3.1 MPI
代码
#include"mpi.h"
#include
#include
#include
int Partition(int* data, int start, int end) //划分数据
{
int temp = data[start]; //以第一个元素为基准
while (start
if (start
int i = 1;
while (n-- > 0) i *= 2;
return i;
}
//求以2为底n的对数，向下取整
int log2(int n)
{
int i = 1, j = 2;
while (j
int i, j, r = end, length = -1; //r表示划分后数据前部分的末元素下标，length表示后部分数据的长度
int* t;
MPI_Status status;
if (m == 0) { //无进程可以调用
if (nowID == id) QuickSort(data, start, end);
return;
}
if (nowID == id) { //当前进程是负责分发的
while (id + exp2(m - 1) > N && m > 0) m--; //寻找未分配数据的可用进程
if (id + exp2(m - 1) //当前进程是负责接收的
MPI_Recv(&length, 1, MPI_INT, id, id, MPI_COMM_WORLD, &status);
if (length > 0) { //id+2^(m-1)进程从id进程接收后部分数据
t = (int*)malloc(length * sizeof(int));
if (t == 0) printf("Malloc memory error!");
MPI_Recv(t, length, MPI_INT, id, id, MPI_COMM_WORLD, &status);
}
}
j = r - 1 - start;
MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
if (j > 0) //负责分发的进程的数据不为空
paraQuickSort(data, start, r - 1, m - 1, id, nowID, N); //递归调用快排函数，对前部分数据进行排序
j = length;
MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
if (j > 0) //负责接收的进程的数据不为空
paraQuickSort(t, 0, length - 1, m - 1, id + exp2(m - 1), nowID, N); //递归调用快排函数，对前部分数据进行排序
if ((nowID == id + exp2(m - 1)) && (length > 0)) //id+2^(m-1)进程发送结果给id进程
MPI_Send(t, length, MPI_INT, id, id + exp2(m - 1), MPI_COMM_WORLD);
if ((nowID == id) && id + exp2(m - 1) 0)) //id进程接收id+2^(m-1)进程发送的结果
MPI_Recv(data + r + 1, length, MPI_INT, id + exp2(m - 1), id + exp2(m - 1), MPI_COMM_WORLD, &status);
}
int main(int argc, char* argv[])
{
int* data;
int rank, size;
int i, j, m, r, n = atoi(argv[1]); //随机数组的长度
double start_time, end_time;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank); //当前进程的进程号
MPI_Comm_size(MPI_COMM_WORLD, &size); //总进程数
if (rank == 0) { //根进程生成随机数组
data = (int*)malloc(n * sizeof(int));
srand(time(NULL) + rand()); //随机数种子
for (i = 0; i
int temp = data[start]; //以第一个元素为基准
while (start
if (start
#pragma omp section //该区域对前部分数据进行排序
quickSort(data, start, pos - 1);
#pragma omp section //该区域对后部分数据进行排序
quickSort(data, pos + 1, end);
}
}
}
int main(int argc, char* argv[])
{
int n = atoi(argv[2]), i; //线程数
int size = atoi(argv[1]); //数据大小
int* num = (int*)malloc(sizeof(int) * size);
double starttime = omp_get_wtime();
srand(time(NULL) + rand()); //生成随机数组
for (i = 0; i |