基本情報技術者 2014年春期午後問03

プログラムの並列実行に関する次の記述を読んで、設問1〜3に答えよ。

　プログラムを並列に実行する方法として、スレッドを使用した並列実行がある。スレッドを使用した並列実行では、プログラムの中で並列実行が可能な部分を抽出して複数の処理に分割し、分割した処理を別々のスレッドとして同時に実行する。　スレッドによる並列実行の例を、図1に示す。プログラムAは、一つのプロセスとして実行され、データ作成、計算処理、結果出力の順に処理が行われる。ここで、計算処理はn個の処理に分割して並列実行が可能であり、分割した処理を異なるスレッドで並列に実行した結果は、スレッドを使わずに計算処理した実行結果と同じであるとする。計算処理では、スレッドの生成と実行を行い、全てのスレッドの終了を同期処理で待つ。各スレッドでは、分割した計算処理（部分計算処理）を行う。

↩設問1

　プログラムAを実行するコンピュータの構成は、性能が同じである複数のCPUと各CPUからアクセス可能な共有メモリで構成されているマルチプロセッサとする。生成された複数のスレッドは、異なるCPUに割り当てられて同時に実行され、各スレッドは共有メモリでデータを共有する。マルチプロセッサにおけるスレッドとCPU、共有メモリの関係を、図2に示す。ここで、データを転送するバスの競合は無いものとする。

設問1：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。　　マルチプロセッサによる並列実行で得られる理想的な高速化率Eは、次の式で求められる。　

E = \frac{1}{1 - r + ( \frac{r}{n} )}

　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：オ

解説

解答の導き方

求めるのは、単一のCPUで実行した場合と比べて高速化率を5以上にするために必要なCPUの最小数です。CPU（Central Processing Unit：プログラムの命令を処理する装置）の数を、問題文の式の

n

に当てはめます。

まず、処理時間の割合「7：90：3」は、データ作成、計算処理、結果出力の順です。合計は

100

なので、計算処理にかかる時間は全体の

90%

です。本文には「計算処理はn個の処理に分割して並列実行が可能」とあります。したがって、並列実行が可能な部分の割合

r

は

0.9

です。

一方、データ作成と結果出力は並列実行できる部分として示されていません。合わせて全体の

10%

なので、式の

1 - r

に当たります。CPUを増やしても、この部分の処理時間は短くなりません。

高速化率の式に

r = 0.9

を入れると、次のようになります。

E = \frac{1}{1 - 0.9 + ( \frac{0.9}{n} )} = \frac{1}{0.1 + \frac{0.9}{n}}

高速化率を5以上にする条件は、次のとおりです。

\frac{1}{0.1 + \frac{0.9}{n}} \geq 5

分母は正なので、両辺を整理すると、

0.1 + \frac{0.9}{n} \leq \frac{1}{5} = 0.2

\frac{0.9}{n} \leq 0.1

よって、

n \geq 9

となります。実際、

n = 9

のときは、

E = \frac{1}{0.1 + \frac{0.9}{9}} = \frac{1}{0.1 + 0.1} = 5

です。CPUは整数個なので、高速化率を5以上にする最小の数は9個です。

誤りやすいポイント

$r$ に、並列実行できる計算処理の割合である $0.9$ ではなく、並列実行できない部分の割合 $0.1$ を入れてしまうことがあります。式の説明では、 $r$ は「並列実行が可能な部分」の割合です。
データ作成、計算処理、結果出力の割合を取り違えないようにします。計算処理の割合が $90%$ です。
CPUを増やすと全体の処理時間がCPU数に反比例して短くなる、と考えるのは誤りです。短縮されるのは並列実行できる部分だけで、並列実行できない $10%$ は残ります。
「5以上」なので、高速化率がちょうど5になる場合も条件を満たします。 $n = 9$ で高速化率がちょうど5になります。

FAQ

Q: CPUを増やし続ければ、高速化率も際限なく大きくなりますか？
A: いいえ。並列実行できない部分の処理時間は残ります。この問題では全体の

10%

が残るため、CPUを非常に多くしても高速化率は最大で10に近づきます。

Q: スレッドとは何ですか？
A: スレッドは、プログラムの処理を分けて実行する単位です。本文では、計算処理を複数に分け、それぞれを別のスレッドで同時に実行しています。

Q: この計算で、スレッドの生成にかかる時間を含めないのはなぜですか？
A: 問題文で、スレッドの生成処理などの並列実行に伴うオーバヘッド（本来の計算以外にかかる追加の時間）を考慮しないと指定されているためです。

関連キーワード: 並列処理、高速化率、CPU、スレッド、逐次処理

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問2：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。　　プログラムの一部を複数の処理に分割して並列に実行するためには、プログラムの中から並列実行が可能な部分を抽出する必要がある。並列実行が可能なループの例を、図3に示す。図3は、iのループに関してループを四つに分割し、分割したそれぞれのループの処理をスレッドとして並列実行する場合である。ここで、配列のデータはスレッド間で共有され、変数iはスレッドごとに確保されるものとする。

　プログラムの中から並列実行が可能な部分を抽出する場合、並列に実行してもデータの更新と参照の順序が変化しないことを保証する必要がある。図4に示すプログラム1〜3を、iのループに関して複数のループに分割し、分割したそれぞれのループの処理を並列に実行する場合の並列実行可能性について考える。ここで、配列は十分に大きいものとする。　プログラム1は、ループの中でb、並列実行できない。プログラム2は、ループの中でc、並列実行できない。プログラム3は、mの値が不明の場合には並列実行できないが、dであることが保証されていれば並列実行は可能である。

b, cに関する解答群　ア：更新した値が次の繰返しで参照されるので　イ：更新した値が次の繰返しで再び更新されるので　ウ：参照した値が次の繰返しで更新されるので　エ：参照した値が次の繰返しで再び参照されるので　 dに関する解答群　ア：m ≧ 0 　イ：m ≧ n 　ウ：m ≦ 0 　エ：m ≦ n

模範解答

b：ア、c：ウ、d：イ

解説

解答の導き方

並列実行とは、複数の処理を同時に進めることです。ループ（同じ処理を繰り返す構造）を並列実行するには、ある繰返しの結果を別の繰返しが必要としないかを確かめます。

問題文には、並列に実行しても「データの更新と参照の順序が変化しないこと」を保証する必要があるとあります。配列（複数の値を番号で管理する入れ物）はスレッド（プログラム内で処理を進める実行単位）の間で共有されるため、ある繰返しが書き換えた値を、別の繰返しが読む場合は注意が必要です。一方、変数

i

はスレッドごとに確保されます。そのため、ここでは

i

ではなく、配列

a

の値の読み書きに注目します。

プログラム1

ループは

i = 2

から始まり、各繰返しで

a [i - 1]

を読み、

a [i]

に書き込みます。

繰返し	読み取る値	書き込む値
$i = 2$	$a [1]$	$a [2]$
$i = 3$	$a [2]$	$a [3]$

i = 2

の繰返しで更新した

a [2]

を、次の

i = 3

の繰返しが読み取ります。したがって、

i = 2

の処理が終わる前に

i = 3

の処理を進めると、必要な値を正しい順序で読めるとは限りません。

これは、選択肢の「更新した値が次の繰返しで参照される」に当たるため、bはアです。

プログラム2

ループは

i = 1

から始まり、各繰返しで

a [i + 1]

を読み、

a [i]

に書き込みます。

繰返し	読み取る値	書き込む値
$i = 1$	$a [2]$	$a [1]$
$i = 2$	$a [3]$	$a [2]$

i = 1

の繰返しが読む

a [2]

は、次の

i = 2

の繰返しで更新されます。順番に実行すれば、

i = 1

は更新前の

a [2]

を読みます。しかし、並列実行では

i = 2

が先に

a [2]

を更新し、

i = 1

がその更新後の値を読んでしまう可能性があります。

つまり、「参照した値が次の繰返しで更新される」ため、cはウです。

プログラム3

各繰返しは

a [i + m]

を読み、

a [i]

に書き込みます。ループ全体では、書き込み先は

a [1]

から

a [n]

です。

m \geq n

であれば、どの繰返しでも読み取り先の添字は次の範囲になります。

i + m \geq 1 + n = n + 1

つまり、読み取り先はすべて

a [n + 1]

以降です。ループが書き込む

a [1]

から

a [n]

とは重ならないため、ある繰返しが書いた値を別の繰返しが読むことはありません。したがって、選択肢の中では

m \geq n

が並列実行を可能にする条件です。dはイです。

誤りやすいポイント

プログラム1とプログラム2の依存関係を逆にすること
プログラム1では、先の繰返しが更新した値を次の繰返しが読みます。プログラム2では、先の繰返しが読んだ値を次の繰返しが更新します。どちらも順序の影響を受けますが、読み書きの順番が逆です。
$i$ がスレッドごとに分かれていれば、並列実行できると思うこと
$i$ が別々でも、共有されている配列の要素を複数の繰返しが読み書きすれば、値を扱う順序が変わる可能性があります。
$m \geq 0$ なら安全だと思うこと
例えば $m = 1$ では、繰返し $i = 1$ が読む $a [2]$ を、繰返し $i = 2$ が更新します。単に $m$ が0以上というだけでは、読み取り先と書き込み先が重ならないとは限りません。

FAQ

Q: 配列の値を読むだけでも、並列実行の問題になりますか？
A: 読むだけなら、別の繰返しがその値を書き換えない限り、順序の問題は起きません。プログラム2のように、ある繰返しが読んだ値を別の繰返しが更新する場合は、どちらが先に実行されるかで読み取る値が変わる可能性があります。

Q: プログラム3で、読み取り先が書き込み先と重ならないことが重要なのはなぜですか？
A: 読み取り先と書き込み先が重ならなければ、別の繰返しによる更新が読み取り値に影響しません。そのため、繰返しの実行順序を変えても結果が変わりません。

Q: 「配列は十分に大きい」とあるのは何のためですか？
A: 配列の端を超えて読み書きする問題を考えなくてよいようにするためです。この設問では、配列の大きさではなく、読み取り先と書き込み先が重なるかどうかを判断します。

関連キーワード: 並列処理、スレッド、ループ依存、データ依存、共有メモリ

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問3：

問題文を見る

　図5に示すプログラム4は、配列aで更新する要素を示すインデックスの値が配列ipで間接的に決定される。この配列aのような更新を含むプログラムは、配列ipの値によっては並列実行できない場合があるので注意が必要である。プログラム4を、図5のようにiのループに関して複数のループに分割し、分割したそれぞれのループの処理をスレッドで並列実行するとき、並列実行可能なip[i]（i = 1, 2, …, 20）の値として適切な答えを、解答群の中から選べ。

解答群

模範解答

イ

解説

解答の導き方

プログラム4では、各回の処理で「

a [i p [i]] \leftarrow b [i]

」を行います。つまり、配列

a

のどの要素を書き換えるかは、配列

i p

の値で決まります。

図5では、ループを4つのスレッドに分けています。スレッド1は

i = 1, \dots, 5

、スレッド2は

i = 6, \dots, 10

、スレッド3は

i = 11, \dots, 15

、スレッド4は

i = 16, \dots, 20

を担当します。スレッドは別々の処理を同時に進めるため、異なるスレッドが同じ

a

の要素を書き換えると、どちらの値が最後に残るかが不確かになります。このような問題をデータ競合といいます。

したがって、確認するのは、別々のスレッドが同じ添字の

a

を書き換えないかどうかです。たとえば、

i = 2

で

i p [2] = 17

なら、その回で更新するのは

a [17]

です。

選択肢イの値を、スレッドごとに分けて確認します。

スレッド	担当する $i$	更新先となる $a$ の添字
スレッド1	$1, \dots, 5$	2、17、14、10、7
スレッド2	$6, \dots, 10$	19、16、13、9、6
スレッド3	$11, \dots, 15$	20、15、12、8、5
スレッド4	$16, \dots, 20$	18、1、11、3、4

どのスレッドの組にも、同じ添字がありません。つまり、スレッドどうしが同じ

a

の要素を書き換えることはなく、並列実行できます。

ほかの選択肢では、異なるスレッドが同じ要素を更新します。

アでは、スレッド1の $i = 1$ とスレッド2の $i = 6$ が、どちらも $a [1]$ を更新します。
ウでは、スレッド1の $i = 3$ とスレッド2の $i = 6$ が、どちらも $a [8]$ を更新します。
エでは、スレッド1の $i = 2$ とスレッド4の $i = 16$ が、どちらも $a [17]$ を更新します。

本文に「配列

i p

の値によっては並列実行できない場合がある」とあるのは、このように更新先が重なる場合があるためです。別々のスレッドによる更新先が重ならない選択肢はイです。

誤りやすいポイント

$i$ の値が重ならないように分割されていることだけでは、並列実行できるとは限りません。確認すべきなのは、実際に更新する $a [i p [i]]$ の添字です。
$i p [i]$ の値が異なるスレッド間で重なると、同じ $a$ の要素への書込みが同時に起こる可能性があります。
この問題では、 $i p [i]$ の値が全て異なるかを確認すれば判断できます。ただし、考え方として重要なのは、異なるスレッドどうしで更新先が重ならないことです。

FAQ

Q: なぜ

i

の範囲が分かれていても、更新先が重なるのですか？
A:

i

は、ループのどの回を実行するかを表します。一方、実際に書き換える

a

の位置は

i p [i]

で決まります。異なる

i

でも、

i p [i]

が同じなら同じ

a

の要素が更新されます。

Q: 同じスレッド内で更新先が重なる場合も、必ず問題になりますか？
A: この問題で注意するのは、異なるスレッドが同じ要素を書き換えることです。同じスレッド内の処理は順番に実行されるため、別スレッド間での同時書込みとは状況が異なります。

b [i]

の値も確認する必要がありますか？
A: この処理では、

b [i]

を読み、

a [i p [i]]

に書き込みます。更新先が別々であれば、読み取る

b [i]

の値が異なること自体は問題になりません。

関連キーワード: 並列処理、スレッド、共有メモリ、データ競合、配列索引

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2014年 春期 午後 問03

プログラムの並列実行に関する次の記述を読んで、設問1〜3に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2014年春期午後問03

設問1：