WebCLを使ったブラウザでの高速計算について
人類の進歩により，Webブラウザ上でのアプリケーションはさらにデスクトップと変わらないものになると思われる．その一部として，莫大な計算量が要求されるような計算幾何学のアルゴリズムなども，ブラウザ上で実行できるとガンガンやばいことになる．パソコンやタブレットなどで高速計算を行う場合，一般的な方法が，GPUを使った並列計算である．それをブラウザなどのJSでできるようにするのがWebCLである．この技術の現在について調査した．
進歩した人類であるAさんは，Flashの船のゲームに飽き，スマートフォン上で青と緑に分かれて地点(ポータル)の取り合いをするゲームを始めた．Aさんは自分が優位に立つために，大量(近未来なので5万点程度)のポータルの緯度経度を収集し，データとして持っている．しかし，Aさんには体力がなく，ポータル同士を大量にリンクさせ，我陣営を固めようとすると移動距離の問題が起こる．そのため，点の集まりの中からできるだけ距離の近い二点をたくさん探して，それを戦略に役立てることにした．
問題の概要
これは，最近接点探索問題の応用としてとらえられます(クラスターに分けるとか木構造のインデックスを貼るとかいろいろ方法はありますが，WebCLが使える手頃な事例がこれだったので)．点同士の距離を全部計算して，近いものを選ぶというのが原始的なアルゴリズムですが，点の数の二乗に比例する計算量がかかってしまいます．このため，すごい人が点の数と点の数の対数を掛けた数に比例するアルゴリズムを考案し，これで大分楽になりましたが，それでも私のMacbook Pro Retina 2012の計算能力ではブラウザでは一番近い二点を探すのに27.6秒程度かかってしまいます．これでは敵陣営に先を越されてしまいます(近未来なのでCPUも速くなっているのではというのはいいっこナシ)．
解決方法
そこでWebCLです．このアルゴリズムは，変更を加えることで並列に計算ができます．このため，ビデオカードの爆発的な処理能力を活用できる可能性があります．
WebCLの現況
WebCLの規格は1.0.0の正式版があるが，現時点で標準で実装されているブラウザはない．しかし，Firefox及びSafariで拡張が出ており，またnode.jsでも使うことができる．このあたりはこちらをご覧ください．
今回は，node.jsの実装がうまく動かなかったため，Firefoxの拡張を利用した．これについてはNokia Researchが頑張っており，昔のスマートフォンが好きな私としてはとても嬉しい限りである．
テストには，先の最近接点探索問題のソースコードを利用した．
過渡期のWebCL
WebCLは思ったより過渡期だった．正式な規格になる過程でAPIの引数の仕様がゴロゴロ変わってプリミティブではなく配列を受け取るようになったり，名前空間がCLからWebCLになったり，その上で元々WebCLの名前空間だったものがwebclになったりしているようだ．テスト用のソースコードは正式な規格の出る直前に出たもので，いろいろと違っていた．チュートリアルを参考に直したら動いたため，Nokia Researchの実装は信頼できる．
また，なんだかよくわからないのだが，Mac OS XのOpenCLの実装とNokia Researchの実装の相性が悪い．具体的にはfabsなどの基本的な関数が動かない．ただ，使っているのがfabsだけだったため，絶対値はさすがに自力で計算した．かくして最近接点の探索に成功した．
WebCLはやっぱり速い
テスト用のソースコードではJSとWebCLの速度比較をできるのだが，GPUがあまり速くない(Ivy Bridgeのオンボード)ため，点が1000個程度だと思ったより速度の差が出ない．このため1万から10万まで計測した．今回はテストで大まかなことがわかれば良いので，複数回の測定などはしていない．
見ての通り，60000個以上で30倍程度の差が出ている．これは速い．検証環境のJavaScript/Firefox(Ivy Bridge 3.1GHz 1コア)とWebCL(Intel HD Graphics 4000 1.1GHz 16ユニット)の比較をすると，FLOPSの理論値(CPUはSandy Bridgeのものを参考)でCPUは24.8GFLOPS, GPUは281.6GFLOPSのため，オーバーヘッドやJavaScriptエンジンの実行速度を考えるとまあ妥当な数値だろう．
ということで
WebCLのテストを行い，その威力を見てみた．まだ環境が整っていないが，確実に普及するのではないか．
長期的な視点として，Webサービスはデータベースとのインタフェースとしてどんどんライトな方向性にシフトしていき，計算能力は各個人のスマートフォンなどの端末が担うことがありうるのではないか．ユースケースとして出したIngressなどでは既に計算量の必要なクエリが存在しており，あのGoogleでさえ負荷の問題が生じている．このような事例は今後増えると考えられるため，その打開策の一つとして，クラウドなどの中央集権的な情報処理からスマートデバイスでのそれなりな高速計算への移行というのはありうる．
