parallel-processing - プログラムが正常に並列化されたかどうかを確認する方法は?

Question

並列マシン上で実行されるプログラムは、プロセッサー数 P の増加に対して次の効率値を持つように測定されます。

P 1 2 3 4 5 6 7
E 100 90 85 80 70 60 50

上記の結果を使用して、スピードアップ グラフをプロットします。

グラフを使用して、プログラムが正常に並列化されたかどうかを説明します。

P E    Speedup
1 100% 1
2  90% 1.8
3  85% 2.55
4  80% 3.2
5  70% 3.5
6  60% 3.6
7  50% 3.5

これは昨年の試験問題で、スピードアップを計算してグラフをプロットする方法を知っています。ただし、プログラムが正常に並列化されていることを確認する方法がわかりません。

Answer 1

アムダールの法則

I think the idea here is that not all portion can be parallelized.

たとえば、プログラムが 1 つのプロセッサ コアを使用して 20 時間を必要とし、1 時間の特定の部分を並列化できない場合、残りの有望な 19 時間 (95%) は並列化できます。このプログラムを並列実行するには、最小実行時間をその重要な 1 時間未満にすることはできません。したがって、スピードアップは最大 20 倍に制限されます

この例では、スピードアップは 6 プロセッサで最大 3.6 に達しました。したがって、平行部分は約 1-1/3.6 で約 72.2% です。