現在、私は教授が授業で配ったガイドを読み返しています。学習ガイドは課題ではなく、試験で何を期待するかを知るためのものです。私は 1 つの問題を除いてすべて完了し、誰かが私を助けてくれることを望んでいました。
ここに問題があります。Tserial = n および Tparallel = n/p + log2(p) とします。ここで、時間はミリ秒単位で、p はプロセス数です。p を k 倍に増やした場合、一定の効率を維持するために n をどれだけ増やす必要があるかを示す式を見つけます。プロセスの数を 8 から 16 に倍増する場合、n をどれだけ増やす必要がありますか? 並列プログラムはスケーラブルですか?
これを理解するための助けをいただければ幸いです。
コメントと最初の回答はどちらも、一定の並列計算時間を解決するのに役立ちますが、それは一定の効率を解決することとは少し異なります。
前述のように、並列効率は、複数のプロセッサをどれだけ効果的に使用しているかによって定義されます。100% の効率は、p 個のプロセッサを使用することで p 倍のスピードアップが得られることを意味します。したがって、効率はプロセッサあたりのスピードアップの観点から定義されます。
したがって、プロセッサーの数を係数 k で増やし、問題のサイズを係数 k' で増やす場合、一定の効率を考慮する必要があります。
最初に、log(p) を含む「並列オーバーヘッド」という用語を使用せずにこれを行いましょう。
たとえば、効率は常に 1 であるため、プロセッサの数を変更しても問題のサイズに対して何もする必要はありません。
ただし、ある程度のオーバーヘッドがあるため、効率を一定に保つには、スケールアップするにつれてより大きな問題サイズに取り組む必要があります。オーバーヘッド項を使用すると、次のようになります。
ここで漸近線を見てみましょう。すでに無限の数のプロセッサーを使用している場合、効率は既にゼロであり (プロセッサーごとの作業はゼロですが、オーバーヘッドは無限であるため)、問題のサイズを一定に保つことができます。効率は変わりません。一方、p=1 のときの並列効率を取り戻すのに十分なほど問題のサイズを大きくすることはできません。これは 100% であり、オーバーヘッドのために、何をしても必ずそれより少なくなります。
また、問題のサイズを大きくするために必要な量は、プロセッサの数を増やす係数よりも常に少し多くなることに注意してください。
あなたが見ている特定のケースでは、p=8、k=2 で、問題のサイズを 2+2/3 増やす必要があります。
この作業が正しいことを願っています。
例えば、Tserial = 10ms の場合、理想世界 (効率 100%) で 2 つのプロセスで並列処理を行う場合、Tparallel (理想) は 10ms/2 = 5ms です。
残念ながら、並列処理を行うと、プロセッサ間で分散される作業を管理するための処理オーバーヘッドが発生します。
この場合、オーバーヘッドの管理にかかる時間の公式は log2(p) です。したがって、プロセッサが 2 つあり、Tserial = 10ms の場合、Tparallel は 5ms + log2(2) = 6ms になります。
上記の例を使用して、「一定の効率」とは、p を k 倍に増やした場合、Tparallel が 6ms のままになるように Tserial、つまり n をどれだけ増やす必要があるかを意味すると仮定します。
a = nを増加させる要因とする
n/p + log2(p) = na/pk + log2(pk)
n/p + log2(p) = na/pk + log2(p) + log2(k)
n/p = na/pk + log2(k)
nk - na = pk log2(k)
ka = (pk log2(k)) / n
a = k - [(pk log2(k)) / n]
p =8 かつ k = 2 の場合
= 2 - [(16 log2(2)) / n] = 2 - (16/n)
この場合、プロセッサの数が 2 倍になれば、並列プログラムはほぼ 2 倍のワークロードを処理できるため、スケーラブルです。提供 n >> 16