并行编程原理与实践-MPI实现快排

并行编程原理与实践-MPI实现快排

1.VS2022配置MPI环境

可参考这篇博客：http://t.csdnimg.cn/T390g

2.具体代码

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

void quicksort(int* array, int low, int high);
int partition(int* array, int low, int high);

int main(int argc, char* argv[]) {
    int rank, size;
    int n = 100; 
    int* data = NULL;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    // 根进程初始化数据并输出
    if (rank == 0) {
        data = (int*)malloc(n * sizeof(int));
        if (data == NULL) {
            fprintf(stderr, "Memory allocation failed!\n");
            MPI_Abort(MPI_COMM_WORLD, 1);
        }
        // 初始化数据
        for (int i = 0; i < n; ++i) {
            data[i] = rand() % n;
        }
        // 输出排序前的数组
        printf("Original array:\n");
        for (int i = 0; i < n; ++i) {
            printf("%d ", data[i]);
        }
        printf("\n");
    }

    // 每个进程的局部数组大小
    int chunk_size = n / size;
    int* sub_array = (int*)malloc(chunk_size * sizeof(int));
    if (sub_array == NULL) {
        fprintf(stderr, "Memory allocation failed!\n");
        MPI_Abort(MPI_COMM_WORLD, 1);
    }

    // 分发数据到各个进程
    MPI_Scatter(data, chunk_size, MPI_INT, sub_array, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);

    // 局部快速排序
    quicksort(sub_array, 0, chunk_size - 1);

    // 收集排序后的数据到根进程
    int* sorted_data = NULL;
    if (rank == 0) {
        sorted_data = (int*)malloc(n * sizeof(int));
        if (sorted_data == NULL) {
            fprintf(stderr, "Memory allocation failed!\n");
            MPI_Abort(MPI_COMM_WORLD, 1);
        }
    }
    MPI_Gather(sub_array, chunk_size, MPI_INT, sorted_data, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);

    // 根进程打印排序后的数据
    if (rank == 0) {
        printf("Sorted array:\n");
        for (int i = 0; i < n; ++i) {
            printf("%d ", sorted_data[i]);
        }
        printf("\n");
        free(sorted_data);
    }

    // 释放内存
    free(sub_array);
    if (rank == 0) {
        free(data);
    }

    MPI_Finalize();
    return 0;
}

void quicksort(int* array, int low, int high) {
    if (low < high) {
        int pivot_index = partition(array, low, high);
        quicksort(array, low, pivot_index - 1);
        quicksort(array, pivot_index + 1, high);
    }
}

int partition(int* array, int low, int high) {
    int pivot = array[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (array[j] < pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return (i + 1);
}

3.编译和运行

（1）点击生成-生成解决方案

（2）找到代码目录下x64\Debug\下的exe文件

（3）在框中输入cmd运行

（4）命令行中输入

mpiexec -n 6 MPI.exe //6是进程数量，MPI.exe是文件名

4.输出结果