【MPI】并行奇偶交换排序

75 阅读 0 评论 50 点赞

我是靠谱客的博主欣慰冷风，这篇文章主要介绍【MPI】并行奇偶交换排序，现在分享给大家，希望可以做个参考。

复制代码

typedef long long __int64;
#include "mpi.h"
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int Compute_partner(int phase,int my_rank,int comm_sz){//根据趟数的奇偶性以及当前编号的编号得到partner进程的编号
    int partner;
    if(!(phase&1)){
        if(my_rank&1){
            partner=my_rank-1;
        }
        else{
            partner=my_rank+1;
        }
    }
    else{
        if(my_rank&1){
            partner=my_rank+1;
        }
        else{
            partner=my_rank-1;
        }
    }
    if(partner==-1 || partner==comm_sz){
        partner=MPI_PROC_NULL;
    }
    return partner;
}
int main(int argc, char* argv[]){
    int my_rank=0, comm_sz=0;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    int np,n,local_n;//分别为进行奇偶交换排序的趟数和读入的数据总量以及分成的每段的长度
    FILE* fp;
    if(my_rank==0){
        fp=fopen("Sort.txt","r");
        fscanf(fp,"%d%d",&np,&n);
        local_n=n/comm_sz;
    }
    MPI_Bcast(&np,1,MPI_INT,0,MPI_COMM_WORLD);
    MPI_Bcast(&local_n,1,MPI_INT,0,MPI_COMM_WORLD);
    int* keys;
    int* my_keys=new int[local_n];
    if(my_rank==0){
        keys=new int[n];
        for(int i=0;i<n;++i){
            fscanf(fp,"%d",&keys[i]);
        }
        fclose(fp);
    }
    double beginTime = MPI_Wtime();
    MPI_Scatter(keys,local_n,MPI_INT,my_keys,local_n,MPI_INT,0,MPI_COMM_WORLD);

//sort(my_keys,my_keys+local_n);//串行快速排序

for(int i=0;i<local_n;++i){//串行奇偶交换排序
        if(!(i&1)){
            for(int j=0;j+1<local_n;j+=2){
                if(my_keys[j]>my_keys[j+1]){
                    swap(my_keys[j],my_keys[j+1]);
                }
            }
        }
        else{
            for(int j=1;j+1<local_n;j+=2){
                if(my_keys[j]>my_keys[j+1]){
                    swap(my_keys[j],my_keys[j+1]);
                }
            }
        }
    }

int* recv_keys=new int[local_n];
    int* temp_keys=new int[local_n];
    for(int i=0;i<np;++i){
        int partner=Compute_partner(i, my_rank, comm_sz);
        if (partner != MPI_PROC_NULL){
            MPI_Sendrecv(my_keys, local_n, MPI_INT, partner, 0, recv_keys, local_n, MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            if(my_rank<partner){//编号小的进程留下归并时较小的一半
                int e=0,e1=0,e2=0;
                int* temp_keys=new int[local_n];
                while(e<local_n){
                    if(my_keys[e1]<=recv_keys[e2]){
                        temp_keys[e]=my_keys[e1];
                        ++e;
                        ++e1;
                    }
                    else{
                        temp_keys[e]=recv_keys[e2];
                        ++e;
                        ++e2;
                    }
                }
                for(int j=0;j<local_n;++j){
                    my_keys[j]=temp_keys[j];
                }
            }
            else{//编号大的进程留下归并时较大的一半
                int e=local_n-1,e1=local_n-1,e2=local_n-1;
                while(e>=0){
                    if(my_keys[e1]>=recv_keys[e2]){
                        temp_keys[e]=my_keys[e1];
                        --e;
                        --e1;
                    }
                    else{
                        temp_keys[e]=recv_keys[e2];
                        --e;
                        --e2;
                    }
                }
                for(int j=0;j<local_n;++j){
                    my_keys[j]=temp_keys[j];
                }
            }
        }
    }
    MPI_Gather(my_keys, local_n, MPI_INT, keys, local_n, MPI_INT, 0, MPI_COMM_WORLD);
    double endTime = MPI_Wtime();
    if (my_rank == 0){
        for(int i=0;i<n;++i){
            printf("%d ",keys[i]);
        }
        puts("");
        printf("spent time = %lf secondn", endTime - beginTime);
    }
    delete[] keys;
    delete[] my_keys;
    delete[] recv_keys;
    delete[] temp_keys;
    MPI_Finalize();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
typedef long long __int64;
#include "mpi.h"
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int Compute_partner(int phase,int my_rank,int comm_sz){//根据趟数的奇偶性以及当前编号的编号得到partner进程的编号
    int partner;
    if(!(phase&1)){
        if(my_rank&1){
            partner=my_rank-1;
        }
        else{
            partner=my_rank+1;
        }
    }
    else{
        if(my_rank&1){
            partner=my_rank+1;
        }
        else{
            partner=my_rank-1;
        }
    }
    if(partner==-1 || partner==comm_sz){
        partner=MPI_PROC_NULL;
    }
    return partner;
}
int main(int argc, char* argv[]){
    int my_rank=0, comm_sz=0;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    int np,n,local_n;//分别为进行奇偶交换排序的趟数和读入的数据总量以及分成的每段的长度
    FILE* fp;
    if(my_rank==0){
        fp=fopen("Sort.txt","r");
        fscanf(fp,"%d%d",&np,&n);
        local_n=n/comm_sz;
    }
    MPI_Bcast(&np,1,MPI_INT,0,MPI_COMM_WORLD);
    MPI_Bcast(&local_n,1,MPI_INT,0,MPI_COMM_WORLD);
    int* keys;
    int* my_keys=new int[local_n];
    if(my_rank==0){
        keys=new int[n];
        for(int i=0;i<n;++i){
            fscanf(fp,"%d",&keys[i]);
        }
        fclose(fp);
    }
    double beginTime = MPI_Wtime();
    MPI_Scatter(keys,local_n,MPI_INT,my_keys,local_n,MPI_INT,0,MPI_COMM_WORLD);

    //sort(my_keys,my_keys+local_n);//串行快速排序

    for(int i=0;i<local_n;++i){//串行奇偶交换排序
        if(!(i&1)){
            for(int j=0;j+1<local_n;j+=2){
                if(my_keys[j]>my_keys[j+1]){
                    swap(my_keys[j],my_keys[j+1]);
                }
            }
        }
        else{
            for(int j=1;j+1<local_n;j+=2){
                if(my_keys[j]>my_keys[j+1]){
                    swap(my_keys[j],my_keys[j+1]);
                }
            }
        }
    }

    int* recv_keys=new int[local_n];
    int* temp_keys=new int[local_n];
    for(int i=0;i<np;++i){
        int partner=Compute_partner(i, my_rank, comm_sz);
        if (partner != MPI_PROC_NULL){
            MPI_Sendrecv(my_keys, local_n, MPI_INT, partner, 0, recv_keys, local_n, MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            if(my_rank<partner){//编号小的进程留下归并时较小的一半
                int e=0,e1=0,e2=0;
                int* temp_keys=new int[local_n];
                while(e<local_n){
                    if(my_keys[e1]<=recv_keys[e2]){
                        temp_keys[e]=my_keys[e1];
                        ++e;
                        ++e1;
                    }
                    else{
                        temp_keys[e]=recv_keys[e2];
                        ++e;
                        ++e2;
                    }
                }
                for(int j=0;j<local_n;++j){
                    my_keys[j]=temp_keys[j];
                }
            }
            else{//编号大的进程留下归并时较大的一半
                int e=local_n-1,e1=local_n-1,e2=local_n-1;
                while(e>=0){
                    if(my_keys[e1]>=recv_keys[e2]){
                        temp_keys[e]=my_keys[e1];
                        --e;
                        --e1;
                    }
                    else{
                        temp_keys[e]=recv_keys[e2];
                        --e;
                        --e2;
                    }
                }
                for(int j=0;j<local_n;++j){
                    my_keys[j]=temp_keys[j];
                }
            }
        }
    }
    MPI_Gather(my_keys, local_n, MPI_INT, keys, local_n, MPI_INT, 0, MPI_COMM_WORLD);
    double endTime = MPI_Wtime();
    if (my_rank == 0){
        for(int i=0;i<n;++i){
            printf("%d ",keys[i]);
        }
        puts("");
        printf("spent time = %lf secondn", endTime - beginTime);
    }
    delete[] keys;
    delete[] my_keys;
    delete[] recv_keys;
    delete[] temp_keys;
    MPI_Finalize();
    return 0;
}