日記を書く [・w・] はやみずさん

2008-05-29

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は新しい値を書き込む。

transactional memoryにおけるトランザクション
  1. トランザクション開始
  2. 共有資源の読み書き
  3. トランザクション中で操作したメモリが、トランザクション開始時点から(他のトランザクションによって)更新されているかチェック

references

  1. no title
  2. Software transactional memory - Wikipedia
  3. Load-link/store-conditional - Wikipedia
Connection: close