文档介绍：凌广杰:基于 MPI 的分布式并行排序算法的实现· 1·
基于 MPI 的分布式并行排序算法的实现

(信息工程学院,计算机系,计算机科学与技术专业凌广杰)
(学号:2000131031)

内容提要:本论文采用 MPI(Message Passing Interface)在由独立处理器构成的计算机网
络上实现了一个称之为 IPBPS(Interconnected Processor-Based Parallel Sorting)的分布式并
行排序算法。IPBPS 算法是基于一个特定的网络拓扑结构上,它的实现主要分为并行计数排
序与归并排序两大模块。采用 MPI 来实现 IPBPS 算法,利用 MPI 消息传递的同步机制,很
好地解决了不同处理器间消息传递的同步问题。每个处理器运行相同的程序,运行时间也几
乎相同,计算负载均匀分布在网络上的每个处理器中,因此并行加速比较高。
关键词:MPI,并行排序,并行程序设计,分布式程序设计
教师点评:该论文基于消息传递的并行计算模型,在多台独立互联的计算机上采用
MPI(消息传递接口)实现了 IPBPS 分布式并行排序算法。针对该具体问题,在任务分配、进
程通信与同步、以及采用 MPI 构建 IPBPS 算法基于的虚拟网络结构上提出了自己的设想与
实现方案。解决了在由多计算机构成的分布式计算平台上不同计算机之间计算负载的均分、
通信与同步等问题。该论文具有一定的创新性,对基于 MPI 的并行与分布式程序设计具有
一定的示范作用。论文的表达书写也比较好。(点评教师:陆楠。副教授)

1. 引言
排序计算是计算机应用中最基本的运算之一,在 20 世纪 60 年代的计算机厂家就估计,
当他们把所有的顾客都考虑在内时,在他们的计算机上,将有超过 25%的时间花在排序上
[3]。排序的重要性不言而喻,传统的串行排序算法的速度已不能满足用户的要求。为了提
高排序的速度,人们普遍转向了并行排序算法的研究。目前大部分并行排序算法的研究都是
基于共享内存的多处理器或流水(Pipeline)计算机上的,但由于多处理机中微处理器的个
数非常有限且通过共享内存可同时传送和访问的数据也不可能很多。因而这些并行排序算法
受到计算机硬件瓶颈的限制[2]。为此,我们应该建立基于分布式内存的并行计算机,并在
此基础上设计排序算法,以解决上述瓶颈。在这种并行计算机上,每个处理单元都拥有自己
独立的局部存储器,各个处理器之间通过消息传递来交换信息,以获得很好的扩展性和较高
的并行加速比。
本文试图分析和用 MPI 实现张冰老师提出的基于一种具有独立内存的计算机组成的网
络环境上的并行排序算法,我们称之为 IPBPS(Interconnected Processor-Base Parallel
Sorting)。

2. MPI 简介
MPI(Message Passing Interface)是根据全球工业、应用和研究部门的应用程序对消息
传递功能的需求,而联合推出的标准消息传递界面函数,不考虑其具体实现,以保证并行应
用程序的可移植性和可扩展性。MPI 是一个库,而不是一门语言,它易于使用、有完备的异
步和同步通信,而且可以建立虚拟的拓