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

並列コンピューティングにおいて、バリアは同期方法の一種です。^[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構造体_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 ); 
    バリア->スレッドバリア番号=スレッドバリア番号;  
    バリア-> total_thread = 0 ; // 合計スレッド数を 0 に初期化します  
}

void thread_barrier_wait ( thread_barrier *バリア){  
    if ( ! pthread_mutex_lock ( & (バリア->ロック))){
        バリア-> total_thread += 1 ;  
        pthread_mutex_unlock ( & (バリア->ロック));
    }

    while (バリア->合計スレッド<バリア->スレッドバリア番号);   

    if ( ! pthread_mutex_lock ( & (バリア->ロック))){
        バリア-> total_thread -= 1 ; // スレッドバリアを通過したのでスレッドを 1 つ減らします   
        pthread_mutex_unlock ( & (バリア->ロック));
    }
}

void thread_barrier_destroy ( thread_barrier *バリア){  
    pthread_mutex_destroy ( & (バリア->ロック));
}

void * thread_func ( void * ptr ){  
    printf ( "スレッド ID %ld はバリアーで待機しています。実行中のスレッドが %d 個足りないためです... \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_BARRIERS_NUMBER 個のスレッドがスレッド バリアに到達する まで、 thread_barrier_wait()を呼び出すすべてのスレッドがブロックされます。

そのプログラムの結果は次のとおりです。

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

プログラムからわかるように、作成されるスレッドは 2 つだけです。これら 2 つのスレッドは両方とも、スレッド関数ハンドラーとして を持ち、 を呼び出しますが、スレッド バリアは解除されるために 3 つのスレッドが( ) を呼び出すことを想定しています。TOTAL_THREADS を 3 に変更すると、スレッド バリアが解除されます。thread_func()thread_barrier_wait(&barrier)thread_barrier_waitTHREAD_BARRIERS_NUMBER = 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 はバリアを通過したことを意味し、スレッド 3 の状態値が 0 の場合はバリアで停止中であることを意味します。^[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構造体_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 ); 

    バリア-> total_thread = 0 ;  
    バリア->スレッドバリア番号=スレッドバリア番号;  
    バリア->フラグ= false ;  
}

void thread_barrier_wait ( thread_barrier *バリア){  
    bool local_sense =バリア->フラグ;   
    if ( ! pthread_mutex_lock ( & (バリア->ロック))){
        バリア-> total_thread += 1 ;  
        ローカルセンス= !ローカルセンス;  
        
        if (バリア->合計スレッド==バリア->スレッドバリア番号){   
            バリア-> total_thread = 0 ;  
            バリア->フラグ= 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 はバリアーで待機しています。実行中のスレッドが %d 個足りないためです... \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_BARRIERS_NUMBER がバリアに到達したかどうかを示すstruct _thread_barrierのブール値メンバー

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

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

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

この問題は、スレッドを再グループ化し、マルチレベル バリア (例: Combining Tree Barrier) を使用することで解決できます。また、ハードウェア実装には、スケーラビリティが向上するという利点もあります。

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

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

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

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

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("スレッド バリアが解除されました\n") には到達しません

ソース コードからわかるように、作成されるスレッドは 2 つだけです。これら 2 つのスレッドには、スレッド関数ハンドラーとして を呼び出す thread_func() がありますが、スレッド バリアが解除されるには 3 つのスレッドが( ) を呼び出す必要があります。TOTAL_THREADS を 3 に変更すると、スレッド バリアが解除されます。pthread_barrier_wait(&barrier)pthread_barrier_waitTHREAD_BARRIERS_NUMBER = 3

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

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

#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 つの「新しく作成された」スレッドが完了するのを待つために を使用しません。メイン スレッドをブロックするために内部でpthread_join()を呼び出し、5 秒待機した後、2 つのスレッドが操作を完了するまでプロセスがブロックされるようにします (行 9 - )。 pthread_barrier_wait()main()sleep(5)

• フォーク・ジョインモデル
• ランデブー（プラン9）
• 記憶の壁

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