Parallel Merge Sort Algorithm And Its Realization In The Pc Cluster

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.