検証
さあ、結果を検証しましょう。それぞれのアルゴリズムの主要な要素数を変更して、実行しました。結果の一例を、表形式で表します。
| 要素数 | 10000 | 20000 | 30000 | |||
| シリアル | パラレル | シリアル | パラレル | シリアル | パラレル | |
| 1回目 | 0.4060 | 6.1150 | 1.6380 | 24.0090 | 3.6510 | 54.057 |
| 2回目 | 0.4210 | 6.2410 | 1.6530 | 25.3200 | 3.8530 | 56.287 |
| 3回目 | 0.4060 | 6.2560 | 1.7010 | 25.3660 | 3.9000 | 56.474 |
| 4回目 | 0.4050 | 6.2250 | 1.6380 | 25.1940 | 3.6820 | 56.443 |
| 5回目 | 0.4210 | 6.3180 | 1.6690 | 25.3040 | 3.8070 | 56.459 |
| 平均 | 0.4118 | 6.2310 | 1.6598 | 25.0386 | 3.7786 | 55.944 |
| 処理効率 | 0.06608891 | 0.066289649 | 0.067542543 | |||
| 要素数 | 10000000 | 20000000 | 30000000 | |||
| シリアル | パラレル | シリアル | パラレル | シリアル | パラレル | |
| 1回目 | 3.4790 | 1.9350 | 7.7220 | 3.8070 | 11.384 | 5.9430 |
| 2回目 | 3.4330 | 1.8870 | 7.9250 | 3.8370 | 10.920 | 5.8820 |
| 3回目 | 3.4320 | 1.8570 | 7.3910 | 3.8380 | 10.921 | 5.8190 |
| 4回目 | 3.4320 | 1.9190 | 7.3950 | 3.8220 | 10.874 | 5.8190 |
| 5回目 | 3.4480 | 1.9030 | 7.5290 | 3.8220 | 10.921 | 5.8040 |
| 平均 | 3.4448 | 1.9002 | 7.5924 | 3.8252 | 11.004 | 5.8534 |
| 処理効率 | 1.812861804 | 1.984837394 | 1.87993303 | |||
| 要素数 | 100000 | 300000 | 500000 | |||
| シリアル | パラレル | シリアル | パラレル | シリアル | パラレル | |
| 1回目 | 2.6990 | 2.3400 | 22.7450 | 15.5390 | 52.4810 | 38.5330 |
| 2回目 | 2.6990 | 2.3240 | 21.2480 | 15.4930 | 52.4970 | 38.7670 |
| 3回目 | 2.7140 | 2.3250 | 20.9510 | 15.4150 | 52.6060 | 39.0010 |
| 4回目 | 2.7150 | 2.3870 | 21.0290 | 15.4920 | 52.4500 | 38.9240 |
| 5回目 | 2.6980 | 2.4960 | 20.9980 | 15.8210 | 52.5430 | 38.8140 |
| 平均 | 2.7050 | 2.3744 | 21.3942 | 15.5520 | 52.5154 | 38.8078 |
| 処理効率 | 1.139235175 | 1.375655864 | 1.353217652 | |||
バブルソートについては、並列化をする方が遅い結果となりました。これは、並列化して実行する処理のほとんどをクリティカルとしたため、実際には並列化が行われないことと、クリティカルエリアを実行するために待ち合わせが発生するためです。並列化をするためには、まず、クリティカルなエリアをまとめ、できるだけ短い時間に抜けるような工夫が必要です。
素数（の数）を求めると、FizzBuzzで、並列化による効果が異なります。FizzBuzzでは1.8倍の効果が出ていますが、素数（の数）を求めるでは、1.3倍にとどまっています。これは、素数の数をカウントするためにクリティカルエリア（アトミックな計算）があることと、並列化で実行されるループの中の処理が、ループの後ろほど数が多いことが原因です。
素数（の数）を求める処理では、「2以下の素数の数」「3以下の素数の数」…「100以下の素数の数」と数が進むにつれて、だんだんと調べる数が多くなります。Open MPのforディレクティブでは、1つのスレッドが実行するループの回数を制御します。例えば、全体で千回のループであれば、100回のループを10回繰り返すような動作をします。この10回の繰り返しを、並列に処理するわけです。今、50万以下の素数を求めるわけですが、これを「25万未満」と、「25万以上50万以下」の2つに分けて実行したとします。すると、「25万未満」を担当するスレッドは、「25万以上50万以下」を担当するスレッドよりも、処理の時間が圧倒的に短くなります。すなわち、いずれかのスレッドの負荷だけが上がり、負荷の平準化がされないために、効率が上がらないのです。これを、「100ずつ」に区切って5,000回のタスクに分けると、1つめのタスクと5,000個目のタスクでは処理にかかる時間が大きく異なりますが、1つめのタスクと2つめのタスクでは、わずかな差しかありません。2つのスレッドに負荷を平準化して掛けることにより、処理効率を上げることができます。今回のコードでは、こういう処理をしていないため、1.3倍の効率しか出ていません。コードを少し変更すれば、処理効率はもう少し向上します。
まとめ
この結果から、何でもかんでも並列化すれば、等しく速くなるわけではない、ということが分かります。並列化に向いているアルゴリズム、向いていないアルゴリズムがあります。また、並列化にむいているアルゴリズムであっても、十分に検討しなければ思わぬバグを作り込むことになります。事前にしっかりと調査し、コードの設計をすることが必要です。
並列化する前に
- パフォーマンスを計測し、高速化しなければならないか、検討する
- 10ミリ秒で終わる処理を5ミリ秒にしたところで、どれほどの意味があるでしょうか。1分かかるところを40秒で処理できるようにするのは、意味があるでしょう。すなわち、「何倍」という倍率よりも、体感できる時間を短くする方が大事です。
- より効率化された書き方がないか、調査する
- 例示した「素数か判定する」ルーチンは、判定に使う数は判定したい数の平方根を超えない整数まででかまいません（IsPrimeNumberFast関数を参照）。そうすると、32ビット程度の数では、並列化をする必要がなくなります。
- ここでは、「並列化に向かないアルゴリズム」の説明として、バブルソートを選びました。ソートをするなら、クイックソートやマージソートなど、より効率的なアルゴリズムがあります。
- 処理を、より単純化する
- 並列化できる箇所を明確にする
- 本文では、いくつかの並列化できない箇所を、予め廃止するか並列化しない箇所へ退避させています。コンソール出力をやめる、メモリの確保を前もって行うなどです。
- 並列に動作すると不具合を引き起こす箇所がないか、検証する
- 処理順序が一定であることに依存しないか、検証します。FizzBuzz問題を、ループ内でコンソールに出力すると、処理順序が一定ではないことが問題になります。そのため、決められた位置へ格納するというアルゴリズムに変更しています。
- 複数のスレッドで、同じ領域を書き換えることがないか、検証します（「生産者と消費者」問題）。
- 不具合を起こす箇所を一か所にまとめ、クリティカルブロックとする
- デッドロックしないように、慎重に設計します（「哲学者の食事」問題）。
- クリティカルブロックの処理時間と、並列化している箇所の処理時間を比較する
- クリティカルブロックの処理時間が長い場合、並列化をあきらめる
謝辞
本記事は、一旦ブログにて公開し、コミュニティの皆さまよりご意見をいただいて、より読みやすいように修正しました。ご協力くださった方々に、この場を借りてお礼申し上げます。
