最速コンピュータをフル活用
小生が現在、自宅で使用しているPCはインテルCorei7-860だ。世界最速と言っても過言でないマシンである。先日、ASUSのSUPER COMPUTERなる別名を持つマザーボードと一緒に購入し、前から持っていた7年ぐらい使っているペンティアム4のPCをマザーボードごと交換して、アップグレードした。ついでに、DVDドライブ、メモリー、電源ユニットの交換も必要だったので、前からの部品がほとんど残っていない。もはやアップグレードとは言えないかもしれない。
今回、この最速PCを使わない手はないと、桂馬道を探索するプログラムを作ってみた。桂馬道とは、ある大きさの盤面で、チェスの桂馬（ナイト）がたどれる経路だけをたどり、一度通ったマスを通らずに、すべてのマス目を通る経路を見つけるというもの。有名なパズルだ。小さな盤、たとえば5×5ぐらいまでなら、人間にもその経路をつきとめることは可能だが、大きくなるとほぼ不可能である。今回挑戦したのは、8×8のマス目。つまり、本物のチェス板と同じ大きさの盤で、コンピュータの力を使って経路を探索させてみた。
実は、わたしが学生だったころ、SHARPのMZ80Bという8ビットのパソコンで、同じことをやってみたことがある。1984年、いまから約26年前だ。高級言語といえばBASICしか知らなかったころだったので、最初はBASICで作った。それがあまりにも遅く、小さな盤の探索でも時間がかった。結局、マシン語、つまりコンピュータのハードを直接叩くようなプログラムで、なんとか満足する性能を出せた。しかし、8×8の盤で結果を出すことは、結局できないでいた。
今回、プロのコンピュータソフト技師になったわたしの技量と最新のPCで、再挑戦だ。高度に技術的な内容はこのコラムにはなじまないので、大きな処理の流れや、試行錯誤の過程を書いてみたい。
探索は、コンピュータの能力を使ってやる。下手なトリックは使わないで行う方針にした。いわゆるBrute forceの方法だ。試行錯誤の過程の結果、一度確認した探索経路は2回目は行わなくてもいいように、プログラムを改善させるように処理を改善したが、これも基本的には探索をすべて行うことなので、方針からは逸脱していないと思う。
アルゴリズムの基本は縦型探索を再帰的処理で行うだけ。コンピュータサイエンスの基本だ。下のようなコードが、探索処理の中心になる。C#のコードだが、CやC++、そして、Javaの人にも分かるだろう。
private static void TryPath(int direction )
{
// step forwardd
CurPos += step;
CurStep++;
if (Board[CPos] == 0)
{
Board[CPos] = CStep;
if (CStep >= BOARD_SIZE * BOARD_SIZE)
{
ShowResult();
}
else
{
TryPath(VTopLeft);
TryPath(VTopRight);
TryPath(VDownLeft);
TryPath(VDownRight);
TryPath(HTopLeft);
TryPath(HTopRight);
TryPath(HDownLeft);
TryPath(HDownRight);
}
Board[CPos] = 0;
}
// step back
CurPos -= step;
CurStep--;
}
少し説明を付け加える。Board[]は8,8のボードのマスの状態を格納するためのアレイだ。8×8つまり、2次元だが、処理の高速化を狙って、1次元にしている。初期状態をすべて0にして、その後にナイトがたどったら、そこにたどったときのステップ数を埋めていくだけだ。後は説明は不要だろう。最初に例えば、一番上の左にナイトを進め、そこからTryPathを発行するのだ。TryPathはTryPathの中で再帰的に、実行されていく。うまくいけば、最後の空きマスに行くためのTryPathが実行され、そのときに以下の条件が満たされ、ShowResult()で盤の状態が記録される。
CStep >= BOARD_SIZE * BOARD_SIZE
さてこの単純なプログラムを実行したところ、いつまでたっても結果が出ない。Corei7-860なんから、すぐに出るだろうと思ったが出ない。確かに、7×7ならすぐに結果が出たが、8×8はまったく出なくなるのだ。そこで、まずやったのが、Corei7の能力を生かすこと。Corei7は 4coreでhyper thredingを生かして、8coreになるのだ。
ということで、4ステップまでナイトが進んだところで、8つの方向への探索をそれぞれ別々のThreadを使うように変更した。具体的なコードは書かないが、5ステップ目のTryPathの発行を、方向ごとに別々のThreadに乗せるようにしたのだ。
8Coreで8Threadなゆえ、それぞれの Threadはきれいに別の物理プロセッサに乗って走るようになり、Corei7をフル活用できることになった。実際、その変更を入れた後は、Task Managerに見える8つのCPU Usageすべてが常に90％以上を示すようになった。
さらに、結果もすぐに現れるようになった。5秒ぐらいで最初のヒット、つまりすべてのマスをたどった結果が出て、3分ぐらいで500件のヒットを達成。24年前にはできなかったことがあっさりできてしまった。
これから目指すは、すべての経路を探索すること。しかし、ここからが難しい。1時間走らせても、1000経路ぐらいしか検出できない。さらに、結果を観察すると、ヒットする経路は最初に起動された8つのThreadの内の1つだけがたどった経路のものばかりであることに気づいた。4ステップまで行ったところで、8つのThreadに分かれるが、ヒットがある経路はある1つのThreadに与えられた1方向からのものだけということだ。ほかの方向をたどった、Threadからのヒット報告は、2、3時間後に少し現れただけだった。それはそれで、そういうことかもしれないので、良しとすることにする。
性能を改善する方法として、アルゴリズムを改善することが、もっとも効果があることだが、他にアルゴリズムも知らないし、最初の方針のBrute forceで行く方針を貫くことにして、アルゴリズムは変えないことにした。そして取った方法が、キャッシュを使うことだ。
考えるに、あるステップまでたどって、残りの空きマスが同じになるような状態になることが何度もあるのではないか？ すると、その同じ空きマスを探索する処理が、何度も繰り返し実行されているだろう。同じ空きマスを探索する処理は、一度やれば二度と実行する必要がないのではないか？ それを実現するためには、一度たどったことのある空きマスへの探索の結果をキャッシュとして記録し、別の探索で同じ空きマスに出くわした時は、先の探索の結果を使うようにすればいいではないか？
ということで、最初にやったのが、Binary treeの構造を作り、そこに空きマスのパターンをキーにして、探索結果を格納するキャッシュを作るということ。これは逆に遅くなるだけで終わった。 Binary tree構造の最大の欠陥である、Treeのバランスが崩れてしまったからだ、ということはすぐに分かった。Treeの深さが異常な速さで伸びていくのが明らかだったからだ。.NETつまりマイクロソフト提供のArrayクラスに、BinarySearchと言うメソッドがあるが、これにも同じ欠点があるのか、逆に遅くなるだけだった。
実は小生、コンピュータサイエンスをしっかり勉強していない。大学は物理学科だった。コンピュータのプログラムは趣味から始めている。普通に業務ソフトを作るだけなら、コンピュータサイエンスは必要ない。必要なのは、JavaやC#などの言語。SQLは一番重要。そして、設計するなら、デザインパターンなどの設計の成功例に基づく設計パターンの知識。Binary treeだLink listだ、Arrayだなどということは、言葉だけを知っているだけでいい。実際の実装は使用するクラスライブラリが提供してくれるものを使うだけでいいからだ。.NETならマイクロソフト提供の膨大なクラスライブラリ。Javaなら、サンマイクロシステムズだろうか。
しかし、こういう種類のプログラムをやるときは、コンピュータサイエンスを知っているのと知らないのとではだいぶ違う。ということで、知らないなりにGoogleを検索した。見つけたのは、Binary treeでNGのときは、B-treeなるものを使うということだ。
B-treeはBinary treeではなく、Balanced treeの意味らしい。SQL serverをはじめ、ほとんどすべてのRelational Databaseは、このB-treeのデータ構造を使っている。ただ、この実装はかなり大変だ。C#のOpen sourceがあればそれを使おうと探すがそれも見つからない。そんなときに見つけたのが、このへんの記事。B-treeも良いが、今回のように、sortの必要がなく、検索だけがあればいい時は、hashを使うのが一番速いらしい。hashなら、microsoftが強力にサポートしているDictionaryがあるわけで、結局それを使うように修正。結果、実に簡単に、性能がアップしたものができた。
その後、64bitのCPUの能力をもっとも生かせるようにと、8×8＝64あるマスの空き状態を0、詰まった状態を1にして、binaryで表すようにして、keyそのものを64bitの数、つまりUint64にするなどして、さらに性能アップさせた。
そして結局達成できたのが、10時間ほど走らせて3000件ほどの経路をたどること。
しかし、このやり方では、すべての経路を検索するには程遠いことが分かってきた。さらに、『Knight's tour』で検索して調べて分かったのだが、すべての経路はいまだに分かっていないらしい。すべて検索したとして、それは何の役にも立たない。理解できないこともないが、世界でもっとも知られたパズルの1つで、コンピュータサイエンスの演習としても使いやすい題材だけに、いまだにすべての経路が分かっていないのは、少し疑問だ。しかし、チャレンジしがいのある題材を見つけたものだ。
いまのわたしのPCの能力では、すべての経路を見つけることは無理のようだ。しかし、実はわたしのPCのマザーボードは、ASUSのP755 WS。別名“SUPER COMPUTER”と言われるもの。 このマザーボード、NVIDIA Tesla cardsを4枚刺すことが出来る。Tesla cardは有名なGPUのカードで、カード1枚あたり、240のGPUが乗り、4枚で960GPUが乗る。結果、TESLAカードを4枚挿すことにより、 4TFopsの性能を達成できるらしい。同じ土俵で比較できるのかよく分からないが、比較のために書いておくと、2009年時点で世界最速Super ComputerはIBMのRoadrunnerというやつらしいが（＊編注）、これが1000TFLops=1PFlopsらしい。さらに、事業仕分けの時に話題になった日の丸スパコンが目指しているのが、その400倍の400ＰFlopsだ。
＊編注：現在の1位は、Crayの「Jaguar」。IBMの「Roadrunner」は3位（参考記事）。
とにかく、実はそういう計算処理をやってみたくて、ASUS SUPER COMPUTERを購入したのも事実。ということで、今回近い将来、わたしのPCに4枚のTESLAを乗せて全経路検索に再挑戦すると、予告することで終わりにする。まず、先立つものが必要だ。