[急いで打ったので文がぐちゃぐちゃですし強調等もないです。すみません。]
[定期的に記事の一番下にこっそりと僕のコメントを追加しています。一応ご確認ください]
このような記事を発見しました。
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）
魔方陣の総数を求める、ということを、僕はスーパーコンピュータT2K-Tsukubaで約2時間30分で計算しましたが、この記事では一般的なコンピュータで10分で計算した、というものです。挑発的ですね。
僕のプログラムを1コア上で実行すると約200時間かかりました。(2012年ごろのAMD Opteron)
(TODO:スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?)
そして、この記事での実行環境は12コアなので、1コア換算すると実行時間は10分*12コア=120分=2時間になります。
これらから、この記事のプログラムは僕のプログラムより何倍速いか計算すると、
200/2=100倍
CPUの性能等を考えると、その記事のプログラムは僕のプログラムより数十倍高速であると言えます。
また、プログラムとアルゴリズムが公開されているので解析してみました。
高速化した理由として考えられるのは以下の3点です。
・数字が既に使用されているか否かの判定にビット演算を用いている
・1列中の数字を埋める際、残り1マスのときだけでなく残り2マスのときにも、入れる数字が列の合計と比べて正しいか判定する
・マスに入れる数のレンジを、列の合計から狭くする
以上をまとめると、
「ビット演算を用いたり、マスに入れる数字の範囲を狭めたり早めにバックトラッキングすることで、僕のプログラムと比較して数十倍高速化することができる」
と言えます。
#あー、怖かった。とんでもないアルゴリズムが考案されたのかと思った。
#"6次に対しては"そこまでつよい高速化ではないと思います。なぜなら、これを6次に適用しても、やはり全解を求めるのは非現実的だと予想できるので。
#※解の総数を求めるためには今のところ全ての解を求める方法しかないので、今のところ「総数を求める=全解をもとめる」になります。(表記が混同していますがよろしくお願いいたします)
#ビット演算による最適化などは当たり前に行っておくべきとの意見を頂きました。その通りです。スパコンを利用する前に、並列処理だけでなくプログラムの基本的な最適化手法なども学んでおくべきだったと反省しております。
#それと、個人的にはコードがとても短くて驚きました。
#Intel Core i7-4930K ってコア数が6でスレッド数が12なんですね。これも考察に入れないと Intel core i7-4930K
#もしこの記事があなたにとって印象悪く映ってしまったなら、ごめんなさい。悪気はないです。急いで書いたので尖ってしまったのかもしれません。僕の文章の書き方が下手なのかもしれません。
[定期的に記事の一番下にこっそりと僕のコメントを追加しています。一応ご確認ください]
このような記事を発見しました。
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）
魔方陣の総数を求める、ということを、僕はスーパーコンピュータT2K-Tsukubaで約2時間30分で計算しましたが、この記事では一般的なコンピュータで10分で計算した、というものです。挑発的ですね。
僕のプログラムを1コア上で実行すると約200時間かかりました。(2012年ごろのAMD Opteron)
(TODO:スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?)
そして、この記事での実行環境は12コアなので、1コア換算すると実行時間は10分*12コア=120分=2時間になります。
これらから、この記事のプログラムは僕のプログラムより何倍速いか計算すると、
200/2=100倍
CPUの性能等を考えると、その記事のプログラムは僕のプログラムより数十倍高速であると言えます。
また、プログラムとアルゴリズムが公開されているので解析してみました。
高速化した理由として考えられるのは以下の3点です。
・数字が既に使用されているか否かの判定にビット演算を用いている
・1列中の数字を埋める際、残り1マスのときだけでなく残り2マスのときにも、入れる数字が列の合計と比べて正しいか判定する
・マスに入れる数のレンジを、列の合計から狭くする
以上をまとめると、
「ビット演算を用いたり、マスに入れる数字の範囲を狭めたり早めにバックトラッキングすることで、僕のプログラムと比較して数十倍高速化することができる」
と言えます。
#あー、怖かった。とんでもないアルゴリズムが考案されたのかと思った。
#"6次に対しては"そこまでつよい高速化ではないと思います。なぜなら、これを6次に適用しても、やはり全解を求めるのは非現実的だと予想できるので。
#※解の総数を求めるためには今のところ全ての解を求める方法しかないので、今のところ「総数を求める=全解をもとめる」になります。(表記が混同していますがよろしくお願いいたします)
#ビット演算による最適化などは当たり前に行っておくべきとの意見を頂きました。その通りです。スパコンを利用する前に、並列処理だけでなくプログラムの基本的な最適化手法なども学んでおくべきだったと反省しております。
#それと、個人的にはコードがとても短くて驚きました。
#Intel Core i7-4930K ってコア数が6でスレッド数が12なんですね。これも考察に入れないと Intel core i7-4930K
#もしこの記事があなたにとって印象悪く映ってしまったなら、ごめんなさい。悪気はないです。急いで書いたので尖ってしまったのかもしれません。僕の文章の書き方が下手なのかもしれません。
コメント
コメント一覧 (10)
並列計算は通信時間がどうしてもかかるので、cpu timeを見ると （コア数＊1coreの時間） より結構大きくなります。並列計算では通信時間が大きな悩みの種です。
（かなり勉強されているようなので、すでにご存知で違うことを心配されているならごめんなさい）
さらに計算機自体が違うため、比較するにはちょっと使いづらいですね。
もし並列化効率や並列化率を見たいのなら、T2K上で256とか128とかすこし並列数を減らして計算する必要があるかと思います。1coreの実行時間もあると面白いけど、ジョブの制限時間で終わらなければ余分なI/Oが必要になって同じ条件で時間を測るのは難しいですね。
今後の参考にもなるし、余裕があればジョブをぶん投げてみてもいいかも？
私もきちんとどこかで勉強したわけじゃなくほぼ独学みたいなものなので、頓珍漢なこと言ってるかもしれません。
高１でスパコンを使えるレベルにいるというのは本当にすごいと思います。
能力を活かして楽しんでください！
http://dictionary.goo.ne.jp/leaf/jn2/100143/m0u/
> ＞スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?
>
> 並列計算は通信時間がどうしてもかかるので、cpu timeを見ると （コア数＊1coreの時間） より結構大きくなります。並列計算では通信時間が大きな悩みの種です。
> （かなり勉強されているようなので、すでにご存知で違うことを心配されているならごめんなさい）
今回の僕のプログラムでは、与えるパラメータをうまく設定すれば通信時間をほぼ0時間にすることができました。また、その場合の実行時間が約2時間30分でした。
> さらに計算機自体が違うため、比較するにはちょっと使いづらいですね。
> もし並列化効率や並列化率を見たいのなら、T2K上で256とか128とかすこし並列数を減らして計算する必要があるかと思います。1coreの実行時間もあると面白いけど、ジョブの制限時間で終わらなければ余分なI/Oが必要になって同じ条件で時間を測るのは難しいですね。
> 今後の参考にもなるし、余裕があればジョブをぶん投げてみてもいいかも？
残念ながら、T2K-Tsukubaの運用は先月で終了してしまい、今は解体中かその後です。
もし実行ができたら、アルゴリズムが何倍程度高速化したのか検証できて面白そうなんですがね…残念です。
>
> 私もきちんとどこかで勉強したわけじゃなくほぼ独学みたいなものなので、頓珍漢なこと言ってるかもしれません。
> 高１でスパコンを使えるレベルにいるというのは本当にすごいと思います。
> 能力を活かして楽しんでください！
自分の作ったプログラムは、i7-ivy 4.4GHz で、35分かかりました。（GCC4.81)
コア数を考慮しても、２倍以上早いです。
自分のプログラムは、アルゴリズムはまったく異なるのですが、対象解の除去に時間がかかっているので、もう一工夫できそうです。
ご報告ありがとうございます。
masaさんが用いたアルゴリズムというのはどのようなものなのでしょうか?
また、「対象解」については、更なる研究・考察が必要だと考えています。
実は、5次魔方陣の総数が一番初めに求められたのは、1973年のことなのです。
当時のコンピュータは今のものよりも相当処理性能が低く、また、コンピュータ資源は貴重で満足に使用できなかったかもしれません。
1976年1月のScientific Americanにその報告書が載っているようなのですが、僕はまだ入手できていません。
しかし、それを解説した文献がいくつかあり、それらによると、1種類の5次魔方陣にはそこから導ける対象解が数万通りあるようです。
これは割と大きな計算量削減に繋がりますから、その文献を早く入手したい次第です。
早速のコメント有難うございます。
自分のアルゴリズムは、25! (階乗) 通りある １～２５の数字の順列を作り枝狩りをしながら 一番内側のループにたどり着き、そこで、対称解かどうかチェックするという物です。
１個目を中央に、２個目を左上に置きますが、１，２，３の３個の数字の位置関係を利用した対称解の除去を行っています。（実際はもう少し複雑ですが。）
この方法だと、中央が１の場合と、左上が１の場合の計算時間が長く、最長と最短で２４倍計算時間に差がでます。（解の個数も多いです。）
そのため各スレッドに動的にジョブを割り振るようにしました。
リンク先のプログラムを見ると、この当たりもOpenMP が面倒を見てくれるのですね。（自分はOpenMP初心者なので、方法を知りませんでした。）
高校生の使ったアルゴリズムは、25^25通りを生成するループで、枝狩りを行っているのではないかと推測しています。(意外と遅いので。。。）
リンク先のアルゴリズムは、基本的には25^25通りを探すアルゴリズムなのですが、ループ毎に、とり得る値の上限、下限をチェックする事によって、高速化していると判断しました。
このアイデアは、自分のアルゴリズムに取り込む事ができそうなので、試す予定です。前半のループほど、広い範囲の値をとるので効果が大きそうです。
一番内側は、２４，２５の２値しか取らないので、無意味ですが。
前回書いた対称解の除去は、重い if 文が２２個あるのですが、無視できる程度の時間しかかかっていない事が確認できました。（入れ子になっているので。また事前の枝狩りの方が重要という事ですね。）
リンク先のプログラムより高速化できましたら、報告させていただいてよろしいでしょうか。よろしくお願いします。
masa
の部分、明らかに間違っていました。
(25-n)^12 通りでしょうか。。。で、ｎを大きくする工夫がされているようです。
新しいアイデアを２つ入れて、64bit コンパイラに変更したところ、
約２倍に高速化できました。
i7-ivy 4.4GHz で、912秒になりましたが、まだ、magicsquare.exe よりも３０％遅いです。ただ、これ以上の高速化は限界と思います。
#pragma omp for schedule(dynamic, 1024)
の使い方と、32bit/64bit コンパイラの癖を理解できたのが、成果でしょうか。
TDM-GCCでは、32bitの場合変数を大域変数として、64bitの場合局所変数として
宣言した方が高速でした。
では、では。
(全解の出力はＨＤ律速になるので行っておりません。オプションで出力可能。）
基本的なアルゴリズムは、多重forループで、外側は２５通り、最内側は２通りのループになるようなアルゴリズムです。
ただし外側の２つのループは展開し、openmp でマルチスレッド化しています。
この対称解除去の方法は効果的で、コードもシンプルになりました。
では、では。
ご報告ありがとうございます。
今回の場合は、5次魔方陣の中央の値の範囲を1から13に限定し、
さらに回転・反転を1通りとして数えることにより、
計算量を約16分の1にした、ということですね。
5次魔方陣は、そのような対称性を用いると、最終的には
32通りを1つとしてまとめることができるようになります。
これは、5次魔方陣の総数を初めて求めたRichard Schroeppelが学生に書かせた
レポートに記されています。
私は、彼に直接連絡を取り、そのレポートを手に入れることができました。
その内容については、後で記事にしたいと思います。