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

浏览量： 2,555

(在苹果系统下，如果文章中的图片不能正常显示，请升级Safari浏览器到最新版本，或者使用Chrome、Firefox浏览器打开。)

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

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

程序设计思路

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

并行实现 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柠檬博客”微信公众号，及时获取你最需要的干货。