MPI实现奇偶排序

发表于 更新于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 9 分钟

作业要求

使用$MPI$实现奇偶排序:$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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <mpi.h>
#include <bits/stdc++.h>
void merge_low(int *a, int *b, int lengthA, int lengthB)
{
    int i = 0, j = 0, k = 0;
    int tempLength = lengthA < lengthB ? lengthA : lengthB;
    int *temp = (int *)calloc(tempLength, sizeof(int));
    while (k < tempLength)
    {
        if (a[i] <= b[j])
        {
            temp[k] = a[i];
            ++k, ++i;
        }
        else
        {
            temp[k] = b[j];
            ++k, ++j;
        }
    }
    memcpy(a, temp, tempLength * sizeof(int));
}
void merge_high(int *a, int *b, int lengthA, int lengthB)
{
    int tempLength = lengthA > lengthB ? lengthA : lengthB;
    int i = lengthA - 1, j = lengthB - 1, k = tempLength - 1;
    int *temp = (int *)calloc(tempLength, sizeof(int));
    while (k >= 0)
    {
        if (a[i] >= b[j])
        {
            temp[k] = a[i];
            --k, --i;
        }
        else
        {
            temp[k] = b[j];
            --k, --j;
        }
    }
    memcpy(a, temp, tempLength * sizeof(int));
}
int find_partner(int rank, int phase, int nrProcesses)
{
    int partner;
    if (phase & 1)
        partner = rank % 2 == 0 ? --rank : ++rank;
    else
        partner = rank % 2 == 0 ? ++rank : --rank;
    return (partner > nrProcesses - 1 || partner <= 0) ? -1 : partner;
}
void odd_even_sort(int *localArray, int sliceLength, int rank, int nrProcesses, int globalLength)
{
    int phase;
    std::sort(localArray, localArray + sliceLength); // 把localarray先排好序
    for (phase = 0; phase < nrProcesses; ++phase)    // 按书上定理，有p个进程就只需p个阶段
    {
        MPI_Status status;
        int partner = find_partner(rank, phase, nrProcesses);
        int partnerLength = globalLength / (nrProcesses - 1);
        if (partner == nrProcesses - 1)
            partnerLength = globalLength - (partner - 1) * partnerLength;
        int *partnerArray = (int *)calloc(partnerLength, sizeof(int));
        if (partner != -1)
        {
            if (phase & 1)
            {
                MPI_Send(localArray, sliceLength, MPI_INT, partner, 0, MPI_COMM_WORLD);
                MPI_Recv(partnerArray, partnerLength, MPI_INT, partner, 0, MPI_COMM_WORLD, &status);
                if (rank % 2 != 0)
                    merge_low(localArray, partnerArray, sliceLength, partnerLength);
                else
                    merge_high(localArray, partnerArray, sliceLength, partnerLength);
            }
            else
            {
                MPI_Send(localArray, sliceLength, MPI_INT, partner, 0, MPI_COMM_WORLD);
                MPI_Recv(partnerArray, partnerLength, MPI_INT, partner, 0, MPI_COMM_WORLD, &status);
                if (rank % 2 != 0)
                    merge_high(localArray, partnerArray, sliceLength, partnerLength);
                else
                    merge_low(localArray, partnerArray, sliceLength, partnerLength);
            }
        }
    }
}
signed main(int argc, char *argv[])
{
    int nrProcesses, rank;
    int *initialArray;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &nrProcesses);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    if (rank == 0)
    {
        int arrayLength = 0, currentOffset = 0;
        // 主进程把数组读入
        std::ifstream fin("input.txt");
        fin >> arrayLength;
        initialArray = new int[arrayLength];
        int x;
        for (int i = 0; i < arrayLength; i++)
        {
            fin >> x;
            initialArray[i] = x;
        }
        fin.close();
        int *sortedArray = (int *)calloc(arrayLength, sizeof(int));
        for (int i = 1; i < nrProcesses; ++i)
        {
            int sliceLength = arrayLength / (nrProcesses - 1);
            if (i == nrProcesses - 1) // 对于最后一个进程，特别处理一下它分到的sliceLength
                sliceLength = arrayLength - (i - 1) * sliceLength;
            // 把每个localArray处理出来，发给工作进程
            int *localArray = (int *)calloc(sliceLength, sizeof(int));
            memcpy(localArray, initialArray + currentOffset, sliceLength * sizeof(int));
            currentOffset += sliceLength;
            MPI_Send(&arrayLength, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            MPI_Send(&sliceLength, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            MPI_Send(localArray, sliceLength, MPI_INT, i, 0, MPI_COMM_WORLD);
            free(localArray);
        }
        // 接受发回来的数组，把它们组装起来
        currentOffset = 0;
        for (int i = 1; i < nrProcesses; ++i)
        {
            int sliceLength = arrayLength / (nrProcesses - 1);
            MPI_Status status;
            if (i == nrProcesses - 1)
                sliceLength = arrayLength - (i - 1) * sliceLength;
            int *receivedArray = (int *)calloc(arrayLength, sizeof(int));
            MPI_Recv(receivedArray, sliceLength, MPI_INT, i, 0, MPI_COMM_WORLD, &status);
            for (int i = 0; i < sliceLength; i++)
                sortedArray[currentOffset + i] = receivedArray[i];
            currentOffset += sliceLength;
            free(receivedArray);
        }
        // 打印结果数组
        std::ofstream fout("output.txt");
        for (int i = 0; i < arrayLength; i++)
            fout << sortedArray[i] << ' ';
        fout << '\n';
        fout.close();
        std::cout << "排序完毕, 请查看output.txt" << '\n';
    }
    else
    {
        // 工作进程
        int arrayLength, sliceLength;
        // 接受主进程发过来的待处理数组
        MPI_Status status;
        MPI_Recv(&arrayLength, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
        MPI_Recv(&sliceLength, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
        int *receivedArray = (int *)calloc(sliceLength, sizeof(int));
        MPI_Recv(receivedArray, sliceLength, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
        // 工作，实现奇偶排序具体算法
        odd_even_sort(receivedArray, sliceLength, rank, nrProcesses, arrayLength);
        // 发回给主进程
        MPI_Send(receivedArray, sliceLength, MPI_INT, 0, 0, MPI_COMM_WORLD);
        free(receivedArray);
    }
    MPI_Finalize();
    return 0;
}

运行方式

1
2
3
4
运行环境：wsl2(Ubuntu 20.04)
编辑器：vscode
编译命令：mpicxx homework.cpp -o homework  (需先sudo apt install mpich)
运行命令：mpiexec -n 8 ./homework (-n用于指定进程数，8代表分配了8个进程)