基于MPI的Warshall算法实现及其优化

基于MPI的Warshall算法实现及其优化

1. Warshall算法分析

1.1 Warshall算法(串行)分析

Warshall算法是求解关系矩阵传递闭包的算法。

输入：关系R的关系矩阵

输出：关系R的传递闭包矩阵

1.1.1 Warshall算法的串行算法分析

Warshall算法的串行算法类C描述

初始化矩阵；

for (i=0;i<n;i++)

    for (j=0;j<n;j++)

{for(k=0;k<n;k++)

a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);

}

       输出传递闭包矩阵;

1.2 Warshall算法的并行算法分析

for(i=0;i<N;i++)

    for(j=0;j<N;j++)

if(a[j][i])

{0号进程把i值发送给pro号进程；

0号进程把j值发送给pro号进程；

0号进程第i行值发送给pro号进程；

0号进程第j行值发送给pro号进程；

0号进程接收pro号进程发来的处理后的第j行的值，并放到0进程的第j行中；

}

{进程pro接收进程0发送的i的值；

进程pro接收进程0发送的j的值；

进程pro接收进程0发送的第i行元素；

进程pro接收进程0发送的第j行元素；

第i行元素与第j行元素对应相加，并把结果放到第j行中去；

进程pro向进程0发送第j行元素；

}

2.算法并行程序的编写

2.1 Warshall算法并行编程模型选择

2.1.1 .并行编程模型的种类

在并行程序设计环境中，为便于程序员进行并行程序设计，完成并行应用计算任务，一般提供了两种基本的并行程序设计模型，即Master/Slave模型（MPMD）和SPMD模型。

所谓MPMD模型：程序是由运行于Host上的程序和运行于计算节点Node上的若干个程序组成的。简单地说就是指用户进行并行程序设计时，需要运行两部分程序代码，其中Host部分代码用于在Host机上运行，它通过基本的消息传递通信函数完成与并行处理机结点Node上运行的代码之间的数据传输。

所谓SPMD模型：一个程序同时启动多份，形成多个独立的进程，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调用MPI函数来实现；每个进程开始执行时，将获得一个唯一的序号（rank）。这种模型只包含一个程序，它既可运行于主机上又可运行于节点上。

2.1.2 . Warshall算法并行编程模型选择

对于Warshall算法，采用SPMD编程模型比较适合。因为前两个for语句具有很强的操作相关性,不适合采用并行计算，所以，首先由0进程负责实现前两个for语句，再通过基本的消息传递通信函数，完成与其他并行处理机结点上的数据传输。而第三个for语句适合采用并行计算，每个进程负责一行a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);（k=0,1,……n-1）处理，每个进程上处理得到的结果采用基本的消息传递通信函数发给0进程，完成所有工作后，由0进程负责输出传递闭包矩阵结果。

2.2 Warshall算法的MPI程序编写

下面是Warshall算法基于SPMD编程模式的MPI并行程序如下：

#include <stdio.h>

#include <mpi.h>

#define  N  6 

void main(int argc,char* argv[])

{

int a[N][N];

int i,j,k ,group_size,my_rank;

MPI_Status status;

  MPI_Init(&argc,&argv);

  MPI_Comm_rank( MPI_COMM_WORLD, &my_rank);

  MPI_Comm_size( MPI_COMM_WORLD, &group_size);

if (my_rank== 0)

{printf("Please you input the initial matrix:/n");

for(i=0;i<N；i++)

         {for(j=0；j<N；j++)

          scanf("%d4",&a[i][j]);

printf("/n");

}

for (i=0；i<N；i++) 

    for (j=0；j<N；j++)

{if(j>group_size) pro=j MOD group_size;

else pro=j;

MPI_Send(i, 1, MPI_INT, pro, 1, MPI_COMM_WORLD, &status );

MPI_Send(j, 1, MPI_INT, pro, 2, MPI_COMM_WORLD, &status );

MPI_Send(&a[i,0], N, MPI_INT, pro, 3, MPI_COMM_WORLD, &status );

MPI_Send(&a[j,0], N, MPI_INT, pro, 4, MPI_COMM_WORLD, &status );

MPI_Recv(&a[j,0], N, MPI_INT, pro, 5, MPI_COMM_WORLD, &status );

}

}   

else {  MPI_Recv(i, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status );

      MPI_Recv(j, 1, MPI_INT, 0, 2, MPI_COMM_WORLD, &status );

      MPI_Recv(&a[i,0], N, MPI_INT, 0, 3, MPI_COMM_WORLD, &status );

      MPI_Recv(&a[j,0], N, MPI_INT, 0, 4, MPI_COMM_WORLD, &status );

      for(k=0;k<N;k++){     a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);   }

MPI_Send(&a[j,0], N, MPI_INT, 0, 5, MPI_COMM_WORLD );

} 

if(my_rank==0)

{printf("The transitive closure of the matrix is:/n");

for (i=0;i<N,i++)

         {for(j=0；j<N；j++)

          printf("%d4",a[i][j]);

          printf("/n");

}

}

 MPI_Finalize();

}

3.并行程序在SGI300上的实现

3.1 Warshall算法程在MPI上的编译、调试及运行

l         利用vi编译器编译程序，编写Warshall算法的并行程序

u       格式为： vi  warshall.c

u       然后利用命令  ：wq  进行保存

l         因为用户设置了正确的MPI系统命令的执行路径，就可以直接地使用命令行方式mpicc来编译C程序，编译方式与cc完全一致。

l         格式为：  SGI300%  cc   -c  warshall  warshall.c  /usr/lib32/libmpi.so

l         其中若出现错误信息，则可用命令vi warshall.c，也即在vi编辑器中对原程序进行修改。

l         利用命令mpirun warshall 进行运行，下面是整个测试及运行过程：

SGI300%  cc -c warshall  warshall.c   /usr/lib32/libmpi.so

SGI300%  mpirun –np 4 warshall

Please you input the initial matrix:

1   0   1    0   0   1

1   1   0    0   0   0

0   1   1    0   0   0

0   0   1    1   1   0

0   0   0    0   1   1

0   0   0    0   1   1

The transitive closure of the matrix is:

 1   1   1   0   1   1

 1   1   1   0   1   1

 1   1   1   0   1   1

 1   1   1   1   1   1

 0   0   0   0   1   1

 0   0   0   0   1   1

SGI300%  exit   

4.Warshall算法程序的优化

通过对并行程序的调试及运行，应该尽量避免过于频繁的消息传递，特别是当所需处理的N值很大时尤为重要。为了避免处理器的负载失衡，本文通过MPI所提供的库函数对并行程序的核心算法进行优化，优化程序结果如下：

for(i=0,i<N,i++) 

    for(j=0；j<N；j++)

{

MPI_Scatter(&a[i,0],1,MPI_INT,&buf[0],1,MPI_INT,0, MPI_COMM_WORLD);

MPI_Scatter(&a[j,0],1,MPI_INT,&buf[1],1,MPI_INT,0, MPI_COMM_WORLD);

MPI_Gather(&buf[0],1, MPI_INT,&a[j,0], 1, MPI_INT,0,MPI_COMM_WORLD)

}

MPI_Bcast(&buf[0],1,MPI_INT,0,MPI_COMM_WORLD);

while(TRUE)

{if(接收到的消息是FINISHED)break;

else{做buf[0]=buf[0]+buf[1]处理;} 

}

其余的地方随数据量的增加对性能的影响不明显在此不做优化。

参 考 文 献

l         MPI Homepage：http://www-unix.mcs.anl.gov/mpi/

l         SGI Homepage  http://www.sgi.com/

l         Lu__s Mourae Silvay and Rajkumar Buyyaz     Parallel Programming Models and Paradigms     School of Computer Science and Software Engineering Monash University

l         Marc Snir   Steve Otto  Steven Huss-Lederman   David Walker Jack  Dongarra   MPI: The Complete Reference  The MIT Press Cambridge , Massachusetts  

London , England

l         都志辉, 《高性能计算之并行编程技术—— MPI并行程序设计》

l         沈志宇，廖湘科，胡子昂。《并行程序设计》，国防科技大学出版社