基于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         沈志宇，廖湘科，胡子昂。《并行程式設計》，國防科技大學出版社