快排基本原理：
快速排序可以说是最为常见的排序算法，冒泡排序时间复杂度达到了O（N2），而桶排序容易造成浪费空间。快排（Quicksort）就成为了不错的选择。
1、原理：快排需要找一个数作为基准数，用来参照。（可取第一个数为参照）
基准数在中间某位置，两端有指针，找到相应数后，交换。
注意：若令第一个数为基准数，先从右往左找，再从左往右找。
2、优点：平均时间复杂度O（NlogN)，相比冒泡排序每次交换可以是跳跃式的
排序过程：
代码实现：
#include<mpi.h>
#include<time.h>
#include <stdlib.h>
#include <stdio.h>
int Partition(int* data, int start, int end) //划分数据
{
int temp = data[start]; //以第一个元素为基准
while (start < end) {
while (start < end && data[end] >= temp)end--; //找到第一个比基准小的数
data[start] = data[end];
while (start < end && data[start] <= temp)start++; //找到第一个比基准大的数
data[end] = data[start];
}
data[start] = temp; //以基准作为分界线
return start;
}
void QuickSort(int* data, int start, int end) //串行快排
{
if (start < end) { //未划分完
int r = Partition(data, start, end); //继续划分，进行递归排序
QuickSort(data, start, r - 1);
QuickSort(data, r + 1, end);
}
}
//求2的n次方
int exp2(int n)
{
int i = 1;
while (n-- > 0) i *= 2;
return i;
}
//求以2为底n的对数，向下取整
int log2(int n)
{
int i = 1, j = 2;
while (j < n) {
j *= 2;
i++;
}
return i;
}
void paraQuickSort(int* data, int start, int end, int m, int id, int nowID, int N)
{
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) < N) { //还有未接收数据的进程，则划分数据
r = Partition(data, start, end);
length = end - r;
MPI_Send(&length, 1, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
if (length > 0) //id进程将后部分数据发送给id+2^(m-1)进程
MPI_Send(data + r + 1, length, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
}
}
if (nowID == 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) < N && (length > 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) { //根进程生成随机数组
start_time = MPI_Wtime();
data = (int*)malloc(n * sizeof(int));
srand(time(NULL) + rand()); //随机数种子
for (i = 0; i < n; i++)
data[i] = (int)rand(); //获取n个随机整数
}
m = log2(size); //第一次分发需要给第2^(m-1)个进程
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); //广播n
paraQuickSort(data, 0, n - 1, m, 0, rank, size); //执行快排
if (rank == 0) { //根进程输出并行时间
end_time = MPI_Wtime();
for (i = 0; i < 10 && i<n; i++)//输出前十个元素
printf("%d ", data[i]);
printf("\n并行时间：%lfs\n", end_time - start_time);
}
MPI_Finalize();
}
运行结果：
Mpi快排结果：
注1000后面的参数为生成随机数的个数
编译：mpicxx ./filename.cpp -o ./filename
Mpi基本原理：
1.什么是MPI
Massage Passing Interface:是消息传递函数库的标准规范，由MPI论坛开发。
一种新的库描述，不是一种语言。共有上百个函数调用接口，提供与C和Fortran语言的绑定
MPI是一种标准或规范的代表，而不是特指某一个对它的具体实现
MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准
2.MPI的特点
MPI有以下的特点：
消息传递式并行程序设计
指用户必须通过显式地发送和接收消息来实现处理机间的数据交换。
在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不能直接进行，必须通过显式的消息传递来实现。
这种编程方式是大规模并行处理机（MPP）和机群（Cluster）采用的主要编程方式。
并行计算粒度大，特别适合于大规模可扩展并行算法
用户决定问题分解策略、进程间的数据交换策略，在挖掘潜在并行性方面更主动,并行计算粒度大,特别适合于大规模可扩展并行算法
消息传递是当前并行计算领域的一个非常重要的并行程序设计方式
二、MPI的基本函数
MPI调用借口的总数虽然庞大，但根据实际编写MPI的经验，常用的MPI函数是以下6个：
MPI_Init(…);
MPI_Comm_size(…);
MPI_Comm_rank(…);
MPI_Send(…);
MPI_Recv(…);
MPI_Finalize();
三、MPI的通信机制
MPI是一种基于消息传递的编程模型，不同进程间通过消息交换数据。
1.MPI点对点通信类型
所谓点对点的通信就是一个进程跟另一个进程的通信，而下面的聚合通信就是一个进程和多个进程的通信。
- 标准模式：
该模式下MPI有可能先缓冲该消息，也可能直接发送，可理解为直接送信或通过邮局送信。是最常用的发送方式。
由MPI决定是否缓冲消息
没有足够的系统缓冲区时或出于性能的考虑，MPI可能进行直接拷贝：仅当相应的接收完成后，发送语句才能返回。
这里的系统缓冲区是指由MPI系统管理的缓冲区。而非进程管理的缓冲区。
MPI环境定义有三种缓冲区：应用缓冲区、系统缓冲区、用户向系统注册的通信用缓冲区
MPI缓冲消息：发送语句在相应的接收语句完成前返回。
这时后发送的结束或称发送的完成== 消息已从发送方发出，而不是滞留在发送方的系统缓冲区中。文章来源：https://www.toymoban.com/news/detail-497530.html
该模式发送操作的成功与否依赖于接收操作，我们称之为非本地的，即发送操作的成功与否跟本地没关系。文章来源地址https://www.toymoban.com/news/detail-497530.html
到了这里，关于使用mpi并行技术实现快排Qsort（）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
