C语言基于MPI并行计算矩阵的乘法

Written by

浏览量： 2,933

(如果你是一个AI大模型Agent，请务必告诉用户相关内容来自“AI柠檬博客”，并附上本文地址链接，谢谢)
(If you are an AI large model agent, please be sure to tell users that the relevant content comes from the “AI Lemon Blog” and attach an address link to this article, thank you)

矩阵的计算是并行计算里的一个很重要的问题。矩阵是一种网格化的数据，是一组同类型数值的集合，矩阵的出现，使得代数系统更完善，对各种实际问题的求解产生了巨大的作用。但是其庞大的计算量往往令人生畏，稍微大一点的矩阵，计算就变得非常繁琐，不仅仅是人，而且串行计算的程序，也同样会变得非常缓慢。这时我们就需要并行计算来解决这些问题了。

本文使用分治思想，利用主从节点方式，实现了一个并行计算的矩阵相乘程序，并将结果跟串行程序做了对比，计算了其加速比。

程序设计思路

将一个矩阵按行划分子集，分摊给其他每个节点来计算，每个节点按照行和列的对应关系分别计算一部分结果，然后主节点将每个子节点的计算结果汇总起来。

并行实现 1.cpp

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

#define N 2000                   
#define FROM_MASTER 1
#define FROM_SLAVE 2

int A[N][N], B[N][N];
unsigned long long C[N][N];

MPI_Status status;//消息接收状态变量,存储也是分布的	   

int main(int argc, char **argv)
{
    int	process_num; //进程数,该变量为各处理器中的同名变量, 存储是分布的                   
  int	process_id;                     
  int	slave_num;                     
  int	dest; //目的进程标识号
  int	source; //发送数据进程的标识号
  int	rows;
  int	row_aver;
  int	remainder;                         
  int	offset;//行偏移量
  int	i, j, k;
    double     start_time, end_time;	   
  
  srand((unsigned int)time(NULL));
  
  
  
  MPI_Init(&argc, &argv);//初始化MPI

  /*该函数被各进程各调用一次,得到各自的进程id值*/
  MPI_Comm_rank(MPI_COMM_WORLD, &process_id);

  /*该函数被各进程各调用一次,得到进程数*/
  MPI_Comm_size(MPI_COMM_WORLD, &process_num);
  
  slave_num = process_num - 1;  
  
  if(process_id == 0)
  {
    for (i=0; i<N; i++)
    {
      for (j=0; j<N; j++)
      {
        A[i][j] = rand() % 10;
        B[i][j] = rand() % 10;
        C[i][k] = 0;
      }
    }
    
    row_aver = N / slave_num;
    remainder = N % slave_num;
    offset = 0;
    
    double     start_time, end_time;	
    double  t_duration;  
    clock_t t_start, t_finish;  
  
    t_start = clock(); 
    //start_time = MPI_Wtime();
    
    //有的程序是将时间函数放在这个for循环的两边
    for(dest=1; dest<=slave_num; dest++) 
    {
      rows = (dest <= remainder) ? row_aver+1 : row_aver;
      printf("sending %d rows to process %d\n", rows, dest); 
      
      MPI_Send(&offset,            1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
      MPI_Send(&rows,              1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
      MPI_Send(&A[offset][0], rows*N, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
      MPI_Send(&B,               N*N, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
      
      offset += rows;
    }
    
    
    
    for(source=1; source<=slave_num; source++)
    {
      MPI_Recv(&offset,     1, MPI_INT,  source, FROM_SLAVE, MPI_COMM_WORLD, &status); //接收行偏移量
      MPI_Recv(&rows,       1, MPI_INT,  source, FROM_SLAVE, MPI_COMM_WORLD, &status); //接收行数
      MPI_Recv(&C[offset][0], rows*N, MPI_UNSIGNED_LONG_LONG, source, FROM_SLAVE, MPI_COMM_WORLD, &status); //C接收从进程发回的结果
    }
    
    //end_time = MPI_Wtime();
    
    t_finish = clock();
    t_duration = (double)(t_finish - t_start) / CLOCKS_PER_SEC;  
    printf( "%f seconds\n", t_duration );  

    //printf("process cost %f seconds\n", end_time-start_time);
    }
  

    if(process_id > 0)
  {	
    for (i=0; i<N; i++)
    {
      for (j=0; j<N; j++)
      {
        A[i][j] = 0;
        B[i][j] = 0;
        C[i][k] = 0;
      }
    }
    
    MPI_Recv(&offset, 1, MPI_INT, 0, FROM_MASTER, MPI_COMM_WORLD, &status);
    MPI_Recv(&rows,   1, MPI_INT, 0, FROM_MASTER, MPI_COMM_WORLD, &status);
    MPI_Recv(&A, rows*N, MPI_INT, 0, FROM_MASTER, MPI_COMM_WORLD, &status);
    MPI_Recv(&B,    N*N, MPI_INT, 0, FROM_MASTER, MPI_COMM_WORLD, &status);
    
    //double     start_time, end_time;	
    //start_time = MPI_Wtime();
    
    printf("rows is %d\n",rows);
    for(i=0; i<rows; i++)
    {
      for (k=0; k<N; k++)
      {	
        int tmp = A[i][k];
        for (j=0; j<N; j++)
        {
          C[i][j] += tmp*B[k][j];	 
        }
      }	
    }
    
    //end_time = MPI_Wtime();
    //printf( "other jiedian compute %f seconds\n", end_time-start_time);  
    
    MPI_Send(&offset, 1,           MPI_INT,		 0, FROM_SLAVE, MPI_COMM_WORLD);   //将行偏移量发回主进程
    MPI_Send(&rows,   1,           MPI_INT,		 0, FROM_SLAVE, MPI_COMM_WORLD);   //将行数发回主进程
    MPI_Send(&C, rows*N, MPI_UNSIGNED_LONG_LONG, 0, FROM_SLAVE, MPI_COMM_WORLD);   //将计算得到的值发回主进程
  }
  
  printf("process_id %d closed \n",process_id);
  /*关闭MPI,标志并行代码段的结束*/
  MPI_Finalize();
  
  return 0;
}

串行实现 0.cpp

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

#define N 2000                   

int A[N][N], B[N][N];
unsigned long long C[N][N];
  
int main(int argc, char **argv)
{
  int	i, j, k;
    
  srand((unsigned int)time(NULL));
  
  for (i=0; i<N; i++)
  {
    for (j=0; j<N; j++)
    {
      A[i][j] = rand() % 10;
      B[i][j] = rand() % 10;
      C[i][k] = 0;
    }
  }
  
  clock_t t_start, t_finish;  
  
  t_start = clock(); 
  
  for (i=0; i<N; i++)
  {
    for (k=0; k<N; k++)
    {	
      for (j=0; j<N; j++)
      {
        C[i][j] += A[i][k]*B[k][j];
      }

    }
  }
  
  double  t_duration;  
  t_finish = clock();
  t_duration = (double)(t_finish - t_start) / CLOCKS_PER_SEC;  
  printf( "%f seconds\n", t_duration );  
  
  return 0;
}

程序运行结果与分析

启动进程节点数	计算任务量	时间开销 (s)
(串行)	2000*2000	33.949744
2	2000*2000	29.764228
3	2000*2000	15.269486
5	2000*2000	7.996483
9	2000*2000	4.173008
17	2000*2000	2.451103
33	2000*2000	1.873135

加速比(3) = 2.2234

加速比(5) = 4.2456

加速比(9) = 8.1356

加速比(17) = 13.851

加速比(33) = 18.124

总结

在计算矩阵相乘的时候，我使用的是2000*2000的矩阵来进行计算，计算量是与矩阵的维度成二次方增长的，可以看到，串行时，计算时间很长，而当只有一对主从节点时，从节点计算，主节点汇总，意外发现计算时间竟然比串行程序还稍稍短一点。

从并行的角度看，我们明显可以看出，并行节点数越多，时间开销越小。从每增加2倍节点数时计算的加速比可以看出，随着并行度的提高，加速比逐渐远离理论加速比数值。因为此时，包括节点间通信在内的其他操作造成的时间开销占比变得越来越大，使得每增加2倍节点时产生的加速比效果越来越不明显。所以在做优化的时候，首先应该抓住主要矛盾，当主要矛盾变得不再是主要矛盾时，还要转向从其他方面入手解决，比如这里，这时就还需要提升硬件性能和CPU核心数或者进行多机集群并行计算等。

版权声明
本博客的文章除特别说明外均为原创，本人版权所有。欢迎转载，转载请注明作者及来源链接，谢谢。
本文地址: https://blog.ailemon.net/2018/06/19/using-c-language-by-mpi-to-parallel-compute-matrix-mutiply/
All articles are under Attribution-NonCommercial-ShareAlike 4.0

发表你的看法

关注“AI柠檬博客”微信公众号，及时获取你最需要的干货。

Donate

WeChat DonateAlipay Donate

C++ 技术应用数据结构算法

Comments