并行归并排序算法及其在PC集群中的实现
|
摘要
现代许多领域中具有挑战性的大规模计算课题需要高性能并行处理机，而硬件技术的迅速发展已使建造并行处理机的新一代计算机的经济可行性显著增加，但是阻碍并行处理机进入主流技术的主要问题还是在软件和应用方面。但是并行算法设计有着特殊的困难。以前我们考虑问题是按时间的顺序来考虑，而现在我们却要把整个问题看作由多个可并行的子问题组成。大型计算中心，排序被认为占用了大量的计算时间。随着并行处理技术的发展，并行排序已经成为并行算法中的一个重要的研究领域。本文提出了并详细描述了一种新的并行归并排序算法，算法充分利用了各个处理器排序后序列长度相等的特点，计算出归并段对中的一个元素和最后一个元素的位置，然后从相应的位置进行归并排序。本算法达到了较高的负载平衡性、可扩展性和排序稳定性，而且排序后，数据分布完全平衡。
现在PC机的性能不断的提高，价格下降，很好的性能价格比使很多单位普遍使用PC集群。因此，研究PC机组成的网络并行计算平台，并在其上进行并行计算，可以大大提高现有设备解决实际问题的能力且为并行算法的研究提供一个试验环境。Linux是UNIX在PC机上的实现，它是一种开放源代码的分时操作系统。它已被广泛用于并行计算平台。MPI消息传递方式是被广泛应用并行机的一种模式，特别适用于那些分布存储的并行机。十多年来，这种模式在重要的计算应用中已取得了实质进步。MPI标准已定义了与C语言、C++和Fortran的绑定。MPICH是MPI的一种稳定的实现，它可以建立与C语言、C++、Fortran 77、Fortran 90、Java的连接。我使用Linux+MPI在PC机上实现了并行计算平台并在此平台上实现了我提出的并行归并排序算法。在已有并行排序算法中，PSRS算法是效率和可扩展性较高的一种，本人在同样的条件下实现了此算法，并与本人提出的算法在理论和实验数据上作了比较，指出了本算法的优缺点。
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 the
n 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 plat
form, compared it with my algorithm and show advantage and shortcoming of my algorithm.
现在PC机的性能不断的提高，价格下降，很好的性能价格比使很多单位普遍使用PC集群。因此，研究PC机组成的网络并行计算平台，并在其上进行并行计算，可以大大提高现有设备解决实际问题的能力且为并行算法的研究提供一个试验环境。Linux是UNIX在PC机上的实现，它是一种开放源代码的分时操作系统。它已被广泛用于并行计算平台。MPI消息传递方式是被广泛应用并行机的一种模式，特别适用于那些分布存储的并行机。十多年来，这种模式在重要的计算应用中已取得了实质进步。MPI标准已定义了与C语言、C++和Fortran的绑定。MPICH是MPI的一种稳定的实现，它可以建立与C语言、C++、Fortran 77、Fortran 90、Java的连接。我使用Linux+MPI在PC机上实现了并行计算平台并在此平台上实现了我提出的并行归并排序算法。在已有并行排序算法中，PSRS算法是效率和可扩展性较高的一种，本人在同样的条件下实现了此算法，并与本人提出的算法在理论和实验数据上作了比较，指出了本算法的优缺点。
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 the
n 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 plat
form, compared it with my algorithm and show advantage and shortcoming of my algorithm.
引文
[1] 沈志宇，廖湘科，胡子昂．并行程序设计．第一版．长沙：国防科技大学出版社，1997，P3
[2] T. Anderson, D. Culler, and D. Patterson. A Case for Networks of Workstations. IEEE Micro. 1995.2
[3] Rajkumar Buyya. High Performance Cluster Computing. Prentice Hall. 1999, P38
[4] 王文义．世界级重大挑战性课题与大规模并行处理系统．郑州工业大学学报．第18卷．(第4期)：P87
[5] 刘建．并行程序设计方法学．第一版．武汉：华中理工大学出版社，2000，P46
[6] [美]Kai Hwang著．高等计算机体系结构 并行性 可扩展性 可编程性．王鼎兴，郑纬民，沈美明，温冬婵译．清华大学出版社，广西科学技术出版社．1995，P41
[7] Andrews. Tanenbaum. Modern Operating Systems. Prentice Hall. 1992, P367
[8] 李晓梅，莫则尧，胡庆丰等著．可扩展并行算法的设计与分析．第一版．北京：国防工业出版社，2000，P3
[9] 陈国良．并行算法的设计与分析．第一版．北京：高等教育出版社，1994，P78～P84
[10] K. Hwang. Advanced Parallel Processing with Supercomputer. Architectures Proc. IEEE vol. 75. 1987
[11] 戴波．并行算法及其应用：硕士论文，2002
[12] Michael J. Quinn. The PRAM Model of Parallel Computation. Parallel Computing Theory and Practice, 1994, P27～P30
[13] Culler Detc. LogP: Towards a Realistic Model of Parallel Computation. USA: the 4th ACM PPOPP, 1993
[14] Susanne E. Hambrush, Ashfag A. Khokhar. C~3: A Parallel Model for Coarse-Grained Machine. Journal of Parallel and Distribution Computing, 1996, P139
[15] Joseph F. Jaja, Kwan Woo Ryu. The Block Distributed Memory Model. IEEE Transaction on Parallel and Distributed System, 1996, 7(8)
[16] 记珊珊．基于PVM的并行计算在PC机群上的实现：硕士论文 2000
[17] http://www-unix.mcs.anl.gov/dbpp/text/book.html
[18] 陈国良．并行计算——结构、算法、编程．第一版．北京：高等教育出版社，P162
[19] http://www-900.cn.ibm.com/developerWorks/cn/linux/cluster/hpc/part4/
[20] 贾玲，王清贤．分布式并行计算环境PVM．信息工程大学学报．第1卷．(第1期)：P23
[21] http://www-unix.mcs.anl.gov/mpi/
[22] 吴锤红，吴锤结．微机网络并行计算环境Linux、并行计算平台MPI及其应用．福建农业大学学报．1997．第四期：P480
[23] 都志辉．高性能计算并行编程技术——MPI并行程序设计．第一版．北京：清华大学出版社，2001，P17
[24] http://grids.ucs.indiana.edu/ptliupages/projects/HPJava/reports/MPIposition/
[25] 朱小红．MPI并行程序设计及其实现：硕士论文 2003
[26] William Gropp, Ewing Lusk, Anthony Skjellum. Using MPI. Second Edition. The MIT Press, 1999, P111
[27] A.Aggarwal, J.S.Vilter. The input/output complexity of sorting and related problems. Comm, ACM 31 (9), (1988) , P1116-P1127
[28] 顾乃杰，王旭，陈国良，蒋凡．并行双调排序算法的有效实现及性能分析．计算机研究与发展．第39卷．(第10期)：P1344～P1348
[29] 杨利，朱和，周兴铭．三个并行排序算法的可扩充性分析．国防科技大学学报．第17卷(第4期)：1995，P67～P80
[30] ShiHanmao, Jschaeffer. Parallel sorting by regular sampling. Paralleland Distributed Computing, 1992, 14(4): P316～P372
[31] 来智勇．并行排序算法．计算机研究与发展，1995，32(6)：P46～P49
[32] 卫群，计永昶，陈国良．一种基于MPP的并行归并算法．计算机研究与发展：1999，36(1)：P52～P56
[33] 颜启华，潘久辉．划分点定位并行排序算法．计算机研究与发展：2002，39(5)：P632～P637
[34] 严蔚敏，吴伟民．数据结构．第二版．北京：清华大学出版社，1992，P285
[2] T. Anderson, D. Culler, and D. Patterson. A Case for Networks of Workstations. IEEE Micro. 1995.2
[3] Rajkumar Buyya. High Performance Cluster Computing. Prentice Hall. 1999, P38
[4] 王文义．世界级重大挑战性课题与大规模并行处理系统．郑州工业大学学报．第18卷．(第4期)：P87
[5] 刘建．并行程序设计方法学．第一版．武汉：华中理工大学出版社，2000，P46
[6] [美]Kai Hwang著．高等计算机体系结构 并行性 可扩展性 可编程性．王鼎兴，郑纬民，沈美明，温冬婵译．清华大学出版社，广西科学技术出版社．1995，P41
[7] Andrews. Tanenbaum. Modern Operating Systems. Prentice Hall. 1992, P367
[8] 李晓梅，莫则尧，胡庆丰等著．可扩展并行算法的设计与分析．第一版．北京：国防工业出版社，2000，P3
[9] 陈国良．并行算法的设计与分析．第一版．北京：高等教育出版社，1994，P78～P84
[10] K. Hwang. Advanced Parallel Processing with Supercomputer. Architectures Proc. IEEE vol. 75. 1987
[11] 戴波．并行算法及其应用：硕士论文，2002
[12] Michael J. Quinn. The PRAM Model of Parallel Computation. Parallel Computing Theory and Practice, 1994, P27～P30
[13] Culler Detc. LogP: Towards a Realistic Model of Parallel Computation. USA: the 4th ACM PPOPP, 1993
[14] Susanne E. Hambrush, Ashfag A. Khokhar. C~3: A Parallel Model for Coarse-Grained Machine. Journal of Parallel and Distribution Computing, 1996, P139
[15] Joseph F. Jaja, Kwan Woo Ryu. The Block Distributed Memory Model. IEEE Transaction on Parallel and Distributed System, 1996, 7(8)
[16] 记珊珊．基于PVM的并行计算在PC机群上的实现：硕士论文 2000
[17] http://www-unix.mcs.anl.gov/dbpp/text/book.html
[18] 陈国良．并行计算——结构、算法、编程．第一版．北京：高等教育出版社，P162
[19] http://www-900.cn.ibm.com/developerWorks/cn/linux/cluster/hpc/part4/
[20] 贾玲，王清贤．分布式并行计算环境PVM．信息工程大学学报．第1卷．(第1期)：P23
[21] http://www-unix.mcs.anl.gov/mpi/
[22] 吴锤红，吴锤结．微机网络并行计算环境Linux、并行计算平台MPI及其应用．福建农业大学学报．1997．第四期：P480
[23] 都志辉．高性能计算并行编程技术——MPI并行程序设计．第一版．北京：清华大学出版社，2001，P17
[24] http://grids.ucs.indiana.edu/ptliupages/projects/HPJava/reports/MPIposition/
[25] 朱小红．MPI并行程序设计及其实现：硕士论文 2003
[26] William Gropp, Ewing Lusk, Anthony Skjellum. Using MPI. Second Edition. The MIT Press, 1999, P111
[27] A.Aggarwal, J.S.Vilter. The input/output complexity of sorting and related problems. Comm, ACM 31 (9), (1988) , P1116-P1127
[28] 顾乃杰，王旭，陈国良，蒋凡．并行双调排序算法的有效实现及性能分析．计算机研究与发展．第39卷．(第10期)：P1344～P1348
[29] 杨利，朱和，周兴铭．三个并行排序算法的可扩充性分析．国防科技大学学报．第17卷(第4期)：1995，P67～P80
[30] ShiHanmao, Jschaeffer. Parallel sorting by regular sampling. Paralleland Distributed Computing, 1992, 14(4): P316～P372
[31] 来智勇．并行排序算法．计算机研究与发展，1995，32(6)：P46～P49
[32] 卫群，计永昶，陈国良．一种基于MPP的并行归并算法．计算机研究与发展：1999，36(1)：P52～P56
[33] 颜启华，潘久辉．划分点定位并行排序算法．计算机研究与发展：2002，39(5)：P632～P637
[34] 严蔚敏，吴伟民．数据结构．第二版．北京：清华大学出版社，1992，P285
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |