いろいろと基本的なところから細かいベンチマークをとりながら再構築をしてみたが、最初に思っていたよりもずっとLoad/Storeが遅い事に気がついた。 今回、駒の効きが八方向にあるので８要素の配列を使っていたのだが、コンパイラの最適化でレジスタに格納し…

ひっくり返す関数が悪い訳ではなかったようだ。 とにかく条件分岐のコストが高過ぎるのが原因らしい。 一生懸命最適化したつもりの関数も全く速くならなかったが、関数内の条件分岐を削っただけで５倍速くなった。 枝刈りはどうしても条件分岐を使わない訳に…

とりあえずαβカットを入れた1SPU版の探索プログラムまで作成してどの程度の効率か調べてみた。 しかし中間評価も手の善し悪しによる並べ替えも入れていないにも関わらずScrZebraの半分以下の探索性能だった。 これは一度全ての場所でおけるかどうかを調べ、…

反転の方法を考えていたが、今ひとつよいアイデアがないので前回の置ける位置の走査時に、すべての方向の結果の論理和をとるのではなく、8要素のベクトルに格納して利用することにした。 例えば上方向へひっくり返すには以下のようにした。 vector unsigned …

このコードがどれくらいの効率を持っているかだが、Zebraの日本語訳のサイトには「200-300クロック」と書いてあったように記憶している。 前回のコードを８方向分に膨らませ（全てのステップで直前のビット演算への依存が高いので、IPCを稼ぐために２方向分…

N-queen問題を解いてみる事で、SPUを128bitの論理回路として用いる事で、ある程度の速度のプログラムが書ける事は分かった。 次にどのような目標を立てるかということだが、以前から少し興味のあった話題として、オセロのプログラムを作成してみたい。 最初…

さて、ここまで伏せてきたが賢明な方は薄々気がついていたと思う。 今回N-queens問題を例題として使ったのは 電通大がN-Queens問題の最高記録を更新 という記事をうっすらと覚えていたからである。 この記事で紹介されていたサイトはリニューアルされてunrea…

それでは実際のベンチマークを見てみる。 盤の大きさを12から18まで変化させ、SPUスレッド数を1から6まで変化させた場合の経過時間を計測した。単位は秒である。またこの表を、スレッド数1に対して何倍速くなったかとして表現した。同じようなアルゴリズムに…

eocitiesにアップロードしたのでようやくソースコードを公開する。ライセンスはパブリックドメインとしておく。 cellqueen_v1.zip ビルドは $ unzip cellqueen_v1.zip $ cd cellqueen_v1 $ makeとし、実行は $ ./cellqueen [盤のサイズ] [SPUの数]とする。li…

並列化プログラムで、並列効果に最も関係するのは「どのように作業を分割するか」ということである。 作業の分割単位が小さければ6つのSPUに平等に仕事をさせやすくなるが、分割や結果の総合にオーバーヘッドが生じる。逆に大きく分割すれば並列化のオーバー…

前回SPUスレッドの非同期実行のためのクラスで、わざわざmailboxを用いた通信用のメソッドを用意した理由は、DMAを通じた通信よりもmailboxの方が早いだろうと目論んだからだ。しかしこれがくせ者で、mailboxは各SPUに32bit単位で1つしかなく、それが塞がっ…

計算のための実行カーネルができたので、これを並列化することが目標となるが、言うのは簡単だが実行するのは非常に大変だった。 なんと言ってもlibspe2ではSPUスレッドの準備と実行に多くのステップが必要な上、スレッドの実行はデフォルトでは非同期には行…

CellBEに限らない、一般的な話をすると、並列計算を行う際に重要な事は、 シングルスレッドで高い性能を出すコードを書く事 アーキテクチャに最適な並列化を行う事 である。前者は意外と忘れられがちで、特にコンパイラやOSなどシステムに密接に関係している…

Cellのアーキテクチャには以前より興味があったが、PS3を購入するだけの動機がなかったので触れる機会がなかった。 正確にはIBMのCellエミュレータをPS3発売以前にインストールして簡単なサンプルプログラムをビルドするくらいはしたのだが、私の環境では遅…

私はスラッシュドット・ジャパンでkahoというハンドルネームで活動している者ですが、PS3 Linuxを用いたCellBE用並列プログラムの作成のためのメモとしてこの日記を活用することにしました。 主に個人的メモと、あわよくば先人からのアドバイスをもらえれば…