T2K-Tsukubaを用いて高校生が5×5魔法陣の解を求めることに成功 - 筑波大

筑波大学は2月28日、同大学の計算科学研究センターが全国共同利用施設として一般公募により行っている「学際共同利用プログラム」において、平成25年度に採択された茨城県の高校生の「5×5の魔方陣のすべての解を求める」計算において、スーパーコンピュータ「T2K-Tsukuba」を使った並列計算により解を求めることに成功したと発表した。

成果は、茨城県立並木中等教育学校4年次(高校1年)の杉﨑行優君、筑波大 計算科学研究センターの朴泰祐教授らの共同研究チームによるものだ。

魔方陣は、正方形の方陣(マス目)に、縦・横・斜めの和が同じになるよう数字を置いたものだ。特に、1からマス目の総数(3×3マスなら1～9、4×4マスなら1～16、5×5なら1～25という具合)までの数字すべてを使ったものを指す。例えば画像1のようにマス目が3×3の時は1～9までの数字をすべて使って縦・横・斜めの和がすべて同じになるように配置すると、画像1のように15になる1通りの解がだけが存在する(左右や上下を反転させた、対称のものを除く)。画像2の4×4の場合は、縦・横・斜めの和は34で解は880通り、画像3の5×5では和は65で解は2億7530万5224通り(1970年代に発見された)。6×6以上の解の総数はわかっていない。

魔方陣の求解、つまりアルゴリズムはすべての数字を「総当たり」で入れて正解かどうかを確かめていくのが基本である。しかし、例えば5×5の場合、1列の和が65とわかっているため、1列の4マスまで埋められれば残り1マスは自動的に求められ、これを総当たりから除くことが可能だ。この考え方は「枝刈り法」と呼ばれる。

杉﨑君はこの枝刈り法をベースに、総当たりのマス目の数を25から14まで減らせることに気づいたという(画像4)。これは非常に重要で、総当たり数が14から15へたった1増えただけでも計算時間は数十倍になると見積もられているからだ。今回は14で総当たりが行われたが、実はこれが最少かどうかはわからないそうで、これ以上さらに減らせる可能性もあるとしている。

画像4は、今回の枝刈法ベースの求解アルゴリズムをもう少し詳しく解説したもの。丸数字は総当たりで数字を入れていく順番(1～25の実際に入れる数字そのものではない)、チェックマークは自動的に求められるマスを表す。斜めのマスを優先的に埋めることで、自動的に求められるマスの個数をさらに増やすことができたという。

続いてのポイントが、スーパーコンピュータによる「並列計算プログラム」の開発だ。今回、T2K-Tsukubaが使われているわけだが、これは2008年に稼働開始した648ノード、総演算性能95.4TFLOPSの並列スーパーコンピュータである。

並列型スーパーコンピュータのプログラミングでは、計算をいかに均等に各コアに振り分けるかが重要だ。今回、5×5魔方陣の解を求めるにあたって、T2K-Tsukubaの512CPUコア(32ノード)が用いられた。これは4.7TFLOPSに相当するという。

魔方陣の解を求めるのに必要な計算を512コアに振り分けるために、マスク・ワーカー方式が採用された。これは、1コアを「マスク」に指定して全体の司令塔の役目を担わせ、それ以外の511コアは「ワーカー」としてマスクの指示に従って計算を行うという方式である。均等に仕事を割り振れないとどうなるかというと、計算を早く終えて手持ちぶさたになってしまうコアが出てきてしまい、全体の計算時間が増えてしまうというわけだ。

実際の計算では、マスクがN番目(Nは0から14のいずれか)のマスまで総当たりをして、その後をワーカーに振り分け、各ワーカーはN+1番目のマスから総当たりを行う。この時、Nの値が小さいとワーカーの「粒度」(仕事のバラつき)が大きくなってワーカーの計算時間にバラつきが出てくる(全体の計算時間は増える)。一方、Nの値が大きいと、粒度は小さくなってワーカーの計算時間が均等になっていくが、マスクとワーカーの通信時間が増大するために、全体の計算時間はやはり増えてしまう。以上のことから、Nには計算時間が最小になるバランスの取れた最適な値が存在するというわけだ。

Nの値については3から8で計算が実行された。そして、N=3、6、8の時の各ワーカーの主要処理実行時間が調べられたところ、するとN=3ではバラつきが大きく、N=6、8ではバラつきがほとんどないことがわかった。また、同じくN=3、6、8の時の各ワーカーの総通信時間を調べ、N=3、6ではほぼ0時間、N=8では1時間以上かかったことが判明している(画像5～7)。よって、N=6の時に計算時間が最も短くなることがわかった。最終的に5×5の魔方陣のすべての解、2億7530万5224通りを求めることに成功。出力結果は約25GBとなった。5×5の魔法陣の全解を求めるのにかかった時間は約2時間36分となっている。

なおT2K-Tsukubaは2014年2月末に運用を終了したあと、2014年度からは新たなスーパーコンピュータ「COMA(こま)」が導入され、「HA-PACS/TCA」との2台体制で、今後も学際共同利用ブログラムを積極的に展開していくとしている。COMAはメニーコア・スーパーコンピュータシステムで、計算科学研究センターが開発してきたPACSシリーズの9代目(PACS-IX)となる。性能は377ノードで総演算性能は960TFLOPS。その内CPU部分が151TFLOPS、61コアのメニーコアブロセッサ部分が809TFLOPSという具合だ。

また、杉﨑君と朴教授は引き続き、5×5魔方陣における並列計算の高速化を進めていく予定だ。COMAの学際共同利用プログラム利用を目指して、アルゴリズムやブログラムの改良を行うという。ちなみに6×6魔方陣へのチャレンジは、現時点では不可能と判断している。総当たり教を36から23まで減らすことができているが、現在のプログラムでは150兆年かかるという計算だ。

エクサスケールのスパコンでも54万年以上かかる計算であり、量子コンピュータが実現して(量子コンピュータとうたわれているものもすでに販売されてはいるが)コンピュータの計算速度が別次元のレベルで飛躍的に向上するか、これまでにない新たなアルゴリズムを考案する必要があるようである。