2008-01-01から1年間の記事一覧
前回のエントリーで説明した書き方では大変分かりにくいので、図で示す。 Aのような配置のとき、128bitレジスタではBに示しているように白と黒をそれぞれ上位と下位64bitにして別々にした形で持っている。 この配置のうち、一番上の一行を16bit整数にする場…
このようにしてパターンの評価値を得た後、使用しなければ意味がないのだが、その評価値の検索で無駄な処理をしてしまっては意味がない。 広大なメモリがあればO(1)でデータを得られるようテーブルをメモリ上に持っておけばよいが、それは無理なのでO(log(N)…
しばらくSPUと関係ない話ばかりだったので、コードを載せて少し話を進めたい。 Move orderingにおいて、盤面のパターンをどのように認識するかという問題について、私のプログラムでは16bitの整数に変換することで実行しているのだが、16bit全部のテーブルを…
細かい改良を施しつつ、ゆっくりと更新しているのだが、現在のプログラムでのFFO endgameベンチマークは以下の通り。 それほど探索性能は悪い訳ではないのだが、枝狩りの性能が悪いので結果として非常に時間がかかっている。 現在はαβカットとmove ordering…
余り時間がないので詳細は後にするとして、周辺配列と対角線について評価を行い、その評価値によって次手を並び替えして検索する方法を試みた。 方法としては以下の通り 残り14, 15, 16手のランダムな配置を作成する そのときの配置を記録 完全読みを行い、…
他の「まともな」オセロプログラムより終盤解析が遅い理由は，次の階層の最善手を探す並び替えがお粗末だからだ． とりあえず４辺と対角線の配置に付いてはパターン化し，有利なものを選択するようにすることは最低限しておこうと思う． ８つの石の配置は3^8…
現在の探索では次の階層の配置の評価を行うときと，新しく配置可能な位置を求めるときとで同じ処理を二回している． これは無駄なのでここを改善すれば速度が上がるだろうと期待していた． しかしやってみると全く反対の結果になった． なぜこのようになるか…
細かい機能の最適化をあきらめて、探索アルゴリズムを実装してhttp://www.radagast.se/othello/ffotest.html FFO endgame test suiteにある終盤解析を実際にやってみた。 最前手は正解を出力したが、そこまでの時間は以下の通りだった。 手の順位付けを最低…
このプログラムのアルゴリズムには標準的な手法のみを使用しているのだが、一つの配置を128bitの値一つで示すことで白番と黒番を64bitシフトで簡単に入れ替える事ができる。 そのためMaxノードとMinノードで関数を分ける必要はない。 ゲームが終了したかどう…
昨日条件分岐が問題ではないかと言ったが、実際は条件分岐を削ると特定の（軽い）パターンを繰り返すために速くなったように見えただけだった。 そして考えてみれば、5Mnpsというのは1ノードあたり640クロックの消費ということになる。 着手可能位置の検出が…
一生懸命最適化したつもりでまたベンチマークをとってみたが，やはり非常に遅い． 4-5Mnps程度の速度しかでない． この原因として思い当たるのが，探索関数の再帰呼び出しだ． 関数を再帰的に呼び出すと，そのとき使用していた変数をメモリに待避させなけれ…
以前SPUで乱数を使うためにメルセンヌツイスターを実装した． この時はただコードを書いただけで全く効率化していないものだったので，少し調べてみたらMMXを使用したSFMTというものがあるそうで，速いらしいとソースコードをダウンロードしてみた． しかし…
以前やったN-Queen問題では，コードのコンパクトさを期待してCで全て書いていた． しかし，現在は全てC++で書くようにしている． なぜかというと，単純に表記が自由だということもあるが，128-bit代入で警告を出さないことと，参照を用いた関数をインライン…
いろいろと基本的なところから細かいベンチマークをとりながら再構築をしてみたが、最初に思っていたよりもずっと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用並列プログラムの作成のためのメモとしてこの日記を活用することにしました。 主に個人的メモと、あわよくば先人からのアドバイスをもらえれば…
