基于ECS的并行与分布式程序设计|多个数组排序任务不均衡案例的MPI编程实现

一、问题描述

对于“多个数组排序”的任务不均衡案例进行MPI编程实现，并探索不同块划分、线程数对算法运行时间的影响。

二、算法设计实现与复杂性分析

动态分配任务实现，用MPI的通信功能：

void mpi_sort(void)
{
    MPI_Status status;
    while (1) {
    //接收任务（g行）
    MPI_Recv(&arr[0][0], g * ARR_LEN, MPI_FLOAT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
    if (status.MPI_TAG >= ARR_NUM)  //任务已全部完成
    return;
    for (int i = 0; i < g; i++)stable_sort(arr[i].begin(), arr[i].end());
    MPI_Send(&arr[0][0], g * ARR_LEN, MPI_FLOAT, 0, status.MPI_TAG, MPI_COMM_WORLD); //发送排序结果
    }
}
int main(){
    for (int i = 0; i < ARR_NUM; i++)arr[i].resize(ARR_LEN);
    for (int i = 0; i < ARR_NUM; i++)arr_result[i].resize(ARR_LEN);
    int my_rank, comm_sz;
    int source;
    MPI_Init(NULL, NULL);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
    if (my_rank!= 0) {
        mpi_sort();
    }
    else{
    printf("rank0\n");
    MPI_Status status;
    init();
    int i, finished = 1;
    clock_t begin;
    for (i = 1; i < size&&i * g < ARR_NUM; i++) //为每个进程发送一个任务，行号作为tag dest=i,tag=i*g
    {   
        printf("rank0 send to %d\n",i);
        MPI_Send(&arr[i * g][0], ARR_LEN * g, MPI_FLOAT, i, i * g, MPI_COMM_WORLD);
    }
    while (finished < size) {
        //接收结果，不能指定源进程号（MPI_ANY_SOURCE）
        MPI_Recv(&arr_result[0][0], ARR_LEN * g, MPI_FLOAT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        printf("rank0 recv from %d\n",status.MPI_SOURCE);
        //把接收到的结果复制进原数组
        memcpy(&arr[status.MPI_TAG][0], &arr_result[0][0], sizeof(float) * ARR_LEN * g);
    if (i * g < ARR_NUM) {  //继续分任务
        printf("rank0 send to %d\n",status.MPI_SOURCE);
        MPI_Send(&arr[i * g][0], ARR_LEN * g, MPI_FLOAT, status.MPI_SOURCE, i * g, MPI_COMM_WORLD);
        i++; 
        }
        else {  //告诉线程任务已完成
        MPI_Send(&arr[0][0], ARR_LEN * g, MPI_FLOAT, status.MPI_SOURCE, ARR_NUM+1, MPI_COMM_WORLD);
        finished++; //完成任务的线程数+1
        printf("%d finished\n",status.MPI_SOURCE);
    }
    }
    clock_t end;
    double cost = (double)(end - begin) / CLK_TCK;
    printf("%fms\n", cost);
    }
MPI_Finalize();
return 0;
}

三、实验及结果分析

1. 实验环境：操作系统linux，鲲鹏通用计算增强型 | kc1.large.2 | 2vCPUs | 4GiB
2. 计时方法：<time.h>的clock()
3. 实验数据：

• 矩阵规模：10000*1000
• 矩阵初始化：分布不均衡的矩阵

第一段：完全逆序 第二段：1/2 逆序，1/2 升序

第三段：1/4 逆序，3/4 升序 第四段：完全升序

//随机不均匀
void init(void)
{
    int ratio;
    srand(unsigned(time(NULL)));
    for (int i = 0; i < ARR_NUM; i++) {
    if (i < g) ratio = 0;
    else if (i < g * 2) ratio = 32;
    else if (i < g * 3) ratio = 64;
    else ratio = 128;
    if ((rand() & 127) < ratio)
    for (int j = 0; j < ARR_LEN; j++)arr[i][j] = ARR_LEN - j;
    else for (int j = 0; j < ARR_LEN; j++)arr[i][j] = j;
    }
}

四、实验设计与结果

组一：线程总数为6，三台主机平均分配，改变动态划分的块大小：

结果：

结果分析：可见在本实验条件下，块大小对MPI动态任务分配算法的运行时间是有影响的，在块大小为400时，时间效率达到最高值。因此选择合适的分块大小有助于提高MPI动态任务分配算法解决该问题的运行效率。

组二：分块大小为50，线程数为6，9，12，15

结果分析：可见实验条件下线程数对算法的时间效率有影响，且随着线程数增大，运行时间变长。可能是本实验中单个线程执行的任务复杂度较低，而消息传递的过程相对较复杂，因此线程越多，并行执行计算带来的时间优势不明显，反而在信息传递的过程中耗费较多时间，拖慢程序的运行速率。因此在实际中运用MPI编程消息传递解决问题时，要充分考虑问题的复杂度、规模等因素，选择合适的线程数和分配策略。

备注：

1.基础配置

2.网络配置

3. makefile

EXECS=array_sort_mpi
MPICC?=mpicxx
all: ${EXECS}
array_sort_mpi: array_sort.cpp
	sudo ${MPICC} -o array_sort_mpi array_sort.cpp
clean:
	sudo rm -f ${EXECS}

4.config

ecs-hw-0003:2
ecs-hw-0002:2
ecs-hw-0001:2