トランザクションメモリ

複数のプロセサが共有データをアクセスする場合には排他制御が必要となるが、使用権を得られなかったプロセサは、札メモリをチェックして使用権を獲得するループに入る。そうなると、使用権が獲得できるまで有効な処理を行えず無駄が生じる。

このような無駄を減らすには、排他制御を行う資源を細分化して、それぞれにロックを設けるという方法が取られる。例えば、銀行口座の例では、どれか1つのプロセサが口座データベースをアクセスしている場合は、他のプロセサは口座データベースをアクセス出来ないようにロックしてしまえば正しい処理ができるが、一時には1つの口座の更新しかできず、無駄が多い。これを、それぞれの口座ごとにロックを設けると、他のプロセサは他の口座データにはアクセスできるので、多数のプロセサが並列に動作でき効率が上がる。

実際の例では事情はこれほど簡単では無く、多数の資源を確保する必要があるのが普通である。プロセサAが資源1をロックして、その次に資源2をロックしようとし、一方、プロセサBは資源2をロックしており、その次に資源1の獲得を要求するということになると、プロセサA、Bともに必要な資源の獲得待ちで先に進めないデッドロックが発生してしまう。ロックを細分化していくと、このような問題の発生の可能性が増大し、注意深いプログラミングが必要となり、マルチプロセサを効率的に使うプログラミングが難しい一因となっている。

この問題の有力な解決法と考えられているのがトランザクショナルメモリ(Transactional Memory:TM。あるいはトランザクションメモリとも言う)という方式である。1993年にHerlihy氏とMoss氏がこのトランザクショナルメモリを考案し、それを実現するハードウェア機構に関する論文を発表した。これに対して、通常のプロセサが備えているロック機構だけを使って、あとはすべてソフトウェアでトランザクショナルメモリを実現するSoftware Transactional Memory(STM)をShavi氏とTouitou氏が1995年に発表している。

トランザクションメモリでは、プログラムの中で排他アクセスを必要とする部分をトランザクションと呼び、トランザクションの最初でトランザクション開始命令、終了時にトランザクション終了命令を置く。プログラムは明に排他制御を行うことなくトランザクション部分のコードを実行するのであるが、何らかの方法で、(1)トランザクションでデータを参照したメモリアドレスを監視し、(2)トランザクションの中でのデータの格納は、他のプロセサからは見えないローカルなバッファ領域に格納しておく。そして、(3)トランザクションの終了時点で、(1)でデータを参照したメモリの値が変更されている場合は、トランザクションを失敗させ、再度、トランザクションの開始からやり直す。一方、データを参照しメモリが書き換えられていない場合は、トランザクションは成功であり、バッファに格納してあるデータをメモリに一括してアトミックに書き戻す。ここで、一括してアトミックにというのが重要で、この書き戻しの間に他のプロセサのメモリアクセスが挟まってはいけない。

ロックによる排他制御の場合は、予防的に他のプロセサの共有資源へのアクセスを制限するが、トランザクションメモリの場合には、共有資源へのアクセスは自由に行うが、使用したデータが書き換えられて複数のプロセサの処理の間で干渉がある場合だけトランザクションが失敗してやり直しとなる。銀行口座の例で言うと、複数のプロセサが別々の口座の残高をアクセスして更新している場合にはすべてのトランザクションは成功して有効な並列処理ができ、たまたま、2つのプロセサが同じ口座残高の更新を同時に行った場合だけトランザクションが失敗してやり直しになる。そして、この処理を行うアプリケーションプログラムは排他制御などの難しい並列処理を気にする必要がないので、プログラムの開発が容易となる。

前述のように、ソフトウェアだけでトランザクションメモリを実現している例もあるが、使用したデータが書き換えられていないかどうかのチェックをソフトウェアで行うのは大変であり、ハードウェアによるアシストが色々と研究されている。

Sun Microsystemsは、2008年のISSCCにおいてトランザクションメモリをサポートするハードウェアを備えたRockプロセサを発表した。Rockプロセサでは、トランザクション開始命令以降にアクセスされたデータキャッシュのラインに特別なマークを付けておき、他のプロセサからの書き込み要求のスヌープにより、マークを付けられたキャッシュラインへの書き込みが検出されるとトランザクションを失敗させる。この機構は、Load Linked/Store Conditionalのサポートハードウェアと類似であるが、すべてのキャッシュラインでの変更をORしてトランザクションに失敗を検出する必要がある。

また、データの格納については、トランザクションの終了まではストアバッファへの書き込みで留めておき、キャッシュやメモリへの書き込みは行わない。そして、トランザクションの終了命令を実行する時点で、そのトランザクションが成功であれば、他のプロセサのメモリアクセスをブロックして、ストアバッファに格納されたストア要求を一括してメモリに書き戻す。

Rockのハードウェアアシストで処理できるトランザクションは、32エントリのストアバッファに格納できるサイズに制限されるが、Javaなどの処理ではこの範囲に収まる小さなトランザクションが多いので有効であるという。

この例のように、一般にハードウェアで処理できるトランザクションのサイズには制限がある。しかし、実用システムでは大きなトランザクションが出てくる場合もあり、ハードウェア機構がストアバッファの不足などで処理しきれない場合には、トランザクションのサイズに制限のないソフトウェアトランザクションメモリに切り替えるというメカニズムも必要になってくる。

なお、Rockプロセサは、スカウトスレッドなど、トランザクションメモリ以外にも先進的な機構を取り入れた野心的なプロセサであったが、SunがOracleに買収される直前に開発がキャンセルされ、CPUチップは完成していたと言われるが、実用化されないで終わってしまった。