はじめに

N-queens problem

Cellのアーキテクチャには以前より興味があったが、PS3を購入するだけの動機がなかったので触れる機会がなかった。
正確にはIBMのCellエミュレータをPS3発売以前にインストールして簡単なサンプルプログラムをビルドするくらいはしたのだが、私の環境では遅くて使い物にならなかったし、開発効率が悪かったのでインストールしただけだった。
最近安価なモデルが発売された事、DLNAに対応し、DivXも再生できるようになったこと、Blu-rayのレンタルも始まりそうな事など、プログラミングに挫折しても利用価値が十分にあるという判断で購入することにした。

まず開発環境のインストールをしなければならない。この辺りの記事はウェブ上に無数にあるので詳しくは書かないが、Yellow Dog Linuxをインストールした。
最初から、メモリに余裕がないのでXは立ち上げず、リモートからssh接続でコードを書くつもりだったのでディストリビューションは何でもよかったのだが、HDMI接続のせいか、Ubuntuのインストールが失敗したため次善の策として選択した。無線LANが使えると聞いていたのだが、成功していない。そのため、PS3 Linuxを使用するときだけケーブルで接続しなければいけないという間抜けな状態だが、やむを得ない。

さて、CellBEでどのような開発をするかだが、浮動小数点でベクトル計算をするのであれば、それなりのテーマを持っている人がやれば当然一般的なCPUよりも高い性能が出るだろうし、既にいくつも例がある。
自分の日常的な仕事としてその必要性がなく（HMMやMCMCに使いたい気はあるが）、あくまでホビー用として考えるとき、私が取り組もうと思っている事はAIやロジックにおける並列計算だ。
より具体的で果てしない目標をぶち上げるとすれば、並列化した囲碁プログラムの実装と言ってしまおう。

インオーダーで分岐予測も貧弱なSPUでは並列化しても効率はたかが知れていると言われても仕方がない。
しかしロジックもやりようによってはベクトル化することで効率を上げる事ができる。またSPUのベクトル処理命令には論理演算や整数計算も含まれており、これらを活用したら意外と効率の高い処理ができるのではないかと期待してよいのではないだろうか。

最初から複雑なロジックを実装するのは無理があるし、SPUの命令も理解していないのでトライ＆エラーで進めていくことにする。
まず私がターゲットとしたのはN-queens問題だ。
N-queens問題とはNxNのボードに互いに効き筋に入らないようにチェスのクイーンを配置する問題だ。
この問題を選択した理由は

  • 問題の分割が容易で、分割された問題同士は独立
  • ビット演算を用いる事でSPUでベクトル演算による効率化が可能

ということにある。

実際にやってみると思わぬ困難に出くわすことになったのだが、コードとともに進めていきたい。