解説

〔aについて〕
選択肢の各CPU数を式に当てはめて解いても良いのですが、ここでは対象となる処理のうち並列化可能な部分(r)を、

　907＋90＋3＝0.9

高速化率を5とした方程式を立てることでCPU数(n)を求めます。

　5 ≦ 11－0.9＋0.9n
　5 ≦ 10.1＋0.9n
　5(0.1＋0.9n) ≦ 1　
　0.5＋4.5n ≦ 1
　0.5n＋4.5 ≦ n
　4.5 ≦ 0.5n
　9 ≦ n

以上の計算より、高速化率 5 を達成するために必要はCPU数は「9個以上」とわかります。

∴a＝オ：9

この設問の並列処理におけるCPU数と速度向上率の関係を表した式を「アムダールの法則」といいます。

解説

〔bについて〕
n=5とした場合、プログラム1では次の4つの処理が行われます。

• a[2] ← a[1]＋b[2]
• a[3] ← a[2]＋b[3]
• a[4] ← a[3]＋b[4]
• a[5] ← a[4]＋b[5]

これらは、前の処理で更新した配列要素を次の処理で参照する「更新→参照」の順序になっています。上記のプログラムを2つのスレッドで並列実行した場合、以下のように2つに分割されます。

スレッド1

a[2] ← a[1]＋b[2]
a[3] ← a[2]＋b[3]

スレッド2

a[4] ← a[3]＋b[4]
a[5] ← a[4]＋b[5]

[スレッド1]の"a[3] ← a[2]＋b[3]"による a[3] の更新処理よりも先に、[スレッド2]で a[3] の参照がされる可能性があるので処理の結果が同じになる保証がありません。

∴b＝ア：更新した値が次の繰返しで参照されるので

〔cについて〕
n=4とした場合、プログラム2では次の4つの処理が行われます。

• a[1] ← a[2]＋b[1]
• a[2] ← a[3]＋b[2]
• a[3] ← a[4]＋b[3]
• a[4] ← a[5]＋b[4]

これらは、先に配列要素の参照を行った後、次の処理でその要素を更新する「参照→更新」の順序になっています。上記のプログラムを2つのスレッドで並列実行した場合、以下のように2つに分割されます。

スレッド1

a[1] ← a[2]＋b[1]
a[2] ← a[3]＋b[2]

スレッド2

a[3] ← a[4]＋b[3]
a[4] ← a[5]＋b[4]

[スレッド1]の"a[2] ← a[3]＋b[2]"による a[3] の参照処理よりも先に、[スレッド2]で a[3] が更新されてしまう可能性があるため処理の結果が同じになる保証がありません。

∴c＝ウ：参照した値が次の繰返しで更新されるので

〔dについて〕
ループ内で参照や更新が行われる配列要素 a[1]～a[n] の参照は、その前後に更新処理を伴う関係で分割実行したときの整合性が保証されません。しかし、ループ内で更新しない配列要素(a[n+1以上])の参照であれば(更新処理が行われないので)参照・更新の順序が崩れることはありません。

n はループ内で更新を行う配列要素の最大インデックスなので、1からnまでのループで更新される配列要素は a[1]～a[n] です。つまり i に加算される m が n以上 であれば、a[i+m] は必ず a[n] より後ろの要素、つまりループ内で更新が行われない配列要素になります。

∴d＝イ：m ≧ n

解説

2つ以上のスレッドに同じ配列要素の更新処理が含まれている場合、処理の前後によって結果が異なったものになってしまいます。

選択肢のインデックスの割り振りの中で、重複しているものに印を付けると以下のようになります。印が付いている部分はスレッド同士でインデックスが競合し更新処理の結果が保証されないので、並列実行ができません。唯一、スレッド同士で重複するインデックスがない「イ」の組合せのみが複数のスレッドでの並列実行が可能です。

∴イ