掲載情報：日刊スポーツ／共同（2/28）、朝日新聞（3/1）、茨城新聞（3/1）、読売新聞（3/2）、日経新聞（3/2）、東京新聞（3/2）
プレスリリース
概要
筑波大学計算科学研究センターは、全国共同利用施設として、一般公募による「学際共同利用プログラム」※1を実施しています。平成25年度に、茨城県立並木中等教育学校4年次（高校1年）の杉﨑行優（すぎざき・ゆきまさ）君の申請が採択されました。杉﨑君は筑波大学計算科学研究センターの朴泰祐教授と共同研究を進めた結果、スーパーコンピュータ「T2K-Tsukuba」※2を使った並列計算により、5×5の魔方陣の全ての解を求めることに成功しました。
魔方陣とは、正方形のマス目に、縦・横・斜めの合計が同じになるよう数字を置いたものです。5×5の魔方陣の全解は2億7530万5224通りあることがすでにわかっています。杉﨑君は「枝刈り法」を改良した求解アルゴリズムを考案し、スパコンに並列計算させるためのプログラムを開発しました。朴教授は、並列データの収集や並列化に関する詳細なアドバイスを行いました。並列計算はT2K-Tsukubaの全648ノードのうち32ノードを使って行われ、最速で約2時間36分で全解を求めることができました。
1．魔方陣
魔方陣は、正方形の方陣（マス目）に、縦・横・斜めの和が同じになるよう数字を置いたものです。とくに、1からマス目の総数までの数字すべてを使ったものを指します。
図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で行いましたが、これが最も少ないかどうかはわかりません。さらに減らせる可能性もあります。
図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 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 各ワーカーの主要処理実行時間（左）と総通信時間（右）
主要処理実行時間は、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/gakusai/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
※並木中等教育学校への直接の取材依頼はご遠慮ください。筑波大学計算科学研究センター広報室が窓口として対応いたします。