Transactional memory
研究室の勉強会のネタとして、transactional memoryというものを勉強している。わりと新しい概念らしく、書籍での情報が得られないので論文を読んだり、Wikipediaを眺めたりしつつ、わからないところを先輩に聞いたりして徐々に理解を深めているところ。とりあえず今まで勉強したことなどを吐き出してみる。
ここでは、software transactional memoryについて主に説明する。
なぜsoftware transactional memoryが必要か
データベースでよく用いられているトランザクションを、マルチプロセッサ環境などでの共有資源管理に持ち込んだものがtransactional memoryである。
v.s. blocking method
共有資源管理の典型的な手法としては、mutexやセマフォ、あるいはロックをするというものであった。しかし、これらの方法では、アクセス権のないプロセス/スレッドは実行をブロックされてしまうので、並列して動作するプロセス数が多い場合には並列度が低くなり効率が悪い。
その上、慎重にプログラムを書かないとデッドロックに陥ってしまう危険性がある。
一方transactional memoryの場合は、実行がブロックされることはなく、必ず有限のステップでメモリの読み書きを行うトランザクションが終了することが保証されている。トランザクションが終了する場合には2つあり、メモリの読み書きが成功したケースと、失敗したケースである。
transactional memoryによって、まずデッドロックを気にしながらプログラムを書かなくてもよくなるので、並列動作するプログラムを書く難易度が下がる。
v.s. other non-blocking method
これまでに提案されている同期機構には、transactional memory以外にも実行をブロックしないものがある。しかし、これらの手法はk-word(k > 1)のCompare&Swap命令があることを前提としているものが多い。実際に流通している、あるいは近い将来に出回るであろうアーキテクチャのほとんどは1 wordのCompare&SwapとLoad-Link/Store-Conditionalしかサポートしていないため、これらの手法は実用に足るものではない。
一方、transactional memoryは1 wordのLoad-Link/Store-Conditionalがサポートされていればよい。
※ 適当な同期プリミティブさえ存在すれば、k-wordのCompare&Swapは実現可能だが、アーキテクチャの命令レベルでサポートされていないとパフォーマンスがでない、ということのようだ
transactional memoryをもうちょい詳しく
Load-Link/Store-Conditional
transactional memoryを実現するためのプリミティブな命令として、Load-LinkとStore-Conditionalという仮想的な命令がある（実装しているアーキテクチャもある）。
まず、Load-Linkでは指定したメモリのアドレスから値を読み出す。そして、その後にLoad-Linkしたメモリアドレスに対しStore-Conditionalを実行すると、そのアドレスの指すメモリの内容がLoad-Linkを実行したときから変化していない場合に限って、Store-Conditionalは新しい値を書き込む。
