広報 > プレスリリース > 高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功

高校生がスーパーコンピュータを使って5×5魔方陣の全解を求めることに成功

プレスリリース

平成26年2月28日

国立大学法人筑波大学

[印刷用PDF 496KB]

概要

筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次(高校1年)の杉﨑行優(すぎざき・ゆきまさ)君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。
魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算はT2K-Tsukubaの全648ノードのうち32ノードを使って行われ、最速で約2時間36分で全解を求めることができました。

1.魔方陣

魔方陣は、正方形の方陣(マス目)に、縦・横・斜めの和が同じになるよう数字を置いたものです。とくに、1からマス目の総数までの数字すべてを使ったものを指します。

魔方陣1 魔方陣2 魔方陣3
図1 魔方陣の例
マス目の数が3×3のとき、縦・横・斜めの和はすべて15になっており、解は対称のものを除くと1通りだけである。4×4では和は34で解は880通り、5×5では和は65で解は2億7530万5224通り(1970年代に発見)。6×6の解の総数はわかっていない。

2.スーパーコンピュータによる並列計算

(1) アルゴリズムの考案

魔方陣の求解は、すべての数字を「総当たり」で入れて正解かどうかを確かめていくのが基本です。しかし、たとえば5×5の場合、1列の和が65とわかっているため、1列の4マスまで埋まると残り1マスは自動的に求められ、これを総当たりから除くことができます。この考え方を「枝刈り法」といいます。
杉﨑君はこの枝刈り法をもとに、総当たりのマス目の数を25から14まで減らせることに気づきました(図2)。これは非常に重要で、総当たり数が14から15へたった1増えただけでも計算時間は数十倍になると見積もられています。今回は総当たりを14で行いましたが、これが最も少ないかどうかはわかりません。さらに減らせる可能性もあります。

image4
図2 枝刈り法をもとにした求解アルゴリズム
丸数字は総当たりで数字を入れる順番(1から25の数字そのものではない)、✓は自動的に求められるマスを表す。斜めのマスを優先的に埋めることで、自動的に求められるマスの個数をさらに増やすことができた。

(2) 並列プログラムの開発

並列型スーパーコンピュータのプログラミングでは、計算をいかに均等に各コアに振り分けるかが重要です。今回、5×5魔方陣の解を求めるにあたって、T2K-Tsukubaの512CPUコア(32ノード)を用いました。これは4.7TFLOPS(1秒間に4.7兆回の計算性能)に相当します。
魔方陣の解を求めるのに必要な計算を512コアに振り分けるために、マスタ・ワーカー方式を用いました。1コアをマスタに指定して全体の司令塔の役目を担わせます。それ以外の511コアはワーカーとしてマスタの指示に従って計算を行います。このとき、仕事の振り分け方が均等でないと、計算を早く終えてさぼっているコアが出てきてしまい、全体の計算時間が増えてしまいます。
実際の計算では、マスタがN番目(Nは0から14のいずれか)のマスまで総当たりをして、その後をワーカーに振り分け、各ワーカーはN+1番目のマスから総当たりを行います。このとき、Nの値が小さいとワーカーの「粒度」(仕事のバラつき)が大きくなってワーカーの計算時間にバラつきがでます(全体の計算時間は増える)。一方、Nの値が大きいと、粒度は小さくなってワーカーの計算時間が均等になっていきますが、マスタとワーカーの通信時間が増大するために、全体の計算時間はやはり増えてしまいます。以上のことから、Nには計算時間が最小になる最適な値が存在することになります。

3.結果

スーパーコンピュータT2K-Tsukubaを用いて並列計算を行い、5×5の魔方陣の全ての解2億7530万5224通りを求めることに成功しました。出力結果は約25GBになりました。
Nの値が3から8について計算を実行し、N=6のときに計算時間が最も短くなることがわかりました。5×5の魔方陣の全解を求めるのにかかった時間は約2時間36分でした(図3)。

図3
図3 N=3~8における実行時間
N=4~7の実行時間はわずかな差だが、N=6のときが最も短い。

また、N=3、6、8のときの各ワーカーの主要処理実行時間を調べたところ、N=3ではバラつきが大きく、N=6、8ではバラつきがほとんどないことがわかりました。また、同じくN=3、6、8のときの各ワーカーの総通信時間を調べ、N=3、6ではほぼ0時間、N=8では1時間以上かかったことが判明しました(図4)。

図4左 図4右
図4 各ワーカーの主要処理実行時間(左)と総通信時間(右)
主要処理実行時間は、N=3のときおよそ0時間から12時間とバラつきが大きかった。

4.今後の展望

筑波大学計算科学研究センターのスーパーコンピュータ「T2K-Tsukuba」は、2014年2月末で運用を終了します。2014年度からは、新たなスーパーコンピュータ「COMA」※3(こま)を導入し、「HA-PACS/TCA」との2台体制で、今後も学際共同利用プログラムを積極的に展開していきます。
杉﨑君と朴教授は引き続き、5×5魔方陣における並列計算の高速化を進めていきます。COMAの学際共同利用プログラム利用を目指して、アルゴリズムやプログラムの改良を行います。6×6魔方陣へのチャレンジは、現時点では不可能と判断しています。総当たり数を36から23まで減らすことができていますが、現在のプログラムでは150兆年かかると見積もられています。これはエクサスケールのスパコンでも54万年以上かかる計算で、事実上不可能です。

用語解説

※1 学際共同利用プログラム(平成26年度)
公募について(締切済) http://www.ccs.tsukuba.ac.jp/kyodoriyou/koubo

※2 スーパーコンピュータ「T2K-Tsukba」
2008年に稼働開始した648ノード、総演算性能95.4TFLOPS(1秒間に95.4兆回)の並列スーパーコンピュータシステム。筑波大、東大、京大の3機関で共通の仕様を用いているため「T2K」の名がついた。T2K-Tsukba は2014年2月末に運用を終了する。

※3 スーパーコンピュータ「COMA」
2014年度から導入されるメニーコア・スーパーコンピュータシステム。計算科学研究センターが開発してきたPACSシリーズの9代目(PACS-Ⅸ)。377ノードで総演算性能は960TFLOPS。そのうちCPU部分が151TFLOPS、61コアのメニーコアプロセッサ部分が809TFLOPS。

<問い合わせ先>
国立大学法人筑波大学 計算科学研究センター 広報室
TEL:029-853-6260 FAX:029-853-6260
E-mail:pr[at]ccs.tsukuba.ac.jp
※並木中等教育学校への直接の取材依頼はご遠慮ください。筑波大学計算科学研究センター広報室が窓口として対応いたします。


Top