素数の積が回文数となるパターンを調べている時、ｖｂａでは時間が掛かり、
調べる範囲を拡げるのに限界がきた。
そこで高速化を図るため
１． コンパイラー言語 → 昔使ったＦＯＲＴＲＡＮが使えないか？
２． ４コアｃｐｕを有効に活用して、並列処理ができないか
調べてみることにした。
ｏｐｅｎＭＰというのがあり、ｃ及びｆｏｒｔｒａｎに対応しているようだ
しかも無料で。
これを使ってみることにした。
まずは導入。
最初 ＴＤＭ−Ｆｏｔｒａｎをインストールしたが、ｗｒｉｔｅ文にエラーがあるそうで、実際にうまく動かないので、
minGM-w64-ｆｏｒｔｒａｎをインストールし直した。
あらきけいすけの雑記帳
さんのページを参考に初期設定。
ソースファイルを置くフォルダーに mingw-w64.bat をコピー
ｏｐｅｎＭＰは基本的にＤＯループを明示的に並列化できるようだ。
機器の概略仕様は以下のとおり、詳しくはここ
を見てください。
CPU:Intel Core i5 4570 3.2GHz Memory:8GB OS:Windows 7 Home excel2013 vba
実行するといくつかの段階でエラーが出たのでメモ代わりに記録しておく。
１．エラーその１
コンパイルエラーにはならないが「アプリケーション実行時のソフトウェア例外（APPCRASH c00000fd)」のエラーがでた。
多数の素数（最大は約１００万個）をファイルから配列に読み混む段階で出ているようだ。
ただし、ｒｅａｄ文よりも前にある最初の実行文が全く実行されずにエラーとなる。
エラーを調べてみる
とスタックオーバーフローのようだ。指定範囲外にアクセスすると出るエラーとのこと
問題の署名:
問題イベント名: APPCRASH
アプリケーション名: openmp.exe
アプリケーションのバージョン: 0.0.0.0
アプリケーションのタイムスタンプ: 5a897892
障害モジュールの名前: openmp.exe
障害モジュールのバージョン: 0.0.0.0
障害モジュールのタイムスタンプ: 5a897892
例外コード: c00000fd
例外オフセット: 00002b73
OS バージョン: 6.1.7601.2.1.0.768.3
ロケール ID: 1041
追加情報 1: f6fd
追加情報 2: f6fdff1be24bd4a93309a009b8de72f0
追加情報 3: e0a8
追加情報 4: e0a884d85aaa560a55bf7d0eec5fdd0a
自分のためのメモ さんのページを発見。
配列を最初に宣言せずに、実行時に配列を確保することでスタック外の別領域に確保されるとのこと。
配列宣言時はallocatableで宣言し、実行時にallocateすることで行えることを知った。
大昔（約４０年前）とはかなり違う。
これで素数をファイルから読み込む時のエラーはなくなった。
２．エラーその２
実行結果がばらばら、素数の積の回文数はチェックしているようだが、
出力した値がばらばら。何のことか解らない。
調べていくと、ｄｏループを並列処理しているとき、何も指定しないと変数は共通となるとのこと
ｄｏループの添え字（ｉとかｊ）は並列処理ごとに別に確保されるようだ。
そこで共通で使っている変数を並列処理（以下「スレッド」という）ごとに独立して確保するために、
ｄｏ ループの並列処理指定（ ！＄ｏｍｐ ｄｏ ）の行に「ｐｒｉｖａｔｅ（変数１，変数２，・・）」と
指定することでそれぞれスレッド毎に独立に変数が確保されることになるようだ。
それでもうまくいかない。
３．エラーその３
回文数となる数をカウントする「ｋｏｓｕ」は共通で使う必要があり、かつ、それぞれが排他的に扱う必要がある。
このため、！＄ｏｍｐ ｃｒｉｔｉｃａｌ文をいれることにした。
単に合計をとるだけなら、reduction ＋ 指定すれば良いのだが、
何個目の回文数かそのときの素数ｍ、ｎを記録するために配列の引数として使用することから
reductionではだめだった。
これでまともな結果がｏｕｔｐｕｔされるようになった。
うまくいったソースファイルをここに乗せます。
この後に記述した、ｓｃｈｅｄｕｌｅ文を入れたソースの一例です。
４．時間比較
アルゴリズムもＶＢＡから変更し数値を数値のまま逆転させて比較することにより、ＶＢＡで行っていた
文字列としての比較よりも高速になったようだ。
コンパイルすることでＶＢＡより６倍くらい速くなり、アルゴリズムの改善＋４ｃｏｒｅによる並列実行(注１)により
ｇｆｏｒｔｒａｎで実行した場合の約１０倍程度速くなった。
表−１に計算時間を示す。
(2018/3/6追記)
注１： 表−１のgfortranの時間はＣＰＵ時間だった。
(2018/3/6追記ここまで)
表−１ ｖｂａとｇｆｏｒｔｒａｎ及びopenmpを使った並列処理 時間比較
| Ｎ番目の素数まで | 3,000 | 10,000 | 20,000 | 30,000 | 70,000 | 100,000 | 200,000 |
| 回文となる組み合わせの数 | 1,064 | 2,937 | 5,362 | 8,066 | 15,668 | 20,363 | 41,807 |
| 変数ｍ番目の最後 | 2,942 | 9,822 | 17,664 | 27,135 | 27,135 | 99,677 | 199,279 |
| 変数ｎ番目の最後 | 2,960 | 9,978 | 17,672 | 27,193 | 27,193 | 99,847 | 199,970 |
| ｖｂａ | 秒 | 45.2 | 535.4 | 2106.8 | 5,054.6 | 27,430.5 | | |
| 時：分：秒 | 0:00:45 | 0:08:55 | 0:35:07 | 1:24:15 | 7:37:10 | | |
| ｖｂａ(改良) | 秒 | | | | | 24,268.3 | 55,419.9 | |
| 時：分：秒 | | | | | 6:44:28 | 15:23:40 | |
| gfortran ディスプレイ出力 | 秒 | 9.3 | 85.0 | 327.7 | 737.9 | 4,045.6 | | |
| 時：分：秒 | 0:00:09 | 0:01:25 | 0:05:28 | 0:12:18 | 1:07:26 | | |
| gfortran ファイルに逐次出力 | 秒 | 11.6 | 111.2 | 440.4 | 1,000.1 | | | |
| 時：分：秒 | 0:00:12 | 0:01:51 | 0:07:20 | 0:16:40 | | | |
| gfortran ファイルにまとめて出力 | 秒 | 11.4 | 106.8 | 423.0 | | | 10,731.4 | 42,509.2 |
| 時：分：秒 | 0:00:11 | 0:01:47 | 0:07:03 | | | 2:58:51 | 11:48:29 |
| gfortran ファイルにまとめて出力※ | 秒 | 2.6 | 8.8 | 30.6 | 86.2 | 490.3 | 1,018.6 | 4,288.4 |
| 時：分：秒 | 0:00:03 | 0:00:09 | 0:00:31 | 0:01:26 | 0:08:10 | 0:16:59 | 1:11:28 |
※openmpによる並列処理及び回文数判断を文字列から数値に変更
その後、１０万番目までの素数の積で回文数となる場合をチェックさせてみると、
ｃｕｐが４つ共動いている状態（１００％）から順次ＣＰＵが終了（７５％→５０％→２５％→０％）
していく。
ＣＰＵの負荷にばらつきがある。
対角項を含む三角行列を計算しているようなものだから（素数ｍ番目＜＝素数ｎ番目となる素数の積）、
均等にｄｏループをＣＰＵに割り振ると
速く終わるものと最後まで稼働するものと差が出るようだ。
均等化するため、ｄｏ文の並列化指定のなかに ｓｔａｔｉｃ、ｄｙａｎａｍｉｃ，１０００〜２００００で
変化させてみた、多少ｓｔａｔｉｃよりは速くなるが、期待したほどではない。
ｇｕｉｄｅｄもためしたが、
余り差は無い。ループの数が少ないのだろうか
結果を表−２に示す。
表−２ openMPでgfortran使った schedule処理による 時間比較 スレッドは４つ
| Ｎ番目の素数まで | 30,000 | 70,000 | 100,000 |
| 回文となる組み合わせの数 | 8,066 | 15,668 | 20,363 |
| 変数ｍ番目の最後 | 27,135 | 27,135 | 99,677 |
| 変数ｎ番目の最後 | 27,193 | 27,193 | 99,847 |
| openmp-17-1.f90 | schedule( static ) | 85.96 | | |
| openmp-17-2.f90 | schedule( dynamic ) | 85.49 | | |
| openmp-17-3.f90 | schedule( dynamic,1000 ) | 85.57 | | |
| openmp-17-4.f90 | schedule( dynamic,2000 ) | 85.36 | | |
| openmp-17-5.f90 | schedule( dynamic,3000 ) | 85.36 | | |
| openmp-17-6.f90 | schedule( dynamic,4000 ) | 85.38 | | |
| openmp-17-7.f90 | schedule( dynamic,5000 ) | 84.88 | | |
| openmp-17-8.f90 | schedule( dynamic,6000 ) | 84.54 | | |
| openmp-17-9.f90 | schedule( dynamic,7000 ) | 83.15 | | |
| openmp-17-10.f90 | schedule( dynamic,8000 ) | 83.40 | | |
| openmp-17-11.f90 | schedule( dynamic,9000 ) | 81.39 | | |
| openmp-17-12.f90 | schedule( dynamic,10000 ) | 81.88 | | |
| | | | | |
| openmp-20.f90 | schedule( static ) | | 487.04 | |
| openmp-20-1.f90 | schedule( dynamic ) | | 492.39 | |
| openmp-20-2.f90 | schedule( dynamic,5000 ) | | 491.89 | |
| openmp-20-3.f90 | schedule( dynamic,8000 ) | | 492.39 | |
| openmp-20-4.f90 | schedule( dynamic,10000 ) | | 490.75 | |
| openmp-20-5.f90 | schedule( dynamic,12000 ) | | 489.25 | |
| openmp-20-6.f90 | schedule( dynamic,15000 ) | | 484.20 | |
| openmp-20-7.f90 | schedule( dynamic,17000 ) | | 480.08 | |
| openmp-30.f90 | schedule( guided ) | | 485.37 | |
| | | | | |
| openmp-40.f90 | schedule( static ) | | | 1014.83325 |
| openmp-40-1.f90 | schedule( dynamic ) | | | 1019.80969 |
| openmp-40-2.f90 | schedule( dynamic, 10000 ) | | | 1019.76294 |
| openmp-40-3.f90 | schedule( dynamic, 20000 ) | | | 1003.88202 |
(2018/03/06 追記)
表−１のgfortranの時間と表−２の時間はcpu時間であった。実時間ではない。
思い切って素数４０万番目まで計算してみた。
２０万番目までの実績から５時間くらいと思っていて、３時間半くらい過ぎたところで見たらいつの間にか終わっていた。(後で再計測すると１時間１５分程度だった)。時間を見ると１８，０００秒。約５時間。？？？
どういうことか？？ 調べてみるとプログラムの中で時間計測に使っていたのは「 call cpu_time 」だった。これはcpuの稼働時間を計測するもので
実時間では無かった。改めて表−３に実時間とＣＰＵ時間を計測したものを前回と合わせて表示する。
表−３を見るとdynamicの無指定とdyanamic,1000ぐらいの実時間が短いようだ。
時間計測を修正したプログラムの一例をここに載せます。
表−３ openMPでgfortran使った schedule処理による 実時間とＣＰＵ時間 追加比較 スレッドは４つ
| Ｎ番目の素数まで | 70,000 |
| 回文となる組み合わせの数 | 15,668 |
| 変数ｍ番目の最後 | 27,135 |
| 変数ｎ番目の最後 | 27,193 |
| 前回 ｏｒ 今回 | 前回 | 今回 |
| schedule処理 | プログラム名 | cpu-time(秒) | cpu-time(秒) | 実時間(秒) | プログラム名 |
|---|
| schedule( static ) | openmp-20.f90 | 487.04 | 486.864 | 208.48 | openmp-21.f90 |
| schedule( dynamic ) | openmp-20-1.f90 | 492.39 | 490.592 | 124.536 | openmp-21-1.f90 |
| schedule( dynamic,1000 ) | −−− | −−− | 490.966 | 124.52 | openmp-21-11.f90 |
| schedule( dynamic,3000 ) | −−− | −−− | 489.999 | 126.002 | openmp-21-12.f90 |
| schedule( dynamic,5000 ) | openmp-20-2.f90 | 491.89 | 489.828 | 128.482 | openmp-21-2.f90 |
| schedule( dynamic,8000 ) | openmp-20-3.f90 | 492.39 | 493.884 | 126.938 | openmp-21-3.f90 |
| schedule( dynamic,10000 ) | openmp-20-4.f90 | 490.75 | 491.029 | 127.671 | openmp-21-4.f90 |
| schedule( dynamic,12000 ) | openmp-20-5.f90 | 489.25 | 487.753 | 143.115 | openmp-21-5.f90 |
| schedule( dynamic,15000 ) | openmp-20-6.f90 | 484.2 | 484.508 | 173.817 | openmp-21-6.f90 |
| schedule( dynamic,17000 ) | openmp-20-7.f90 | 480.08 | 484.336 | 203.862 | openmp-21-7.f90 |
| schedule( guided ) | openmp-30.f90 | 485.37 | 486.692 | 208.916 | openmp-31.f90 |
(2018/03/06 追記ここまで)
(2018/03/07 追記)
これまでのＮ番目の素数までの実行時間を表−４にまとめた。
表−４ openMPでgfortran使った schedule処理による 実時間とＣＰＵ時間比較(スレッドは４つ)
| Ｎ番目の素数まで | 70,000 | 100,000 | 200,000 | 400,000 |
| 回文となる組み合わせの数 | 15,668 | 20,363 | 41,807 | 83,949 |
| 変数ｍ番目の最後 | 27,135 | 99,677 | 199,279 | 227,280 |
| 変数ｎ番目の最後 | 27,193 | 99,847 | 199,970 | 227,966 |
| プログラム名 | openmp-21-11.f90 | openmp-22-11.f90 | openmp-23-11.f90 | openmp-24-11.f90 |
| schedele 処理 | dynamic , 1000 | dynamic , 2000 | dynamic , 2000 | dynamic , 2000 |
| cpu time (秒) | 491 | 1,031 | 4,333 | 18,169 |
| cpu time (時：分：秒) | 0:08:11 | 0:17:11 | 1:12:13 | 5:02:49 |
| 実時間 (秒) | 125 | 260 | 1,087 | 4,555 |
| 実時間 (時：分：秒) | 0:02:05 | 0:04:20 | 0:18:07 | 1:15:55 |
(2018/03/07 追記ここまで)
|
