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

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

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

 

程序设计思路

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

 

并行实现 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核心数或者进行多机集群并行计算等。

 

打赏作者
很喜欢这篇文章,赞赏一下作者,以激励其创作出更多好文!

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

分享到社交网络:

发表评论

电子邮件地址不会被公开。 必填项已用*标注