ハードウェア・トランザクショナルメモリのサーベイ

http://research.cs.wisc.edu/trans-memory/biblio/hwtm.html に載っているハードウェア・トランザクショナルメモリの主要な論文を順に読んでいきます。
2
ReiOdaira @ReiOdaira

トランザクショナルメモリの元論文[Herlihy+,93]を久しぶりに読み返した。よく知られているが元論文はハードウェアTM。ロックフリーデータ構造を簡単に書ける、ってのを強調してたのね。スヌーププロトコルを利用した部分は後のHTMと共通だがTM用に別キャッシュを使うのが特徴。

2012-01-18 02:10:05
ReiOdaira @ReiOdaira

Multiple Reservations and the Oklahoma Update [Stone+,93]はHerlihyらと同時期にハードウェアTMを提案した論文のようだ。LL/SCを拡張して、予約レジスタ中にtxストアのデータをバッファしておいて最後にコミット。

2012-01-20 14:50:24
ReiOdaira @ReiOdaira

Speculative Lock Elision [Rajwar+,01]はハードウェアTMと同じ仕組みだが、TM用の命令は用意せずにロック獲得・解放の命令シーケンスをハードウェアが全自動で認識して投機的に除去する。認識を間違ったとしてもプログラムの意味は保たれるのがポイント。

2012-01-20 18:26:40
ReiOdaira @ReiOdaira

同じ著者のTransactional Lock-Free Execution of Lock-Based Programs [Rajwar+,02]は前の論文のSLEを拡張して、衝突が起きた場合にもロックに戻らない。Txにタイムスタンプを付加し、若いtxが常に勝つようにする。

2012-01-20 19:58:41
ReiOdaira @ReiOdaira

Transactional Memory Coherence and Consistency [Hammond+,04]はいわゆるTCC。プログラム全体を複数のtxに分割して常にtxを実行し続ける。MESIのようなプロトコルは不要なので設計が簡単になる。プログラミングは大変そう?

2012-01-21 01:10:03
ReiOdaira @ReiOdaira

Unbounded Transactional Memory [Ananian+,05]は従来のハードウェアTMのtxサイズがキャッシュサイズ等に制限されていたのを無くした。しかし結局のところソフトウェアTMと同じ構造(txデータはメモリに、云々)をハードウェアで作ったという話。

2012-01-21 18:32:58
ReiOdaira @ReiOdaira

@ReiOdaira 著者らはUTMだけでなく、現実的な"Large TM"も提案している。通常は従来同様コヒーレンスプロトコルを用い、キャッシュから溢れるとラインにオーバーフロービットを立ててメモリの専用領域に追い出す。ビットが立っているラインの衝突検知では当領域も探索する。

2012-01-21 19:06:44
ReiOdaira @ReiOdaira

Thread-Level Transactional Memory [Moore+,05]はハードウェアTMの機能を一般化したユーザインタフェースの提案・・・なのだが、だから何という感じ。キャッシュから追い出されたtxデータをbloomフィルターで管理する話はこれが初出か?

2012-01-21 19:54:18
ReiOdaira @ReiOdaira

Virtualizing Transactional Memory [Rajwar+,05]は性能云々よりも、キャッシュオーバーフローやコンテキストスイッチしてもアボートしない手法にフォーカスした論文。手法自体は[Ananian+,05]と[Moore+,05]の組み合わせ。

2012-01-22 14:58:51
ReiOdaira @ReiOdaira

Characterization of TCC on Chip-Multiprocessors [McDonald+,05]はTCCをシミュレータで評価してスヌープコヒーレンス方式と比較した。結論:性能は大差ない。(だから並列プログラミングしやすいTCC勝利、と言いたいらしい。)

2012-01-22 16:46:31
ReiOdaira @ReiOdaira

LogTM: Log-based Transactional Memory [Moore+,06]はeagerなバージョン管理(データは新しい値で更新し前の値はログに取っておく)を最大の特徴とする。しかし新しい値はオーバーフローするまではキャッシュにあるので従来手法と大差ない。

2012-01-22 22:21:29
ReiOdaira @ReiOdaira

@ReiOdaira オーバーフローしてメモリに書き戻された未コミットデータが他txに読まれないように衝突検知する仕組みはスヌープでなくディレクトリ式であることに依存している。Eager方式はコミットが速いのが利点というがオーバーフローしない限りは従来方式と同じ速さと思われる。

2012-01-22 23:01:52