さて、ここまで伏せてきたが賢明な方は薄々気がついていたと思う。 今回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スレッドの準備と実行に多くのステップが必要な上、スレッドの実行はデフォルトでは非同期には行…