MPIパラレルプログラミングシリーズの5:図の単一ソース最短パスアルゴリズム
17763 ワード
図の単一ソース最短パス問題とは、指定された頂点sから他のすべての頂点iまでの最短距離を求めることである.一点から他の頂点までの距離であるため、単源と呼ぶ.本論文ではdijkstraアルゴリズム:経路長の増加順の最短経路アルゴリズムを紹介し,このアルゴリズムMPI並列化アルゴリズムを与えた.
一、アルゴリズム思想
このアルゴリズムの考え方は、各成分D[i]がソース頂点vから他の頂点v[i]までの経路長である補助ベクトルDを導入することである.初期状態:vからviへの経路がある場合、D[i]は円弧[v,vi]の重み値である.そうでなければD[i]は無限大である.明らかに
D[j] = min{D[i]}
頂点vから他の頂点までの最短経路の長さであり、その経路は(v,vj)である.
では、次の最短パスの長さはどのように計算されますか?実は簡単です.次の最短パスの長さは、ソース頂点vがある頂点vkに直接到達する長さ、すなわち{v,vk}です.ソース頂点vが頂点vjを通ってある頂点までの長さ、すなわち{v,vj,vk}であるかのいずれかである.
Sが最短経路を求めた頂点の集合であると仮定すると,次の最短経路(その終点をxとする)は,円弧{v,vx}であるか,中間がS中の頂点のみを通過して最後に終点Xに到達する経路である.
一般的に、次の最短パスの長さは次のとおりです.
D[j]=min{D[i]|viはV-S}に属する
ここで、Vは図頂点の集合であり、D[i]は円弧{v,vi}の重み値、またはD[k]と円弧{vk,vi}の重み値の和である.
二、アルゴリズムの説明
以上の考えによれば、アルゴリズムの説明は以下の通りである.
入力:図Gの隣接行列m[0...n-1][0...n-1]、ソース頂点v
出力:最短パス値ベクトルD[0...n-1]、最短パス行列p[0...n-1][0...n-2].ここで、D[i]はソース頂点vから頂点viまでの最短経路長であり、ベクトルp[i]はソース頂点vから頂点viまでの最短経路である
1)初期化D[i]
D[i]=m[v][vi]==無限大?無限大:m[v][vi]
2)現在の最短パス値の計算
min = min{D[i]}
final[i]=1//タグ頂点i最短パス取得済み
3)最短パス値および最短パスの更新
for(i = 0; i < n; i++)
if(!final[i])
if(D[i] > min + m[vk][vi])
D[i] = min + m[vk][vi];
end if
endif
for( j = 0; j < n-1 ; j++)
if(p[vk][j]!=無限大)
p[vi][j] = p[vk][j];
end if
end for
p[vi][j] = vi
end for
4)最短パスと最短パス値の出力
三、アルゴリズム実現
ここではアルゴリズムのコアコードのみを示します.以下のようにします.
四、並列アルゴリズムの説明
このアルゴリズムを並列化解析し,ベクトルD(アルゴリズムの第1ステップに対応)を初期化し,最短パス値と最短パス(アルゴリズムの第3ステップに対応)を更新することは,現在の最短パスと最短パス値があれば,各頂点の最短パスのアルゴリズムが互いに独立しているため,並列化可能であることが明らかになった.本並列化アルゴリズムでは,現在の最短経路と最短経路値をどのように求めるかが鍵となる.
私たちは全部でP個のプロセスを使うと仮定して、図の右のn個の頂点、私達は各プロセスにn/p個の頂点を担当させて、各プロセスはすべて自分のベクトルDと最短の経路pがあって、私達はどのように現在の最短の経路の長さと最短の経路を求めますか?まず、各プロセスの現在の最短パスを計算し、ローカル最短パスをプロセス0に送信し、プロセス0はこれらのプロセスの最短パスを比較し、現在のグローバル最短パスを取得し、この結果をすべてのプロセスにブロードキャストすることができる.
アルゴリズムの説明は次のとおりです.
合計pプロセスがあると仮定します
入力:図Gの隣接行列m[0...n-1][0...n-1]、ソース頂点v
出力:最短パス値ベクトルD[0...n-1]、最短パス行列p[0...n-1][0...n-2].
1)プロセス0は隣接行列mとソースノードvを読み出し,m,vを他のすべてのプロセスにブロードキャストする.
2)各プロセスは、それぞれのローカルDとPを並列に初期化する
3)最短経路を求める
1)各プロセスは、それぞれのローカル最短パス値を並列に計算し、0番プロセスに送信する
2)0番プロセスは、グローバル最短パス値と対応するプロセス番号を求め、他のすべてのプロセスにブロードキャストします.
3)グローバル最短パス値を持つプロセスは、対応する最短パスを他のプロセスにブロードキャストする(各プロセスの最短パスを更新する)
4)各プロセスは,新たにそれぞれのDとPを並列に行う.
五、並列アルゴリズム実現
ここでは、アルゴリズムの3番目のステップの具体的な実装のみを示します.
六、MPI関数説明
本並列アルゴリズムで用いられるMPI関数は主に点対点通信関数MPI_SendとMPI_Recv,グローバル通信関数MPI_Bcast.MPIの名前は本当に良くて、メッセージングのプログラミング、私はMPIアルゴリズムの核心がタスクの区分とタスク間の通信だと思います.
次は、図の最下生成ツリーとその並列アルゴリズムについて説明します.
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
一、アルゴリズム思想
このアルゴリズムの考え方は、各成分D[i]がソース頂点vから他の頂点v[i]までの経路長である補助ベクトルDを導入することである.初期状態:vからviへの経路がある場合、D[i]は円弧[v,vi]の重み値である.そうでなければD[i]は無限大である.明らかに
D[j] = min{D[i]}
頂点vから他の頂点までの最短経路の長さであり、その経路は(v,vj)である.
では、次の最短パスの長さはどのように計算されますか?実は簡単です.次の最短パスの長さは、ソース頂点vがある頂点vkに直接到達する長さ、すなわち{v,vk}です.ソース頂点vが頂点vjを通ってある頂点までの長さ、すなわち{v,vj,vk}であるかのいずれかである.
Sが最短経路を求めた頂点の集合であると仮定すると,次の最短経路(その終点をxとする)は,円弧{v,vx}であるか,中間がS中の頂点のみを通過して最後に終点Xに到達する経路である.
一般的に、次の最短パスの長さは次のとおりです.
D[j]=min{D[i]|viはV-S}に属する
ここで、Vは図頂点の集合であり、D[i]は円弧{v,vi}の重み値、またはD[k]と円弧{vk,vi}の重み値の和である.
二、アルゴリズムの説明
以上の考えによれば、アルゴリズムの説明は以下の通りである.
入力:図Gの隣接行列m[0...n-1][0...n-1]、ソース頂点v
出力:最短パス値ベクトルD[0...n-1]、最短パス行列p[0...n-1][0...n-2].ここで、D[i]はソース頂点vから頂点viまでの最短経路長であり、ベクトルp[i]はソース頂点vから頂点viまでの最短経路である
1)初期化D[i]
D[i]=m[v][vi]==無限大?無限大:m[v][vi]
2)現在の最短パス値の計算
min = min{D[i]}
final[i]=1//タグ頂点i最短パス取得済み
3)最短パス値および最短パスの更新
for(i = 0; i < n; i++)
if(!final[i])
if(D[i] > min + m[vk][vi])
D[i] = min + m[vk][vi];
end if
endif
for( j = 0; j < n-1 ; j++)
if(p[vk][j]!=無限大)
p[vi][j] = p[vk][j];
end if
end for
p[vi][j] = vi
end for
4)最短パスと最短パス値の出力
三、アルゴリズム実現
ここではアルゴリズムのコアコードのみを示します.以下のようにします.
1: void short_path_function( 2: int **matrix, 3: int vertex_num, 4: int vertex_source){ 5: 6: int *short_path_value; 7: int *final; 8: 9: int *short_path_storage; 10: int **short_path; 11: 12: int min; 13: int vertex; 14: 15: int i,j,k; 16: 17: // 18: short_path_value = my_malloc(sizeof(int) * vertex_num); 19: final = my_malloc(sizeof(int) * vertex_num); 20: dynamic_allocate_matrix((void *)&short_path, (void *)&short_path_storage, vertex_num, 21: vertex_num-1, sizeof(int)); 22: 23: // 24: for(i = 0; i < vertex_num; i++){ 25: final[i] = 0; 26: short_path_value[i] = matrix[vertex_source][i]; 27: 28: // 29: for(j = 0; j < vertex_num-1; j++) 30: short_path[i][j] = -1; 31: 32: // 33: if(short_path_value[i] < MAX_VAULE) 34: short_path[i][0] = i; 35: } 36: 37: final[vertex_source] = 1; 38: for(i = 1; i < vertex_num; i++){ 39: // 40: min =MAX_VAULE ; 41: for(j = 0; j < vertex_num; j++) 42: if(!final[j]) 43: if(short_path_value[j] < min){ 44: min = short_path_value[j]; 45: vertex = j; 46: } 47: 48: final[vertex] = 1; 49: 50: // 51: for(j = 0; j < vertex_num; j++){ 52: if(!final[j]) 53: if(min + matrix[vertex][j] < short_path_value[j]){ 54: // 55: short_path_value[j] = min + matrix[vertex][j]; 56: 57: // 58: k = 0; 59: while(short_path[vertex][k] != -1){ 60: short_path[j][k] = short_path[vertex][k]; 61: k++; 62: } 63: 64: short_path[j][k] = j; 65: } 66: } 67: } 68: 69: // 70: array_int_print(vertex_num, short_path_value); 71: print_int_matrix(short_path, vertex_num-1, vertex_num); 72: } 四、並列アルゴリズムの説明
このアルゴリズムを並列化解析し,ベクトルD(アルゴリズムの第1ステップに対応)を初期化し,最短パス値と最短パス(アルゴリズムの第3ステップに対応)を更新することは,現在の最短パスと最短パス値があれば,各頂点の最短パスのアルゴリズムが互いに独立しているため,並列化可能であることが明らかになった.本並列化アルゴリズムでは,現在の最短経路と最短経路値をどのように求めるかが鍵となる.
私たちは全部でP個のプロセスを使うと仮定して、図の右のn個の頂点、私達は各プロセスにn/p個の頂点を担当させて、各プロセスはすべて自分のベクトルDと最短の経路pがあって、私達はどのように現在の最短の経路の長さと最短の経路を求めますか?まず、各プロセスの現在の最短パスを計算し、ローカル最短パスをプロセス0に送信し、プロセス0はこれらのプロセスの最短パスを比較し、現在のグローバル最短パスを取得し、この結果をすべてのプロセスにブロードキャストすることができる.
アルゴリズムの説明は次のとおりです.
合計pプロセスがあると仮定します
入力:図Gの隣接行列m[0...n-1][0...n-1]、ソース頂点v
出力:最短パス値ベクトルD[0...n-1]、最短パス行列p[0...n-1][0...n-2].
1)プロセス0は隣接行列mとソースノードvを読み出し,m,vを他のすべてのプロセスにブロードキャストする.
2)各プロセスは、それぞれのローカルDとPを並列に初期化する
3)最短経路を求める
1)各プロセスは、それぞれのローカル最短パス値を並列に計算し、0番プロセスに送信する
2)0番プロセスは、グローバル最短パス値と対応するプロセス番号を求め、他のすべてのプロセスにブロードキャストします.
3)グローバル最短パス値を持つプロセスは、対応する最短パスを他のプロセスにブロードキャストする(各プロセスの最短パスを更新する)
4)各プロセスは,新たにそれぞれのDとPを並列に行う.
五、並列アルゴリズム実現
ここでは、アルゴリズムの3番目のステップの具体的な実装のみを示します.
1: int get_short_path_value( 2: int *final, 3: int *vertex, 4: int **short_path, 5: int *short_path_value, 6: int *short_path_copy, 7: int *shortest, 8: int vertex_num, 9: int local_vertex_num, 10: int process_id, 11: int process_size, 12: MPI_Comm comm){ 13: 14: int min; 15: int local_vertex; 16: 17: int shortest_process_id; 18: 19: MPI_Status status; 20: 21: int j; 22: 23: // 24: min = MAX_VAULE; 25: for(j = 0; j < local_vertex_num; j++) 26: if(!final[j]) 27: if(short_path_value[j] < min){ 28: min = short_path_value[j]; 29: local_vertex = j; 30: } 31: 32: // 0 33: if(process_id) 34: MPI_Send(&min, 1, MPI_INT, 0, DATA_MESSAGE, comm); 35: else{ 36: //0 37: shortest[0] = min; 38: for(j = 1; j < process_size; j++) 39: MPI_Recv(shortest+j, 1, MPI_INT, j, DATA_MESSAGE, comm, &status); 40: 41: //0 ， 42: min = shortest[0]; 43: shortest_process_id = 0; 44: for(j = 1; j < process_size; j++) 45: if(shortest[j] < min){ 46: min = shortest[j]; 47: shortest_process_id = j; 48: } 49: } 50: //0 , ， 51: MPI_Bcast(&min, 1, MPI_INT, 0, comm); 52: if(min == MAX_VAULE) 53: return min; 54: 55: //0 56: MPI_Bcast(&shortest_process_id, 1, MPI_INT, 0, comm); 57: 58: // ， 1， 59: if(process_id == shortest_process_id){ 60: final[local_vertex] = 1; 61: *vertex = BLOCK_LOW(shortest_process_id, process_size, vertex_num) + local_vertex; 62: 63: // 64: for(j = 0; j < vertex_num -1; j++) 65: short_path_copy[j] = short_path[local_vertex][j]; 66: } 67: 68: // 69: MPI_Bcast(short_path_copy, vertex_num-1, MPI_INT, shortest_process_id,comm); 70: MPI_Bcast(vertex, 1, MPI_INT, shortest_process_id, comm); 71: 72: return min; 73: } 六、MPI関数説明
本並列アルゴリズムで用いられるMPI関数は主に点対点通信関数MPI_SendとMPI_Recv,グローバル通信関数MPI_Bcast.MPIの名前は本当に良くて、メッセージングのプログラミング、私はMPIアルゴリズムの核心がタスクの区分とタスク間の通信だと思います.
次は、図の最下生成ツリーとその並列アルゴリズムについて説明します.
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }