9

シーケンシャル コードは次のとおりです。

do i = 1, n
   do j = i+1, n
      if ("some_condition(i,j)") then
         result = "here's result"
         return
      end if
   end do
end do

次以外に、外側のループの反復を同時に実行するためのよりクリーンな方法はありますか?

  !$OMP PARALLEL private(i,j)
  !$OMP DO 
  do i = 1, n     
     !$OMP FLUSH(found)
     if (found) goto 10
     do j = i+1, n        
        if ("some_condition(i,j)") then
           !$OMP CRITICAL
           !$OMP FLUSH(found)
           if (.not.found) then           
              found = .true.
              result = "here's result"
           end if
           !$OMP FLUSH(found)
           !$OMP END CRITICAL
           goto 10
        end if
     end do
10   continue
  end do
  !$OMP END DO NOWAIT
  !$OMP END PARALLEL

-loopでの反復の順序は、いくつかiが見つかる限り、任意である可能性があります ( を満たす限り、実行ごとに変更されても問題ありません)。 result"some_condition"

4

3 に答える 3

1

$OMP DOループから抜け出すことは許可されていないようです。別の方法として、手動で実装することもできます。

処理するインデックスの固定された連続範囲を各スレッドに与える

OpenMPのガイド: C++ の簡単なマルチスレッド プログラミング:

  results = "invalid_value"

  !$OMP PARALLEL private(i,j,thread_num,num_threads,start,end)

  thread_num = OMP_GET_THREAD_NUM()
  num_threads = OMP_GET_NUM_THREADS()
  start = thread_num * n / num_threads + 1
  end = (thread_num + 1) * n / num_threads

  outer: do i = start, end
     !$OMP FLUSH(found)             
     if (found) exit outer
     do j = i+1, n
        if ("some_condition") then
           found = .true.
           !$OMP FLUSH(found)
           results(thread_num+1) = "here's result"
           exit outer
        end if
     end do
  end do outer

  !$OMP END PARALLEL

  ! extract `result` from `results` if any
  do i = 1, size(results)
     if (results(i).ne."invalid_value") result = results(i)
  end do

UPDATE : に置き換えgotoられ、 @MSB の回答に基づいて配列exitが導入されました。results

解決策が存在する場合、このアプローチはより$OMP DO早く終了します。

各スレッドに一度に 1 回の繰り返しを与えて処理します

task ディレクティブの使用 ( @High Performance Markで推奨):

  !$OMP PARALLEL
  !$OMP SINGLE
  !$OMP TASK UNTIED
          ! "untied" allows other threads to generate tasks
  do i = 1, n ! i is private
     !$OMP TASK ! implied "flush"
     task:     do j = i+1, n ! i is firstprivate, j is private       
        if (found) exit task
        if ("some_condition(i,j)") then
           !$OMP CRITICAL
           result = "here's result" ! result is shared              
           found = .true.           ! found is shared
           !$OMP END CRITICAL ! implied "flush"
           exit task
        end if
     end do task
     !$OMP END TASK 
  end do 
  !$OMP END TASK
  !$OMP END SINGLE
  !$OMP END PARALLEL

outerこのバリアントは、私のテストでは、 -loopを使用したバージョンよりも 2 倍高速です。

于 2010-06-05T09:59:16.100 に答える
1

完全に別のアプローチは、OpenMP 3.0 の一部である TASK コンストラクトを使用することです。あなたがしようとしているように見えるのは、ループをスレッド間で分割し、いずれかのスレッドが答えを見つけるまで計算してから、すべてのスレッドを停止させることです。問題は、すべてのスレッドに共有フラグをチェックさせる必要性は、(a) パフォーマンスを低下させ、(b) BREAKS と CYCLES で醜いループに導くことです。

@MSBの回答は、既存のアプローチをどのように適応させるかについて非常に良いアドバイスを与えると思います. しかし、問題に取り組むより自然な方法は、プログラムが多数のタスク (おそらく最も内側のループの反復ごとに 1 つ) を作成し、それらをワーカー スレッドにディスパッチすることです。いずれかのスレッドが成功を報告すると、すべてのスレッドにファイナライズ タスクを送信でき、プログラムを続行できます。

もちろん、これにはプログラムをさらに書き直す必要があり、おそらく順次実行が悪化します。OpenMP の実装が標準の v3.0 をサポートしている必要があります。

また、この分野では、私が管理できる以上の支援が必要な場合があります。私は OpenMP TASKS を自分で使い始めたばかりです。

于 2010-06-06T09:14:41.080 に答える
1

順次コードには、並列化に適さない依存関係があるようです。「何らかの条件」を真にする i & j の値が複数あるとします。i & j do ループの実行順序によって、これらの条件のどれが最初に見つかったかが決まり、result の値が設定され、その後で戻り値が設定されます。ステートメントは、「何らかの条件」が真である追加のケース i,j の検索を終了します。シーケンシャル コードでは、do ループは常に同じ順序で実行されるため、プログラムの動作は決定論的であり、「何らかの条件」を真にする i & j の同一の値が常に検出されます。並行バージョンでは、さまざまなループ i が非決定論的な順序で実行されるため、実行ごとに異なる i の値が真の "

おそらく、プログラマーとして、真の「何らかの条件」をもたらす i & j の値は 1 つしかないことをご存知でしょうか? その場合、実行を短絡しても問題ないように見えます。しかし、OpenMP 仕様では、「DO ステートメント以外の関連付けられたループ内のステートメントは、ループからの分岐を引き起こすことはありません」と述べているため、内部ループ内の何かによって出力ループが中止されることは許可されていません。真の「何らかの条件」が常に 1 つしかない場合は、「リターン」を削除して、その 1 つのケースが見つかった後にスレッドに「何らかの条件」が真であることを確認させることで、CPU 時間を浪費することができます。それでもシーケンシャル プログラムよりも高速である可能性があります。スケーラーの「結果」変数を使用すると、実行順序に依存するため、おそらく非準拠です。結果を合計する「リダクション」に変更するか、次元 (n) の 1-D 配列として結果を返すことができます。「何らかの条件」が真である i の最小値を見つける必要がある場合は、Fortran 組み込み関数 minloc を使用して配列結果から取得できます。

多くの「flush」および「critical」ディレクティブを含むソリューションは、シーケンシャル バージョンよりも高速ではない場合があります。

更新: 複数の結果が可能であり、いずれかが実行されるという明確化に基づいて、1 つの並列メソッドは、複数の結果を返し、順次コードに 1 つを選択させることです。つまり、「結果」をスケーラーではなく 1D 配列にします。内側の j ループは「omp do」ディレクティブと「関連付け」られていないため、短絡することができます。そのため、「結果」は、i の範囲に従って次元化された 1D であるだけで済みます。だから、このようなもの：

program test1

integer :: i, j
integer, parameter :: n = 10
integer, dimension (n) :: result

result = -999

!omp parallel default (shared) private (i, j)
!omp do
do i = 1, n
   inner: do j = i+1, n
      if ( mod (i+j,14) == 0 ) then
         result (i) = i
         exit inner
      end if
   end do inner
end do
!omp end do
!omp end parallel

write (*, *) 'All results'
write (*, *) result

write (*, *)
write (*, *) 'One result'
write (*, *) result ( maxloc (result, 1) )

end program test1
于 2010-06-05T17:09:40.987 に答える