メニーコアにおけるバリア同期の課題とその解決手法

6. メニーコア特有の問題と解決方法

メニーコアプロセサは、マルチコアプロセサのプロセサの数が多いだけであるが、最大でも4～8コアのマルチプロセサではうまく行く手法でも、数十コアになると問題が出てくることがある。前節で述べたプロセサコア間の接続もその1つであるが、それ以外にも、全コアの並列処理の終了を待ち合わせる同期処理やキャッシュコヒーレンスの維持も難しくなってくる。

並列分散処理の終了を待ち合わせるバリア同期

並列化による性能向上のところで、並列化したすべてのプロセサの処理の終了を待ち合わせる同期時間の短縮が重要ということを書いた。このように、すべてのプロセサの処理が終了するまでバリア(Barrier)を張って、次の処理の開始を止めて置くので、バリア同期と呼ぶ。

メモリ上にカウンタ変数を作り、処理を終わったプロセサ数を数え、カウントがプロセサ数に達すると終了とするという方法は、原理的には良いのであるが、2つ問題がある。

1つは、処理を終了したプロセサが、カウンタ変数を読んで+1し、カウンタ変数に書き戻すという一連の動作の間に他のプロセサがカウンタ変数を読んだり、カウンタ変数に値を書き込んだりすると動作がおかしくなってしまう。このため、カウンタ変数のアクセスには排他制御が必要という点である。このために、カウンタ変数の読み込み前にロックの獲得、カウンタ変数への書き戻し後にロックの解放という操作が必要となり、カウントアップに時間が掛る。コア数が少ない場合はそれほど混雑しないが、メニーコアでカウンタ変数にアクセスするコアが多くなると、アクセスしようとしても、他のコアがロックしていて待たされる時間が長くなる。

なお、アトミックにメモリの内容をカウントアップする命令を持っているプロセサであれば、ロックの獲得、解放は不要であり、カウントアップのオーバヘッドを減らすことができる。

また、並列の処理が終わったプロセサは、カウンタ変数を読み出してカウントが終了したかどうかを判定するループを廻る。このため、カウンタ変数にはメニーコアの多くのコアからのアクセスが集中する。そして、混雑でメモリアクセス時間が伸びてしまうので、全コアがカウントアップを検出するのには、コア数比例よりもずっと長い時間が掛るという問題がある。このため、メモリ上のカウンタ変数を使う方式では、メニーコアの場合、同期に非常に長い時間が掛ってしまう。

これに対して、京スパコンに使われているSPARC64プロセサでは同期専用のハードウェアを備えている。原理的には図6.1のように、各コアに1bitが対応するレジスタを設け、各コアが処理を完了すると、自分のコアに対応するビットをセットすることができるようになっている。このレジスタのセット動作は、他のコアのセット動作と競合することが無いので、短時間で実行することができる。

そして、レジスタの全ビットはすべてのコアに通知され、各コアの内部レジスタとして、その内容を読めるようになっている。これも他のコアのアクセスと競合しないので短時間で読むことができる。

並列処理の開始時にバリアレジスタをクリアして置き、各コアPが自分の処理を終わったら、バリアレジスタのビットをセットする。そして、処理の終わったコアはバリアレジスタの全ビットを読み出すというループを廻り、すべてのビットが"1"にセットされるのを待つ。全ビットが"1"になれば、すべてのコアの処理が終わったことが確認できるので、次の処理を開始する。

このようにすると、バリアレジスタへの書き込みが他のコアの書き込みと競合することはない。また、各コアのレジスタの読み込みも競合することが無いので、メモリ上のカウンタ変数を使う方式に比べて短い時間でバリア同期を行うことができる。

しかし、メニーコアの場合は、各コアからバリアレジスタまでのセット線を張り、バリアレジスタの情報を全コアに配る配線を張るのは負担が大きい。このため、ツリーネットワークで各コアの処理終了情報を集めるという方法が使われる。

この方法では、図6.2のように、同期を必要とするすべてのコアを含むツリーを構成する。最下層の各コアは、自分の処理が終わると実線の矢印を通って上位のコアに終了を通知する。2層目以上のコアは、下位のすべてのコアの処理の終了通知が揃い、自分の処理も終了すると実線の矢印の先の上位コアに終了を通知する。このようにして、最上位のコアが下位のすべてのコアから終了通知を受け取り、自分の処理も終われば、すべての並列処理が終了したことが分かる。

そして、最上位のコアは、破線の矢印をたどって下位のコアにすべてのコアの処理の終了を通知し、通知を受け取ったコアは、次の処理を開始する。

このツリーは物理的に存在する必要はなく、リングやメッシュなどを使う通信経路を使って実線と破線で結ばれたコア間の通信が可能であり、仮想的なツリーを構成できればよい。また、図6.2では2分木(バイナリツリー)を示したが、2個ではなく、3個以上の下位コアを持つツリーを構成しても良い。

図6.2のような2分木であればN-1ノード(ただし、Nは2のベキ)の同期を行う2×(log₂N-1)ステップの通信でことができる。この方法は図6.1に示したバリアレジスタを用いる方法よりも通信ステップは多いが、コア数が多くなっても通信時間の増加は緩やかであるので、メニーコアの同期には有効な方法である。なお、京スパコンのノード間をつなぐToFuインタコネクトでは、このような方法でノード間の同期を実現している。