バリア（コンピュータサイエンス）

並列計算において、バリアは同期方式の一種です。[1]ソースコード内のスレッドまたはプロセスのグループにバリアを設定すると、その時点で任意のスレッド/プロセスが停止し、他のすべてのスレッド/プロセスがこのバリアに到達するまで処理を続行できなくなります。[2]

多くの集合ルーチンやディレクティブベースの並列言語は、暗黙的なバリアを課します。例えば、OpenMPを使用したFortranの並列doループは、最後の反復が完了するまで、どのスレッドでも実行を継続できません。[要出典]これは、プログラムがループの完了直後の結果に依存する場合です。メッセージパッシングでは、グローバル通信（リダクションやスキャッターなど）は、暗黙的にバリアを課す可能性があります。

並行コンピューティングにおいて、バリアは上昇状態または下降状態のいずれかになります。ラッチという用語は、上昇状態で開始し、一度下降状態になると再び上昇できないバリアを指すために使用されることがあります。カウントダウンラッチという用語は、所定の数のスレッド/プロセスが到着すると自動的に下降するラッチを指すために使用されることがあります。

実装

スレッドバリアと呼ばれるスレッドの例を見てみましょう。スレッドバリアには、バリアに入ったスレッドの総数を追跡するための変数が必要です。[3]十分な数のスレッドがバリアに入ると、バリアは解除されます。スレッドバリアを実装する際には、ミューテックスのような同期プリミティブも必要です。

このスレッド バリア方式は、バリアが解除される前に、予想される数のスレッドがバリアに到達するまで、スレッドが「中央バリア」の前で待機する必要があるため、集中バリアとも呼ばれます。

POSIXスレッドを使用してスレッドバリアを実装した次のCコードは、この手順を示しています。[1]

#include <stdio.h> #include <pthread.h> #TOTAL_THREADS 2 を定義する#THREAD_BARRIERS_NUMBER 3 を定義する#define PTHREAD_BARRIER_ATTR NULL // pthreadバリア属性typedef struct _thread_barrier  { intスレッドバリア番号;  pthread_mutex_tロック;  整数合計スレッド; }スレッドバリア; thread_barrierバリア; void thread_barrier_init ( thread_barrier *バリア、pthread_mutexattr_t * mutex_attr 、int thread_barrier_number ){       pthread_mutex_init ( & (バリア->ロック), mutex_attr );  バリア->スレッドバリア番号=スレッドバリア番号;   barrier -> total_thread = 0 ; // スレッド合計を0に初期化する  }void thread_barrier_wait ( thread_barrier *バリア){   if ( ! pthread_mutex_lock ( & (バリア->ロック))){ バリア-> total_thread += 1 ;   pthread_mutex_unlock ( & (バリア->ロック)); } while (バリア-> total_thread <バリア-> thread_barrier_number );    if ( ! pthread_mutex_lock ( & (バリア->ロック))){ barrier -> total_thread -= 1 ; // スレッドバリアを通過したのでスレッドを1つ減らす    pthread_mutex_unlock ( & (バリア->ロック)); }}void thread_barrier_destroy ( thread_barrier *バリア){   pthread_mutex_destroy ( & (バリア->ロック));}void * thread_func ( void * ptr ){   printf ( "スレッド ID %ld は、実行中のスレッド数が十分でないため、バリアーで待機しています... \n " 、pthread_self ()、THREAD_BARRIERS_NUMBER );   thread_barrier_wait ( &バリア); printf ( "バリアが解除され、スレッドID %ldが現在実行中です\n " , pthread_self ()); }intメイン() { pthread_tスレッドID [合計スレッド数];  thread_barrier_init ( &バリア, PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );   ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );    } // pthread_join() は指定されたすべてのスレッドが終了するまでプロセスをブロックするため、 // バリアで待機するのに十分なスレッドがないため、このプロセスはブロックされます ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_join (スレッドID [ i ], NULL );  } thread_barrier_destroy ( &バリア); printf ( "スレッドバリアが解除されました\n " ); // この行はTOTAL_THREADS < THREAD_BARRIERS_NUMBERなので呼び出されません }

このプログラムでは、スレッド バリアは構造体struct _thread_barrier として定義されており、次のものが含まれます。

  • total_thread:プロセス内のスレッドの合計数
  • thread_barrier_number : スレッドバリアを解除するために、そのバリアに入ると予想されるスレッドの総数
  • lock : POSIXスレッドミューテックスロック

バリアの定義に基づいて、バリアを有効にするためにプログラム内のスレッドの合計数を「監視」するthread_barrier_wait()のような関数をこのプログラムに実装する必要があります。

このプログラムでは、 thread_barrier_wait()の呼び出しは、THREAD_BARRIERS_NUMBER 個のスレッドがスレッドバリアに到達するまでブロックされます。このプログラムの結果は次のようになります。

スレッド ID <thread_id、例: 139997337872128> は、実行中のスレッドが 3 つ足りないため、バリアで待機しています...スレッド ID <thread_id、例: 139997329479424> は、実行中のスレッドが 3 つ足りないため、バリアで待機しています... // (メイン プロセスは、スレッドが 3 つ足りないためブロックされています) // 行 printf("Thread barrier is lifted\n") には到達しません

プログラムからわかるように、生成されるスレッドは2つだけです。これら2つのスレッドはどちらもスレッド関数ハンドラとして を持ち、 を呼び出します。一方、スレッドバリアは解除されるために 3つのスレッドが( )を呼び出すことを想定しています。thread_func()thread_barrier_wait(&barrier)thread_barrier_waitTHREAD_BARRIERS_NUMBER = 3

TOTAL_THREADS を 3 に変更すると、スレッド バリアが解除されます。

スレッド ID <スレッド ID、例: 140453108946688> は、実行中のスレッドが 3 つでは足りないため、バリアで待機しています... スレッド ID <スレッド ID、例: 140453117339392> は、実行中のスレッドが 3 つでは足りないため、バリアで待機しています...スレッド ID <スレッド ID、例: 140453100553984> は、実行中のスレッドが 3 つでは足りないため、バリアで待機しています...バリアが解除され、スレッド ID <スレッド ID、例: 140453108946688> が現在実行中ですバリアが解除され、スレッド ID <スレッド ID、例: 140453117339392> が現在実行中ですバリアが解除され、スレッド ID <スレッド ID、例: 140453100553984> が現在実行中ですスレッド バリアが解除されました

感覚反転集中障壁

スレッドバリアを通過するスレッドごとにスレッドの総数を1つ減らすだけでなく、スレッドバリアは、各スレッドの状態を通過中または停止中としてマークするために反対の値を使用できます。 [4]たとえば、状態値が0のスレッド1はバリアで停止中であることを意味し、状態値が1のスレッド2はバリアを通過したことを意味し、状態値が0のスレッド3はバリアで停止中であることを意味します。[5]これはセンスリバーサルとして知られています。 [1]

次のCコードはこれを実証しています: [3] [6]

#include <stdio.h> #include <stdbool.h> #include <pthread.h> #TOTAL_THREADS 2 を定義する#THREAD_BARRIERS_NUMBER 3 を定義する#define PTHREAD_BARRIER_ATTR NULL // pthreadバリア属性typedef struct _thread_barrier  { intスレッドバリア番号;  整数合計スレッド;  pthread_mutex_tロック;  boolフラグ; }スレッドバリア; thread_barrierバリア; void thread_barrier_init ( thread_barrier *バリア、pthread_mutexattr_t * mutex_attr 、int thread_barrier_number ){       pthread_mutex_init ( & (バリア->ロック), mutex_attr );  バリア-> total_thread = 0 ;   バリア->スレッドバリア番号=スレッドバリア番号;   バリア->フラグ= false ;  }void thread_barrier_wait ( thread_barrier *バリア){   bool local_sense =バリア->フラグ;    if ( ! pthread_mutex_lock ( & (バリア->ロック))){ バリア-> total_thread += 1 ;   ローカルセンス= !ローカルセンス;    if (バリア->合計スレッド数==バリア->スレッドバリア数){    バリア-> total_thread = 0 ;   バリア-> flag = local_sense ;   pthread_mutex_unlock ( & (バリア->ロック)); }それ以外{   pthread_mutex_unlock ( & (バリア->ロック)); while ( barrier -> flag != local_sense ); // フラグを待つ     } }}void thread_barrier_destroy ( thread_barrier *バリア){   pthread_mutex_destroy ( & (バリア->ロック));}void * thread_func ( void * ptr ){   printf ( "スレッド ID %ld は、実行中のスレッド数が十分でないため、バリアーで待機しています... \n " 、pthread_self ()、THREAD_BARRIERS_NUMBER );   thread_barrier_wait ( &バリア); printf ( "バリアが解除され、スレッドID %ldが現在実行中です\n " , pthread_self ()); }intメイン() { pthread_tスレッドID [合計スレッド数];  thread_barrier_init ( &バリア, PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );   ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );    } // pthread_join() は指定されたすべてのスレッドが終了するまでプロセスをブロックするため、 // バリアで待機するのに十分なスレッドがないため、このプロセスはブロックされます ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_join (スレッドID [ i ], NULL );  } thread_barrier_destroy ( &バリア); printf ( "スレッドバリアが解除されました\n " ); // この行はTOTAL_THREADS < THREAD_BARRIERS_NUMBERなので呼び出されません }

このプログラムは、以前のCentralized Barrierのソースコードとすべての機能を備えています。ただし、2つの新しい変数を使用するという点で実装方法が異なります。[1]

  • local_sense : THREAD_BARRIERS_NUMBER がバリアに到達したかどうかを確認するスレッド ローカル ブール変数。
  • flag :構造体_thread_barrierのブール値メンバー。THREAD_BARRIERS_NUMBERがバリアに到達したかどうかを示す。

スレッドがバリアで停止すると、local_senseの値が切り替わります。[1]スレッドバリアで停止するスレッドがTHREAD_BARRIERS_NUMBER個未満の場合、それらのスレッドはstruct _thread_barrierのフラグメンバーがプライベート変数と等しくないという条件で待機を続けます。local_sense

スレッド バリアで停止するスレッドがちょうどTHREAD_BARRIERS_NUMBER 個ある場合、合計スレッド数は 0 にリセットされ、フラグは に設定されますlocal_sense。

樹木バリアを組み合わせる

集中型バリアの潜在的な問題は、すべてのスレッドがパス/ストップのグローバル変数に繰り返しアクセスするため、通信トラフィックがかなり高くなり、スケーラビリティが低下することです。

この問題は、スレッドを再グループ化し、階層バリア（例えば、Combining Tree Barrier）を使用することで解決できます。また、ハードウェア実装はスケーラビリティの向上という利点ももたらします。

結合ツリーバリアは、すべてのスレッドが同じ場所でスピンするのを回避することでスケーラビリティを解決するためにバリアを実装する階層的な方法です。 [4]

kツリーバリアでは、すべてのスレッドがk個のスレッドからなるサブグループに均等に分割され、これらのサブグループ内で第1ラウンドの同期が行われます。すべてのサブグループが同期を完了すると、各サブグループの最初のスレッドが第2レベルに入り、さらに同期が行われます。第2レベルでは、第1レベルと同様に、スレッドはk個のスレッドからなる新しいサブグループを形成し、グループ内で同期を行います。各サブグループ内の1つのスレッドが次のレベルに送られ、これが繰り返されます。最終的に、最終レベルでは同期するサブグループは1つだけになります。最終レベルの同期後、解放信号が上位レベルに送信され、すべてのスレッドがバリアを通過します。[6] [7]

ハードウェアバリアの実装

ハードウェアバリアは、上記の基本的なバリアモデルをハードウェアで実装します。[3]

最も単純なハードウェア実装では、バリアを実装するための信号を伝送するために専用線を使用します。この専用線はOR/AND演算を実行し、パス/ブロックフラグとスレッドカウンタとして機能します。小規模なシステムでは、このようなモデルは機能し、通信速度は大きな問題にはなりません。大規模なマルチプロセッサシステムでは、このハードウェア設計により、バリア実装のレイテンシが大きくなる可能性があります。プロセッサ間のネットワーク接続は、レイテンシを低減する実装の一つであり、これはCombining Tree Barrierに類似しています。[8]

POSIX スレッドバリア関数

POSIXスレッド標準は、スレッドバリア関数を直接サポートしています。この関数を使用すると、他のスレッドがそのバリ​​アに到達するまで、指定されたスレッド またはプロセス全体をバリアでブロックすることができます。[2] POSIXがスレッドバリアを実装するためにサポートしている主な3つのAPIは次のとおりです。

pthread_barrier_init()
スレッドバリアを初期化し、バリアを解除するために必要なスレッド数を設定する[9]
pthread_barrier_destroy()
スレッドバリアを破壊してリソースを解放する[9]
pthread_barrier_wait()
pthread_barrier_init()この関数を呼び出すと、呼び出しで指定された数のスレッドがpthread_barrier_wait()バリアを解除するまで現在のスレッドがブロックされます。[10]

次の例 (pthread API を使用してCで実装) では、スレッド バリアを使用してメイン プロセスのすべてのスレッドをブロックし、プロセス全体をブロックします。

#include <stdio.h> #include <pthread.h> #TOTAL_THREADS 2 を定義する#THREAD_BARRIERS_NUMBER 3 を定義する#define PTHREAD_BARRIER_ATTR NULL // pthreadバリア属性pthread_barrier_tバリア; void * thread_func ( void * ptr ){   printf ( "実行中のスレッド数が十分でないため、バリアで待機しています... \n " , THREAD_BARRIERS_NUMBER );  pthread_barrier_wait ( &バリア); printf ( "バリアが解除され、スレッドID %ldが現在実行中です\n " , pthread_self ()); }intメイン() { pthread_tスレッドID [合計スレッド数];  pthread_barrier_init ( &バリア, PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );   ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );    } // pthread_join() は指定されたすべてのスレッドが終了するまでプロセスをブロックするため、 // バリアで待機するのに十分なスレッドがないため、このプロセスはブロックされます ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_join (スレッドID [ i ], NULL );  } pthread_barrier_destroy ( &バリア); printf ( "スレッドバリアが解除されました\n " ); // この行はTOTAL_THREADS < THREAD_BARRIERS_NUMBERなので呼び出されません }

そのソースコードの結果は次のようになります。

実行中のスレッドが 3 つ足りないため、バリアで待機しています...実行中のスレッドが 3 つ足りないため、バリアで待機しています... // (メイン プロセスは、3 つのスレッドが足りないためブロックされています) // 行 printf("Thread barrier is lifted\n") には到達しません

ソースコードからわかるように、生成されるスレッドは2つだけです。これら2つのスレッドはどちらもスレッド関数ハンドラとしてthread_func()を持ち、 を呼び出します。一方、スレッドバリアは解除するために3つのスレッドが( )を呼び出すことを想定しています。pthread_barrier_wait(&barrier)pthread_barrier_waitTHREAD_BARRIERS_NUMBER = 3

TOTAL_THREADS を 3 に変更すると、スレッド バリアが解除されます。

実行中のスレッドが 3 つ足りないため、バリアで待機しています...実行中のスレッドが 3 つ足りないため、バリアで待機しています... 実行中のスレッドが 3 つ足りないため、バリアで待機しています...バリアが解除されました。スレッド ID 140643372406528 が現在実行中です。バリアが解除されました。スレッド ID 140643380799232 が現在実行中です。バリアが解除されました。スレッド ID 140643389191936 が現在実行中です。スレッド バリアが解除されました

main() はスレッド、つまりプロセスの「メイン」スレッドとして扱われるため、 [11]pthread_barrier_wait() insideを呼び出すと、main()他のスレッドがバリアに到達するまでプロセス全体がブロックされます。次の例では、pthread_barrier_wait()insideでスレッドバリアを使用して、 main()2つの「新しく作成された」スレッドがスレッドバリアに到達するまで、プロセス/メインスレッドを5秒間ブロックします。

#TOTAL_THREADS 2 を定義する#THREAD_BARRIERS_NUMBER 3 を定義する#define PTHREAD_BARRIER_ATTR NULL // pthreadバリア属性pthread_barrier_tバリア; void * thread_func ( void * ptr ){   printf ( "実行中のスレッド数が十分でないため、バリアで待機しています... \n " , THREAD_BARRIERS_NUMBER ); 睡眠（5 ） pthread_barrier_wait ( &バリア); printf ( "バリアが解除され、スレッドID %ldが現在実行中です\n " , pthread_self ()); }intメイン() { pthread_tスレッドID [合計スレッド数];  pthread_barrier_init ( &バリア, PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );   ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {         pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );    }pthread_barrier_wait ( &バリア); printf ( "スレッドバリアが解除されました\n " ); // この行はTOTAL_THREADS < THREAD_BARRIERS_NUMBERなので呼び出されません pthread_barrier_destroy ( &バリア);}

この例では、2つの「新しく作成された」スレッドが完了するまで待機しません。メインスレッドをブロックするためにinside をpthread_join()呼び出し、2つのスレッドが5秒間待機して処理を完了するまでプロセスがブロックされるようにします（9行目 - ）。pthread_barrier_wait()main()sleep(5)

参照

参考文献

  1. ^ abcde 「障壁の実装」カーネギーメロン大学。2018年1月20日時点のオリジナルよりアーカイブ。 2017年8月2日閲覧。
  2. ^ ab GNUオペレーティングシステム. 「pthread_barrierの実装」. gnu.org . 2024年3月2日閲覧。
  3. ^ abc Solihin, Yan (2015-01-01). 『並列マルチコアアーキテクチャの基礎（第1版）』Chapman & Hall/CRC. ISBN 978-1482211184。
  4. ^ ab Culler, David (1998).並列コンピュータアーキテクチャ、ハードウェア/ソフトウェアアプローチ. Gulf Professional. ISBN 978-1558603431。
  5. ^ Culler, David (1998).並列コンピュータアーキテクチャ、ハードウェア/ソフトウェアアプローチ. Gulf Professional. ISBN 978-1558603431。
  6. ^ ab Nanjegowda, Ramachandra; Hernandez, Oscar; Chapman, Barbara ; Jin, Haoqiang H. (2009-06-03). Müller, Matthias S.; Supinski, Bronis R. de; Chapman, Barbara M. (編).超並列時代のOpenMPの進化. コンピュータサイエンス講義ノート. Springer Berlin Heidelberg. pp. 42–52. doi :10.1007/978-3-642-02303-3_4. ISBN 9783642022845。
  7. ^ Nikolopoulos, Dimitrios S.; Papatheodorou, Theodore S. (1999-01-01). 「ccNUMAシステムにおける同期アルゴリズムと同期規律の定量的アーキテクチャ評価」. 第13回国際スーパーコンピューティング会議議事録. ICS '99. ニューヨーク、ニューヨーク州、米国: ACM. pp.  319– 328. doi :10.1145/305138.305209. ISBN 978-1581131642. S2CID  6097544. 2017年7月25日時点のオリジナルよりアーカイブ。2019年1月18日閲覧。
  8. ^ NR Adiga他「BlueGene/Lスーパーコンピュータの概要」高性能ネットワーキングおよびコンピューティングに関する会議論文集、 2002年。
  9. ^ ab "pthread_barrier_init(), pthread_barrier_destroy()". Linux manページ. 2024年3月16日閲覧。
  10. ^ "pthread_barrier_wait()". Linux manページ. 2024年3月16日閲覧。
  11. ^ 「Cプログラムでプロセスとスレッドの数を取得する方法」。stackoverflow 。2024年3月16日閲覧。

「バリア同期による並列プログラミング」sourceallies.com . 2012年3月.

「https://en.wikipedia.org/w/index.php?title=Barrier_(computer_science)&oldid=1319441072」より取得