預金の引き出しでは、残高確認→現金の引き出し→残高の更新という一連の処理を他のプロセサの処理からの干渉なく行う必要がある。

プロセサ1の引き出しの処理で、残高の更新を行う前に、他のプロセサが引き出し前の残高を読んで、引き出し、残高更新を行ってしまうと、処理がおかしくなってしまう。このため、Lockというメカニズムを使って、1つのプロセサがこの一連の処理を終わるまで、他のプロセサはこの処理を開始できないようにするというのが一般的なやり方である。しかし、これでは複数のプロセサがあっても一時には1つのプロセサしか使えず、効率が悪い。

プロセサ1が口座A、プロセサ2が口座Bの引き出し処理を並行に実行するのは問題ないので、口座ごとにLockを設ければこの問題は解決する。しかし、口座Aから口座Bへの振込をする場合は両方の口座のLockを獲得する必要がある。この時、プロセサ1が口座AからBへの振込のため口座AをLockし、プロセサ2が口座BからCへの振込のため口座BをLockし、プロセサ3が口座CからAへの振込のため口座CをLockしていると、どのプロセサも振込先の口座のLockを獲得できず、デッドロックに陥ってしまう。

並列実行度を上げるためには、Lockの細分化は必須であるが、デッドロックが起こりやすくなり、注意深いプログラミングが必要となる。これが、並列プログラミングが難しい1つの理由となっている。

並列プログラミングの切り札 - ハードウェアトランザクションメモリ

この問題の有力な解決手段と考えられているのがトランザクションメモリ(Transaction Memory)である。トランザクションメモリはソフトウェアでも実現できるが、実行性能の点で、ハードウェアで実現するHTM(Hardware Transaction Memory)が望ましい。Haswellでは、このHTMをサポートすることが発表されている。また、IBMのスパコン用プロセサであるBG/QやメインフレームのzEnterprise EC12プロセサもすでにHTMをサポートしており、HTMサポートが一般化しつつある。

トランザクションメモリでは、一連の不可分な処理の開始時にトランザクション開始命令、終了時にトランザクション終了命令を実行する。そして、トランザクションの開始から終了までの間にデータを読み込んだメモリアドレスをRead Set、書き込んだメモリアドレスをWrite Setと呼び、こられのメモリアドレスへの他のプロセサからのアクセスを監視する。

トランザクションの終了までに、Read Setに他のプロセサからの書き込みが無く、Write Setへの他のプロセサからの読み出し、書き込みが無ければ、一連の処理に干渉する他のプロセサの処理は存在しないので、終了命令の実行でトランザクションを正常終了(コミットと呼ぶ)することができる。一方、他のプロセサがRead SetやWrite Setにアクセスして干渉が検出された場合は、トランザクションを異常終了(アボートと呼ぶ)する。異常終了すると、トランザクション開始からの状態変更を捨てて、トランザクションの開始直前の状態に戻ってやり直す。

このようにすると、干渉が無い場合は正しく処理が終わり、実行時に干渉が検出された場合だけ、処理をやり直すということが自動的に出来るので、Lockを使う必要がなく、プログラミングが簡単になる。

HTMを実現するには、Read SetとWrite Setのアドレスを記憶する必要がある。そして、Write Setのデータは、コミットするまでは他のスレッドやコアから見えてはならず、コミット時には一括してメモリに書き込む必要がある。

また、他のプロセサがRead SetやWrite Setのアドレスに書き込みを行おうとする場合やWrite Setのアドレスから読み込みを行おうとする場合は干渉があるので、これを検出して、実行中のトランザクションをアボートする必要がある。そして、トランザクションをアボートすると、Write Setのデータを捨てて、開始命令の実行直前のアーキテクチャ状態を回復する必要がある。

(中編に続く)

■Intel 次世代プロセッサ「Haswell」関連記事
・【レポート】HPC性能が大幅に強化されたHaswell(前編) -各コアに256bit長のFMAを2個装備 (2012年10月3日)
・【レポート】HPC性能が大幅に強化されたHaswell(中編) - TLBミスによる性能低下を減少 (2012年10月4日)
・【レポート】HPC性能が大幅に強化されたHaswell(後編) - HPCとして通用する性能を実現 (2012年10月5日)
・【レポート】IDF 2012 - 次期Intel Core「Haswell」の内部構造を探る - Uncore(GPU/Media Block)編 (2012年9月25日)
・【レポート】IDF 2012 - 次期Intel Core「Haswell」の内部構造を探る - マイクロアーキテクチャ編 (2012年9月18日)
・【レポート】IDF 2012 - 次期Intel Core「Haswell」の内部構造を探る - 拡張命令(AVX2/TSX)編 (2012年9月18日)
・【レポート】トランザクションメモリのサポートが明らかとなったIntelのHaswell (2012年2月16日)