HOME»基本情報技術者平成26年春期問題»午後問3
基本情報技術者過去問題 平成26年春期 午後問3
⇄問題文と設問を画面2分割で開く⇱問題PDF問3 ソフトウェア
プログラムの並列実行に関する次の記述を読んで，設問1～3に答えよ。
プログラムを並列に実行する方法として，スレッドを使用した並列実行がある。スレッドを使用した並列実行では，プログラムの中で並列実行が可能な部分を抽出して複数の処理に分割し，分割した処理を別々のスレッドとして同時に実行する。
スレッドによる並列実行の例を，図1に示す。プログラムAは，一つのプロセスとして実行され，データ作成，計算処理，結果出力の順に処理が行われる。ここで，計算処理はn個の処理に分割して並列実行が可能であり，分割した処理を異なるスレッドで並列に実行した結果は，スレッドを使わずに計算処理した実行結果と同じであるとする。計算処理では，スレッドの生成と実行を行い，全てのスレッドの終了を同期処理で待つ。各スレッドでは，分割した計算処理(部分計算処理)を行う。
プログラムAを実行するコンピュータの構成は，性能が同じである複数のCPUと各CPUからアクセス可能な共有メモリで構成されているマルチプロセッサとする。生成された複数のスレッドは，異なるCPUに割り当てられて同時に実行され，各スレッドは共有メモリでデータを共有する。マルチプロセッサにおけるスレッドとCPU，共有メモリの関係を，図2に示す。ここで，データを転送するバスの競合は無いものとする。
プログラムを並列に実行する方法として，スレッドを使用した並列実行がある。スレッドを使用した並列実行では，プログラムの中で並列実行が可能な部分を抽出して複数の処理に分割し，分割した処理を別々のスレッドとして同時に実行する。
スレッドによる並列実行の例を，図1に示す。プログラムAは，一つのプロセスとして実行され，データ作成，計算処理，結果出力の順に処理が行われる。ここで，計算処理はn個の処理に分割して並列実行が可能であり，分割した処理を異なるスレッドで並列に実行した結果は，スレッドを使わずに計算処理した実行結果と同じであるとする。計算処理では，スレッドの生成と実行を行い，全てのスレッドの終了を同期処理で待つ。各スレッドでは，分割した計算処理(部分計算処理)を行う。
設問1
次の記述中の に入れる正しい答えを，解答群の中から選べ。
マルチプロセッサによる並列実行で得られる理想的な高速化率Eは次の式で求められる。
E＝11－r＋rn
n：CPUの数 (n≧1)
r：対象とする処理のうち，並列実行が可能な割合 (0≦r≦1)
図1のプログラムAにおいて，データ作成，計算処理，結果出力の処理時間の割合が7：90：3の場合，単一のCPUで実行したときと比べた高速化率を 5 以上にするには，CPUが最低a個必要である。ここで，スレッドの生成処理などの並列実行に伴うオーバーヘッドは考慮しない。
マルチプロセッサによる並列実行で得られる理想的な高速化率Eは次の式で求められる。
E＝11－r＋rn
n：CPUの数 (n≧1)
r：対象とする処理のうち，並列実行が可能な割合 (0≦r≦1)
図1のプログラムAにおいて，データ作成，計算処理，結果出力の処理時間の割合が7：90：3の場合，単一のCPUで実行したときと比べた高速化率を 5 以上にするには，CPUが最低a個必要である。ここで，スレッドの生成処理などの並列実行に伴うオーバーヘッドは考慮しない。
a に関する解答群
- 5
- 6
- 7
- 8
- 9
- 10
解答選択欄
- a:
解答
- a=オ
解説
〔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数と速度向上率の関係を表した式を「アムダールの法則」といいます。
選択肢の各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数と速度向上率の関係を表した式を「アムダールの法則」といいます。
設問2
次の記述中の に入れる正しい答えを，解答群の中から選べ。
プログラムの一部を複数の処理に分割して並列に実行するためには，プログラムの中から並列実行が可能な部分を抽出する必要がある。並列実行が可能なループの例を，図3に示す。図3は，iのループに関してループを四つに分割し，分割したそれぞれのループの処理をスレッドとして並列実行する場合である。ここで，配列のデータはスレッド間で共有され，変数iはスレッドごとに確保されるものとする。
プログラムの中から並列実行が可能な部分を抽出する場合，並列に実行してもデータの更新と参照の順序が変化しないことを保証する必要がある。図4に示すプログラム1～3を，iのループに関して複数のループに分割し，分割したそれぞれのループの処理を並列に実行する場合の並列実行可能性について考える。ここで，配列は十分に大きいものとする。
プログラム1は，ループの中でb，並列実行できない。プログラム2は，ループの中でc，並列実行できない。プログラム3は，m の値が不明の場合には並列実行できないが，dであることが保証されていれば並列実行は可能である。
プログラムの一部を複数の処理に分割して並列に実行するためには，プログラムの中から並列実行が可能な部分を抽出する必要がある。並列実行が可能なループの例を，図3に示す。図3は，iのループに関してループを四つに分割し，分割したそれぞれのループの処理をスレッドとして並列実行する場合である。ここで，配列のデータはスレッド間で共有され，変数iはスレッドごとに確保されるものとする。
プログラム1は，ループの中でb，並列実行できない。プログラム2は，ループの中でc，並列実行できない。プログラム3は，m の値が不明の場合には並列実行できないが，dであることが保証されていれば並列実行は可能である。
b，c に関する解答群
- 更新した値が次の繰返しで参照されるので
- 更新した値が次の繰返しで再び更新されるので
- 参照した値が次の繰返しで更新されるので
- 参照した値が次の繰返しで再び参照されるので
d に関する解答群
- m ≧ 0
- m ≧ n
- m ≦ 0
- m ≦ n
解答選択欄
- b:
- c:
- d:
解答
- b=ア
- c=ウ
- d=イ
解説
〔bについて〕
n=5とした場合、プログラム1では次の4つの処理が行われます。
∴b＝ア：更新した値が次の繰返しで参照されるので
〔cについて〕
n=4とした場合、プログラム2では次の4つの処理が行われます。
∴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
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]
- スレッド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]
∴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]
- スレッド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]
∴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
設問3
図5に示すプログラム4は，配列 a で更新する要素を示すインデックスの値が配列 ip で間接的に決定される。この配列 a のような更新を含むプログラムは，配列 ip の値によっては並列実行できない場合があるので注意が必要である。プログラム4を，図5のように i のループに関して複数のループに分割し，分割したそれぞれのループの処理をスレッドで並列実行するとき，並列実行可能な ip[i](i＝1，2，…，20) の値として適切な答えを，解答群の中から選べ。
解答群
解答選択欄
解答
- イ
解説
2つ以上のスレッドに同じ配列要素の更新処理が含まれている場合、処理の前後によって結果が異なったものになってしまいます。
選択肢のインデックスの割り振りの中で、重複しているものに印を付けると以下のようになります。
印が付いている部分はスレッド同士でインデックスが競合し更新処理の結果が保証されないので、並列実行ができません。唯一、スレッド同士で重複するインデックスがない「イ」の組合せのみが複数のスレッドでの並列実行が可能です。
∴イ
選択肢のインデックスの割り振りの中で、重複しているものに印を付けると以下のようになります。
∴イ