并行归并排序算法及其在PC集群中的实现

【作者】 邱涌；

【导师】 王文义；

【作者基本信息】 郑州大学 ， 计算机应用技术， 2004， 硕士

【摘要】 现代许多领域中具有挑战性的大规模计算课题需要高性能并行处理机，而硬件技术的迅速发展已使建造并行处理机的新一代计算机的经济可行性显著增加，但是阻碍并行处理机进入主流技术的主要问题还是在软件和应用方面。但是并行算法设计有着特殊的困难。以前我们考虑问题是按时间的顺序来考虑，而现在我们却要把整个问题看作由多个可并行的子问题组成。大型计算中心，排序被认为占用了大量的计算时间。随着并行处理技术的发展，并行排序已经成为并行算法中的一个重要的研究领域。本文提出了并详细描述了一种新的并行归并排序算法，算法充分利用了各个处理器排序后序列长度相等的特点，计算出归并段对中的一个元素和最后一个元素的位置，然后从相应的位置进行归并排序。本算法达到了较高的负载平衡性、可扩展性和排序稳定性，而且排序后，数据分布完全平衡。 现在PC机的性能不断的提高，价格下降，很好的性能价格比使很多单位普遍使用PC集群。因此，研究PC机组成的网络并行计算平台，并在其上进行并行计算，可以大大提高现有设备解决实际问题的能力且为并行算法的研究提供一个试验环境。Linux是UNIX在PC机上的实现，它是一种开放源代码的分时操作系统。它已被广泛用于并行计算平台。MPI消息传递方式是被广泛应用并行机的一种模式，特别适用于那些分布存储的并行机。十多年来，这种模式在重要的计算应用中已取得了实质进步。MPI标准已定义了与C语言、C++和Fortran的绑定。MPICH是MPI的一种稳定的实现，它可以建立与C语言、C++、Fortran 77、Fortran 90、Java的连接。我使用Linux+MPI在PC机上实现了并行计算平台并在此平台上实现了我提出的并行归并排序算法。在已有并行排序算法中，PSRS算法是效率和可扩展性较高的一种，本人在同样的条件下实现了此算法，并与本人提出的算法在理论和实验数据上作了比较，指出了本算法的优缺点。更多还原

【Abstract】 The challenging and massive computation problem in many modern fields need parallel computers of high performance, and with development of the technology of hardware the economic feasibility of building parallel computer is increasing intensely, but the main problem that prevent parallel technology becoming the mainstream technology lies in the software and the application. There are special difficulties in designing parallel algorithm. Previously, we thought a problem in term of time, but now, we think a whole problem made up of many parallelizable son problems. In the big computation center, sorting is thought of occupying much time. With development of parallel technology, parallel sorting has already become an important research realm. This paper proposes and describes a new parallel sorting algorithm. It takes advantage of character that the length of the list in every processor is equal after sorting in a parallel system. It computes the positions of the first and last elements in merging pair, and then make merging sorting from those positions. The algorithm distributes data averagely after sorting and reach high efficiency, scalability and stability.Now, PCs’ performance is increasing and price is decreasing, and many units use PC clusters according to the high ratio of performance and value. So researching cluster making up of PCs and doing parallel computing can increase power of facility and provide an experimentation environment to them who researching parallel algorithm. Linux is realization of UNIX on PC, and it is open source and time-sharing operating system. MPI (Message passing Interface) is a mode widely used by parallel computers, and particularly is fit to parallel computer with distributed memory. For ten years, this mode has made material progress in application of computers. The Standard of MPI has defined binding to C, C++ and Fortran. MPICH is one of stable realization of MPI. It can build joint to C, C++, Fortran and Java. I have realized parallel platform using Linux+MPI and my algorithm on this platform. Among the parallel sorting algorithms that have been proposed, PSRS is more efficient and scalable. I realized it on the same platform, compared it with my algorithm and show advantage and shortcoming of my algorithm.更多还原