C、OpenMP：どのようにしてこのトリプルループの並列化を改善できますか？

Question

私は（基本的にはその場で2次元配列を編集）のOpenMPを使用してFloyd-Warshallアルゴリズムを並列化しようとしているが、私は、私はここに、最善の方法でそれについてつもりだことを疑うが、私がこれまで持っているものです。

#pragma omp parallel for private(i, j, k) shared(g) 
    for (i = 0; i < n; i++) { 
     for (j = 0; j < n; j++) { 
      for (k = 0; k < n; k++) { 
       g->A[j][k] = imin(g->A[j][k], g->A[j][i] + g->A[i][k]); 
      } 
     } 
    } 

私はより良いのOpenMPを利用することができますどのように任意のアイデア？ランタイムの半分になった瞬間、確かにそれを改善することができます。

また、並列化のために使用される他の技術のための任意の提案として誰場合、私はすべての耳です。私はMPIについて考えましたが、私は全部main関数を並列にする必要がありますか？

ありがとうございました。

EDIT

上記のコードは動作しません、以下の答えは、なぜ表示されます。

Answer 1

アルゴリズムを並列化することは簡単ではありません。これを並列実行する方法については、 http://www.mcs.anl.gov/~itf/dbpp/text/node35.htmlの注記を参照してください。少数のプロセッサー（デュアル、クワッド、オクタコアのマシン）をお持ちの場合は、Parallel Floyd 1がおそらくあなたに適しています。膨大な数のプロセッサ（本当に素晴らしいGPU、メッシュコンピュータ）をお持ちの場合は、Parallel Floyd 2のほうが良いかもしれません。