日々の流転

λ. Haskell on a Shared-Memory Multiprocessor. Tim Harris, Simon Marlow, Simon Peyton Jones

• <URL:http://research.microsoft.com/~simonpj/papers/parallel/>
• <URL:http://jp.citeulike.org/article/342280>

をざっと読んだ。

まず復習(以下ではSTGマシンの知識は仮定)。これまでのGHCのネイティブスレッドへの対応はジャイアントロックを使った対応だった。つまり、外部のコードとかは複数のネイティブスレッドで同時に実行できるけど、同時にHaskellコードを実行するネイティブスレッドはただ一つだけだった*1。これだとSMPでもあまり嬉しくないので、より細粒度のロックにして並列度を上げたい。ただ、各サンクにロックを用意して操作毎にロックすることにすると、無茶苦茶オーバーヘッドがかかる。

で、「どうすんだろな〜」と思ってたんだが、この論文では、割と楽観的な前提に基づいて「そもそもサンクに対して厳密な排他制御は不要」と言っている。私がこの分野についてあまり知らないからかもしれないが、コロンブスの卵みたいで随分感心した。

まず、サンクを評価結果(へのindirection)で上書きする際にポインタを書き込む領域を別に用意することで、サンク上の他のデータが評価結果の書き込みで壊れないようにする。これで複数のスレッドが同時に同一のサンクを実行しても問題なくなる。ただ、複数のスレッドが同時に同じサンクを実行すると、計算を重複して行うことになってしまう。副作用のある計算は複数回実行するとまずいので真面目に排他制御するが、大多数の純粋な計算は何度実行しようと意味論的には問題ない。

もちろん、意味論的に問題なくても計算量的には問題になる。そこで各スレッドは定期的な lazy black-holing のタイミングでサンクを排他的に所有しようとし、それによって重複する計算を検出する。で、検出された重複する計算は捨てる。この処理にはサンクに対する排他制御が必要になるが、lazy black-holing の頻度は通常のサンク操作の頻度よりもずっと低いため、各操作毎に排他制御するよりもオーバーヘッドはずっと低い。また、すぐに計算が終了するようなサンクは排他制御無しで実行できる*2し、計算に時間がかかるようなサンクの場合も無駄な計算は一定時間で破棄できることが保証される。

あとは、複数のスレッドが同時に同じサンクを実行する可能性を極力下げれば良い。そのために、サンクに制御を移す時点での eager black-holing (ここでは grey-holing と呼んでいる) も提案している。これも排他制御無しで行え、これによって複数のスレッドが同時に同じサンクを実行してしまう可能性を限りなく小さく出来る。ただ、このタイミングでのサンクへの書き込みは通常のアクセスパターンから外れているので、キャッシュのスラッシング(cache-thrashing)を引き起こす可能性もあり、これによって逆に性能が低下することも有り得る。

とかとか。

他にもいろんなテクニックを使ってるけど、特に面白かった部分は以上の話。

λ. google:アルキメデスの卵

ふと検索してみたら、2件ひっかかった。