ushiroadParallelArrayを試す

これは2012年9月時点での情報です。
現在、Mozilla Firefoxでは並列計算を行うための ParallelArray 型の実装が進められています。早速この危険そうなドッグフードを試してみました。

Firefox 17 編

Firefox 17 (11月リリース予定)には、ParallelArray がプラグイン不要で実装されています。現在のところ、これは実際には並列計算を行わないハリボテなのですが、今からこれでプログラムを書いておけば、本物の並列計算がサポートされた暁には自動的にプログラムがとんでもない速さになります。

と言いたいところですが、上記のような行為は全く推奨できません。なぜかというと、現在Firefox 17に入っているParallelArrayは、本物の並列計算に対応できないようなコードも平然と通してしまうからです。
例えば、["xx", "yy", "zz"] という配列にmapをかける以下のようなプログラムを考えます。 

var pa = new ParallelArray(["xx", "yy", "zz"]);

var prefix = "Hello";
pa.map(function(el) {
  prefix = prefix + "!";
  return prefix + el;
});
↓ 結果 
["Hello!xx", "Hello!!yy", "Hello!!!zz"]

並列化の対象が数値ではなく文字列で、しかもmap に渡す関数の外側にある変数を参照した上に書き換えています。これを並列化できたら凄い事ですが、まあ無理でしょう（次で述べるRiver Trailでは勿論失敗します）。しかし、そういったチェックは無く、動くべきでないコードが動いてしまいます。

ということで、Firefox 17 のParallelArrayは「体験版」ですらなく、ハリボテであることを承知の上でも使うべきではありません。現時点で並列計算を試したい場合は、下記の Intel River Trail を使う方が良いでしょう。

River Trail 編

River Trail は Intel がFirefox向けに開発しているプラグインで、これをインストールすると本物の並列計算をサポートしたParallelArrayが利用可能になります。River Trail版のParallelArrayを使うためにはプラグインのインストールに加えて、付属のJavascriptライブラリも読み込む必要があります。

基礎レベル知識:

まず、最も簡単な例を挙げます。
[各要素に10を足す]

var pa = new ParallelArray([0, 1, 2, 3, 4]);
pa.map(function(el) {
  return el + 10;
});
↓ 結果 
[10, 11, 12, 13, 14]

Reduceもあります。ただし、現在の実装ではReduceは並列化されず、内部で普通のJSが走るだけです。

pa.reduce(function(a, b) {
  return a + b;
})
↓ 結果 
10

上の例ではmapに実数が一つずつ渡されましたが、実数の2つ組や3つ組が欲しい場合もあります（複素数、ベクトル、RGB色など）。勿論それも可能です。

[3次元ベクトルの長さを求める]

var pa = new ParallelArray([[1, 1, 1], [2, 3, 4], [6, 7, 8]]);
pa.map(function(el) {
  return Math.sqrt( el[0] * el[0] + el[1] * el[1] + el[2] * el[2] );
});
↓ 結果 
[1.7320507764816284, 5.385164737701416, 12.206555366516113]

map の結果も入れ子（配列の配列）にすることができます。

[RGB色の反転]

var pa = new ParallelArray([[255, 255, 0], [0, 128, 0], [0, 128, 255]]);
pa.map(function(el) {
  return [ 255 - el[0], 255 - el[1], 255 - el[2] ];
});
↓ 結果 
[ [0, 0, 255], [255, 127, 255], [255, 127, 0] ]

ところで、mapの結果を普通の配列のような記法で書きましたが、実はこれは普通の配列ではない（ParallelArrayにmapをした結果はParallelArrayになる）ので、普通の配列のようにアクセスできません。これの扱い方は後で書きます。

実践レベル知識:

partition

先程入れ子の配列をParallelArrayのコンストラクタに渡す例を挙げましたが、このときParallelArrayが内部で配列の構造を調べるため、非常に低速です。
そこで、まず入れ子になっていない（フラットな）TypedArrayでParallelArrayを構築して、partition メソッドで後から入れ子にする、という方法を採ります。

var fa = new Float32Array(9);
fa.set([255, 255, 0, 0, 128, 0, 0, 128, 255]);

var pa = new ParallelArray(fa);
pa.partition(3).map(function(el) {
  return [ 255 - el[0], 255 - el[1], 255 - el[2] ];
});
↓ 結果 
[ [0, 0, 255], [255, 127, 255], [255, 127, 0] ]

partition(3) とすると、フラットな配列が3つごとにグループ化されます。

要素の取得

やっとmapの結果を取り出せる時が来ました。ParallelArrayがネイティブで実装されれば普通の配列と同じように扱えるようになるでしょうが、現時点では、get メソッドを使う必要があります。
フラット（入れ子になっていない）の場合は

pa.get(0);

などとします。
入れ子の場合は、各レベルのインデックスを配列に詰めて渡します。

pa.get([2, 0]); // 2番目のグループの0番目

しかし、これは低速です。そこで、partition を行った時とは逆に、配列をフラットに戻してからアクセスします。フラット化後のインデックスの計算は自分で行う必要があります。

var pa_f = pa_map_result.flatten();
pa_f.get(3);

応用: aobenchのParallelArray化

aobench screenshot

実践的なサンプルを、ということで Fujita Syoyo 氏のaobenchをParallelArray化してみました。aobenchは簡単なモンテカルロ・レイトレーシングのプログラムで、まず視点から１次レイをキャストし、オブジェクトにぶつかった地点から多数(デフォルトで64本)の２次レイをキャストして遮蔽関係を調べます。１次レイの計算には元々ほとんど時間がかからないので、ここは従来通り直列で計算し、２次レイに関する情報をParallelArrayに詰めて並列計算する、という設計にしました。（図1）

aobench parallel
図1 aobenchの並列化

１次レイが物体にぶつかると、レイと対応するピクセルの座標（xとyを一つの値に詰め込んでsxsyとした）、ぶつかった面の向き（Nx, Ny, Nz）、ぶつかった位置（Px, Py, Pz）、そして２次レイの方向を決めるための乱数列（2×レイ本数）を一組としてParallelArrayに追加します。
map 後はピクセル座標とピクセル輝度が出てくるので、これを回収してフレームバッファに書き込みます。尚、図では4つのサブピクセルの計算結果を全て回収していますが、同じピクセル内であっても、あるサブピクセルの１次レイは物体に衝突したが別のサブピクセルは衝突しなかった、というケースがあるので、必ず全てのサブピクセルが配列に入っているとは限りません。

肝心のベンチマーク結果は

通常: 5779.5 ms
Parallel: 1249.3 ms
(4回平均, MacBook Air 11inch Mid 2012, Corei7)

ということで、4.6倍の高速化になりました。 苦労してプログラムを書き換えて4.6倍、というのは用途によっては微妙かもしれませんが、メニイコアCPUならもっと感動的に速くなるかもしれません（持ってないので試せません）

Demo, source

注意

ここまで、いかにも手軽に並列化できるような書き方をしましたが、実のところ結構な苦行です。以下に（現時点での）注意点を挙げます。

2012-09-19 ushiroad