並列計算の並列性がCPUの数が増えるほど上がる？

質問

並列計算をMPIを用いて行っているのですが、

CPUを２個使ったの時に掛かった計算時間を１として、
４、８、１６　
と使用CPU数を増やしていくと、計算速度が
１．５、１０、２０
と、CPU数以上に伸びていきます。

普通、CPU数以上に早くなる事は無いと思っていたのですが、１つ当たりのCPUで使用するメモリ、配列サイズが少なくなったせいで計算速度が上がることがあった、あり得る事なのかな？と思ったのですが・・・実際にCPU数よりも計算速度の速度比が上がる事はあり得るのでしょうか？

計算結果をみると、正しいです。

回答No.4

ki073 · ベストアンサー

＞１つ当たりのCPUで使用するメモリ、配列サイズが少なくなったせいで計算速度が上がることがあった、

CPUに内蔵されているキャッシュメモリに収まる程度にアクセスする配列のサイズが小さくなったときにはあり得ます。プログラムの高速化のテクニックの1つです。大きな配列を端から端まで何度も読み書きしているプログラムの場合に効果があります。

MPIでCPUに振り分けているのを、1つのCPUで順次実行するようにプログラムを書き換えると速度が上がるはずですので確認できます。

並列化ができているようですので、もしGPUとopenACCが利用できるのであればかなり速くなるように思います。

お礼

回答有難うございます。

確かに１６CPUだと、一つに割り振られる配列数がかなり少なくなりますので、キャッシュメモリに収まるかもしれません。

今回、ＧＰＵとＣＰＵ並列の速度比較テスト中です。
差分計算ではあるのですが、計算時間が最も掛かるＦＯＲループからＩＦ文を取り除けないので、どこまで早くなるのか・・・ＧＰＵは思ったよりも万能ではない、と感じています。

回答No.6

kimamaoyaji

パイプラインの予想演算で、規則的なパターン例えばコーデックの様な物は失敗は少ないです。
一方不規則な演算では予測してパイプラインで並列演算をしても、予測が外れる場合が多くなります。
具体的にどうと言うのは私レベルでは説明が難しいですが、CPUベンチマークPASSMARK
http://www.cpubenchmark.net/cpu_list.php
Core i5 4670K@3.4GHz　7801
Core i7 4770@ 3.4GHｚ　9954
Pentium G3430 @ 3.30GHz 3378　　　　　　　　　　HT無しTBなし
Core i3-4130 @ 3.40GHz 4858X(3.3/3.4)=4715 HT有りTBなし
においてHTを搭載していない、PentiumとCore i3もしくはCore i5とCore i7の同じCPU数で比較してみてHT搭載の方が、クロック当たりの性能が上になります、HTは３GHｚのCPUが理論上1.5X2の筈なんですが、それ以上の効果が出る事から、スレッド数が多いほど最大限の効率を出していると言えます、つまり処理するスレッド（CPU数）が多いほど演算効率が良いと言えるのではないでしょうか、でなければインテルがHT機能を付けた事が無意味と言う事になります。
どの演算でという事はPassmarkのベンチを実際にPentiumとCore i3で行って比較するしかありません、このペンチは有料で、実は私の場合試用期間が過ぎているので試せませんので、どの演算の部分という事は検証できなく、お伝えできません。

お礼

回答有難うございます。
HT機能が計算を早くしているのですね・・・。使用しているのはXeonなのでその効果もあるのでしょうね。

回答No.5

ki073

No.4です。

＞ＧＰＵは思ったよりも万能ではない、と感じています。

確かにそう思います。私自身はopenACCを使っていますので、CPU用に書いたプログラムをほとんど修正なしにGPU用プログラムにできるので、GPUとの比較をよくしますが、GPUの方が遅い場合がほとんどです。
書かれているようにループの中にif分があるとかなり苦しいです。見かけ上の計算量が十倍程度増えてもif分が取り除けるようであれば、そのコードの方がかなり速かったりします。ご参考に。

回答No.3

kimamaoyaji

１CPUでの計算速度が問題で、演算を１CPUで行うと１つのタスクでパイプライン処理による演算がコケると、再演算になりタイムロスが生じます、それを解消するためにインテルは１CPUで２スレッド演算が出来るようにHT（ハイパー・スレッディング）を行い演算速度の向上を行っているので、１CPUでのロスタイムが大きい時は、マルチCPU、マルチタスクの分散処理の方が早く演算が求められる場合があります。
理想的状況では、１CPUの能力XCPU数を超える事はありません。

お礼

＞理想的状況では、１CPUの能力XCPU数を超える事はありません。

今回が例外的なのか当方では判断できません・・・ロスタイムを生じているかどうか、どうやって判断すれば良いのでしょうか？

回答No.2

parts

長時間にわたる高度なデータ演算で且つマルチスレッド最適化がされているものあれば普通のことです。後は、いくつのプロセッサに最適化しているかだけの問題ですよ。

答えとしては、処理内容によります。というのが正しいのかな？

これは、スレッド粒度とタスクの関係によるものです。１＋１の計算を２つのプロセッサで分離して2倍になるかということと同じです。また、１＋２の結果に１００を掛けなさいで、性能は2倍になるでしょうか、下手に投機的な処理が働き２つのコアで１＋２と出ていない結果A×100をされたら、処理を差し戻され、その分のクロックを失います。
その逆です。要は、処理が膨大な時にプロセッサに割り振る処理の内容をどれだけの粒度で与えるかによって、プロセッサ数倍以上の性能を発揮することがあるのです。

例えば、質問者様がリンゴ16個が入った箱のリンゴを一人で、検品し8つの箱に分けなさないと言われたとしましょう。大きさで特大、大、中、小の4種類と傷あるなしも、大きさで判断し、8つに分けるのです。

さあ、頑張って、箱は100箱あります。

何時間で終わるでしょうか？
その作業をする人が二人になると、どれだけ早くなるでしょうか？
4人になると・・・。
8人なら、16人なら・・・。

これを如何に早く終わらせるかは、それを指揮する人がどのような区分け方法を考えるかによります。プログラミングであれば、例えば最初に届いたリンゴの箱の中身を、１～16番まで決めて、１からひとつずつ大きさを確認し、その後、傷を見て、そして箱に分けるのが、普通です。

しかしまず、傷があるかないかだけで箱を一つ使って選別し、もう一度箱に戻し、大きさを次に分ける方法でも良い。

そもそも、100箱を調べるなら数箱を手分けして、いっぺんにやる方法もあるでしょう。それに選別の仕方でいくつかのステージ分けをすることもできます。

これが答えです。

例えば、例えば仕分け班が本来4人一組だと効率的な作業を、二人でやっていたなら、Aの作業が終わった、次にBの作業が必要になります。その都度準備が必要です。物差しと専用のめがね（ルーペ）がそれぞれ必要だと仮定した場合、その持ち替えだけで時間が掛かります。

しかし、4人になると、Bの作業は別の二人が行います。そうなると、物差し係とめがね係がそれらを交換しなくとも作業できるようになり、時間短縮になります。8人になると、4人1組の組が増えるだけですから単純に作業時間はその倍数になります。

この場合は、たぶん４人で一連のグループが終わる設計であると思われますが、１つの作業が終わったタイミングで、内容の入れ替えを行う例えば、着替えが必要だとしましょう。だとしたら、その時間は処理には含まれませんが、着替えるために時間が掛かります。Waitとなるのです。

しかし、専業の人がいれば、そこに渡せば次の処理が行われます。
だから、待ちはゼロとなり、その待っていた分の時間が無くなるため、速度は倍速以上になります。

ただし、今回は100箱の箱だったとして、100組以上（例えば200組）のスタッフが作業をしても、速度は上がりません。１＋１を２つのプロセッサで行っても速度が向上しないのと同じ原理です。

これは、一般に長時間同じ処理（ループ）演算を分散して行えるように設計されたプログラムではよく起きることで、個人であれば動画エンコードや編集などが該当するぐらいしかありませんので、あまり知られていません。スレッドの粒度は、Hyper Threadingが登場した頃には、よく言われていましたけど、今では知らない人も多いですし、かなり自動化もすすでいますから、開発者でさえも理屈は知らない場合が多いのです。

いかがでしょうか？

お礼

丁寧な回答ありがとうございました。
すみません、あまり私の知識不足で仰る意味がよく分からなかったのですが、
早くなることもあるとのこと、良かったです。

回答No.1

aokii

CPU数よりも計算速度の速度比が上がる事はあり得ません。

お礼

ありがとうございます。