計算の分散 - w

最近計算の分散について考え気味。
僕はメモリは共有してない方が萌えるのでそっちっぽい話。

僕がインターネットと距離を置いてるあいだにErlangとかが流行ってたらしいけど、ああいうのは僕としては結構どうでもよい。と、いうのは、まあ、別にプロセス起動だとかスレッド起動だとか、メッセージのやりとりだとか、そういう部分が簡単になったところで別にそんなに嬉しくないからだ。（←ちゃんと勉強してないのでこういう偉そうなことを書くのはよくない）
いや、うん。スレッド起動とか、メッセージ通信とかは、Cのライブラリにしたとしても、そーれほど苦痛なものになるわけではない。多少型チェックに弱いとか、書きにくさとか、うっかり変な変数共有してた…とかはあるけど、C使いの人なら、そのぐらい日常茶飯事だから、どうでもいいよね。

そうじゃなくて、データ構造の話。

メモリを共有してないCPU（つか具体的にはアレ←全然具体的じゃない）に処理を分散させようと思うと、なかなか、これがめんどい。普通のコードならば、

とりあえず動くものを
ベンチ
ボトルネックをぐぎゃー

となるのだけど、分散メモリCPUの場合は、「とりあえず動くところ」までが遠い場合がある。

木とかリストみたいにポインタ（参照）でリンクするのが基本になってるデータ構造がそのまま使えない（CPUごとにアドレス違うよ）
配列とかもランダムアクセスされると、メモリ転送のコストが大きくなる
別CPUで処理する部分は、メッセージ通信とかの処理を入れないと

等々。「とりあえず動かす」レベルにするだけでも、データ構造の見直しとかが必要になる。

いまのところは、ここらへんは人力でネチョネチョやるしかないのだけど、これってなんとか言語レベルでサポートはできないかなー、というのが、最近3分くらいの思考のネタ。

で、だーっと考えつつ、↓ここらへんを読みつつ、
http://itpro.nikkeibp.co.jp/article/COLUMN/20070501/269948/?ST=develop&P=2
データ構造のほうに、並列性を記述というのは確かになんかアリっぽなー。

例えば、二分木の場合

data Tree = Node (Tree,Tree) | Leaf

こういうのがあったとして、左側と右側はデータ的には並列してるので（←あやしい言葉だなー）、

data Tree = Node ( : Tree,Tree : ) | Leaf

なんかこんな感じで、それを記述できて、こういう風に書いておくと、参照がポインタを使わないベースアドレス + オフセットという形で表された上に、コンパイラとアロケータが協力して、なんか左側と右側をメッセージ通信にイイ感じになるようなサイズ、配置にしてくれるとか、なんだかそういう素敵な。

…いや、そんなのがあって嬉しいか？実はあまり嬉しくない。並列してまで最適化したいような部分のことを考えれば、シリアライズしてるオーバーヘッドなんて結構どうでもよいので、「普通のデータ構造 + シリアライザ」でも体力と時間さえあればあんまり困らない。

困るのは…やっぱ、アクセスパターンが直線じゃない場合なんだよなー。「1byteロード → 計算 → 1byteストア」のループを並列にするのはまあ、結構気合いでどうにでもなるのだけど、「3x3」の領域に対して計算とかになると、なかなか綺麗に割れなくて、それ専用のルーチンが必要になったり、「25x25の領域にランダムアクセス」とかになると、毎回まるごと転送するのはコストが大きいし、だからといって、毎回必要なだけ転送するというのも難しく…。

なんかひとりごとだNE！ループからアクセスパターンを解析みたいなのをもうちょっと一般的にして…なんか自動化できないかな…
自動的に解析するのが無理だとしても、「アクセスパターン記述子」みたいなのを書いて、それに対する転送ルールみたいなのを書けば、なんかうまくやってくれるとかできないかなー。

…少なくとも僕にはできない。