（一）基于MPI 的程序设计方法
并行程序设计可以通过多种方法实现,它们各有特点,并适合于不同的场合。最常用的是共享变量方法和消息传递方法。
- 共享变量方法的主要特点是利用共享存储器中共享变量来实现处理机间的通信,它主要用在共享存储结构中。
- 消息传递方法的主要特点是不同处理机间必须通过网络传送消息来相互通信,并达到任务间需要的同步操作,它主要应用于分布式存储结构中。
MPI 是基于消息传递模型的,在这种模型中,把任务分成若干部分(进程) ,让每个处理器(节点) 独自运行不同或者相同的部分(进程) 。驻留在不同处理器(节点) 上的进程可以通过网络传递消息来互相通信,从而达到并行计算的效果,减少计算的时间。其中进程的分配、结果的收集均通过消息传递来完成。
在MPI 中,通过指定通信因子和组来对进程进行一种逻辑上的划分,通讯因子定义了进程组内或组间通讯的上下文。
（二）算法描述
输入: 长度为 n 的无序序列，p 台处理器,每台处理器有 n/p 个元素
输出 :长度为 n 的有序序列
示例说明PSRS排序过程，假定序列长度n = 27，p = 3，则PSRS排序过程如下图所示：
（三）算法流程
Begin
1.均匀划分: n 个元素均匀地划分成 p段,每台处理器有 n/p个元素。
将 N 条数据均匀划分为 p 段，每个进程处理一段数据。
其中 ( i = 0 , 1 , … , p−1 ) 号进程处理 ⌊ (i×N) / p ⌋到 ⌊ (i+1)×N / p ⌋−1 个元素；
2.局部排序:各处理器利用串行排序算法,排序 n/p个数。
各进程对各自的数据进行排序。
3.正则采样:每台处理器各从自己的有序段中选取 p 个样本元素。
p 个进程中，每个进程需要选取出 p 个样本（regular samples）。
取规则为 ⌊ i×dataLength / p ⌋ , i = 0 , 1 , … p−1 。
4. 样本排序:用一台处理器将所有 p 个样本元素用串行排序算法排序之。
用一个进程对 p 个进程的共 p×p 个样本进行排序，此时样本都是局部有序的，使用归并能减少时间复杂度。
5.选择主元:用一台处理器选取 p-1 个主元,并将其播送给其余处理器。
一个进程从排好序的样本中选取 p−1 个主元。选取方法是 i×p , i = 1 , 2 , … , p−1 。
6.主元划分:各处理器按主元将各自的有序段划分成 p 段。
p 个进程的数据按照 p−1 个主元划分为 p 段。
7.全局交换:各处理器将其辖段按段号交换到相应的处理器。
进程 i ( i = 0 , 1 , … p−1 )将第 j ( j = 0 , 1 , … , p−1 ) 段发送给进程 j 。也就是每个进程都要给其它所有进程发送数据段，并且还要从其它所有进程中接收数据段，所以称为全局交换。
8.归并排序:处理器使用归并排序将所接收的诸段施行排序。
各处理器对接收到的 p 个数据段进行归并，因为 p 个数据段已经是局部有序的。
完成以上操作后，将进程 0 到 p − 1 的数据按顺序拼接起来，就是全部数据排序结果。
End
（四）示例图片
标签：Sorting,PSRS,样本,Sampling,处理器,进程,消息传递,排序,MPI From： https://www.cnblogs.com/imreW/p/17184789.html