基本情報技術者 2019年秋期午後問02

スレッドを使用した並列実行に関する次の記述を読んで、設問1〜3に答えよ。

　プログラム中の並列実行が可能な部分を取り出し、その部分を分割して複数のスレッドで並列に実行する方法（以下、スレッド並列法という）がある。マルチプロセッサシステムでは、スレッド並列法を適用することによって、プログラムの実行時間を短縮できることがある。　　プログラムにおいて、スレッド並列法を適用しないで実行したときの実行時間を、スレッド並列法を適用したときの実行時間で割った値を、プログラム実行時間の高速化率という。　プログラムをスレッド並列法を適用しないで実行したときの、プログラム全体の実行時間に対する、並列実行可能な部分の実行時間の割合を

r

（

0 \leq r \leq 1

）とする。スレッドの個数を

n

（

n \geq 1

）にして、プログラムにスレッド並列法を適用すると、マルチプロセッサシステムでは、プログラム実行時間の高速化率

E

は、次の式で求められる。ここで、各スレッドはそれぞれ異なるプロセッサに割り当てられるものとし、プログラムの実行に使用する全てのプロセッサの性能は同じとする。

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

　この式は、並列実行可能な部分のプログラム実行時間がスレッド並列法の適用によって

\frac{1}{n}

になり、その他の部分のプログラム実行時間は変化しないときの高速化率を計算するものである。　　プログラム中に並列実行が可能な部分をもつプログラムAに対してスレッドの個数を2にしてスレッド並列法を適用すると、高速化率は

\frac{3}{2}

になった。この場合、rはaである。　　rが3/4であるプログラムBの場合、スレッドの個数を増やしても、高速化率の上限はbである。

設問1：

問題文を見る

　本文中のに入れる正しい答えを、解答群の中から選べ。　 aに関する解答群　ア：1/6 　イ：1/4 　ウ：1/3 　エ：1/2 　オ：2/3 　 bに関する解答群　ア：2 　イ：3 　ウ：4 　エ：6 　オ：8

模範解答

a：オ、b：ウ

解説

解答の導き方

この問題では、並列実行できる部分の割合

r

と、スレッドの個数

n

から、プログラム全体の高速化率

E

を求める式を使います。スレッド（プログラムを実行する処理の単位）を増やすと、並列実行できる部分は短時間で終わります。一方、並列実行できない部分の時間は変わりません。

aを求めます。

本文では、プログラムAについて「スレッドの個数を2にして」「高速化率は

\frac{3}{2}

」とあります。したがって、式の

n

に

2

、

E

に

\frac{3}{2}

を入れます。

\frac{3}{2} = \frac{1}{( 1 - r ) + \frac{r}{2}}

両辺の逆数をとると、分母は

\frac{2}{3}

になります。また、分母の中を整理すると、次のようになります。

(1 - r) + \frac{r}{2} = 1 - \frac{r}{2}

よって、

1 - \frac{r}{2} = \frac{2}{3}

です。両辺から

\frac{2}{3}

を引くと、

\frac{r}{2} = \frac{1}{3}

となります。両辺を

2

倍して、

r = \frac{2}{3}

です。解答群ではオに当たります。

bを求めます。

プログラムBでは

r = \frac{3}{4}

です。スレッドの個数

n

を増やすと、式の分母にある

\frac{r}{n}

は小さくなり、上限では

0

に近づきます。

一方、並列実行できない部分の割合

1 - r

は変わりません。プログラムBでは、

1 - r = 1 - \frac{3}{4} = \frac{1}{4}

です。したがって、高速化率の上限は次のとおりです。

\frac{1}{1 - r} = \frac{1}{\frac{1}{4}} = 4

解答群ではウに当たります。スレッドを増やしても、並列実行できない部分の時間は残るため、高速化率には上限があります。

誤りやすいポイント

式の分母にある $1 - r$ を見落とさないようにします。これは、並列実行できず、時間が短くならない部分の割合です。
aでは、 $E = \frac{3}{2}$ をそのまま分母と考えないようにします。式の右辺は分母の逆数なので、分母は $\frac{2}{3}$ です。
bでは、スレッドを増やせば高速化率も際限なく大きくなる、と考えないようにします。並列実行できない部分が残るので、高速化率には上限があります。

FAQ

Q: bの上限は、有限個のスレッドでも必ず

4

になりますか？

A: いいえ。有限個のスレッドでは

\frac{r}{n}

が

0

にならないため、高速化率は

4

より小さい値です。スレッドの個数を増やすほど

4

に近づきます。

r

は、スレッド並列法を適用した後の割合ですか？

A: いいえ。本文では、スレッド並列法を適用しないときのプログラム全体の実行時間に対する、並列実行可能な部分の実行時間の割合としています。

関連キーワード: スレッド、並列処理、高速化率、並列実行可能部分

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

この設問をAIに質問する

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

設問2：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。

　配列の操作を行う繰返しの処理において、図1、図2のように繰返しの範囲を分割して、スレッド並列法を適用することを考える。　このとき、操作の内容によって、正しい結果が得られる場合と得られない場合があるので、十分に検討することが必要である。　　正しい結果が得られる場合の例を、図1に示す。　図1に示すプログラム1は、制御変数iの取る範囲を分けることによって繰返し範囲を分割した繰返しの処理を、それぞれ異なるスレッドで実行できる。　なお、図1、図2において、実線の四角はプログラム、破線の四角は繰返しの処理、破線の四角から出る二つの矢印は分割を示す。

　正しい結果が得られない場合の二つの例を、図2に示す。　プログラム2の繰返しの処理を、スレッド2-1とスレッド2-2の二つに分割すると、cことがあるので、スレッド並列法を適用しない場合の実行結果と等しくなることを保証できない。したがって、プログラム2に対しては、繰返しの範囲の分割によるスレッド並列法を適用できない。　また、プログラム3の繰返しの処理を、スレッド3-1とスレッド3-2の二つに分割すると、dことがあるので、スレッド並列法を適用しない場合の実行結果と等しくなることを保証できない。したがって、プログラム3に対しても、繰返しの範囲の分割によるスレッド並列法を適用できない。

cに関する解答群　ア：a[51]の値をスレッド2-1で更新するより先にスレッド2-2で更新する　イ：a[51]の値をスレッド2-1で更新するより先にスレッド2-2で参照する　ウ：a[51]の値をスレッド2-1で参照するより先にスレッド2-2で更新する　エ：a[51]の値をスレッド2-1で参照するより先にスレッド2-2で参照する　 dに関する解答群　ア：a[51]の値をスレッド3-1で更新するより先にスレッド3-2で更新する　イ：a[51]の値をスレッド3-1で更新するより先にスレッド3-2で参照する　ウ：a[51]の値をスレッド3-1で参照するより先にスレッド3-2で更新する　エ：a[51]の値をスレッド3-1で参照するより先にスレッド3-2で参照する

模範解答

c：ウ、d：イ

解説

解答の導き方

この設問では、繰返し処理を二つのスレッドに分けたとき、同じ配列要素を「参照（値を読み取ること）」する処理と「更新（値を書き換えること）」する処理の順序が変わるかを調べます。スレッドとは、独立して処理を進める実行単位です。並列実行では、二つのスレッドのどちらが先に動くかは決まっていません。

プログラム2

プログラム2の処理は、各回で次の計算をします。

a [i] \leftarrow a [i + 1] + b [i]

スレッド2-1は

i = 1

から

i = 50

まで、スレッド2-2は

i = 51

から

i = 100

までを担当します。境目にある

a [51]

に注目します。

処理	$a [51]$ に対する操作
スレッド2-1で $i = 50$ のとき	$a [51]$ を参照する
スレッド2-2で $i = 51$ のとき	$a [51]$ を更新する

繰返しを分割しない場合は、

i = 50

の処理が終わってから

i = 51

の処理に進みます。そのため、スレッド2-1が

a [51]

を参照してから、スレッド2-2が

a [51]

を更新します。

しかし、並列実行では順序が逆になることがあります。スレッド2-2が先に

a [51]

を更新すると、スレッド2-1は、元の実行順序なら読んでいたはずの値とは異なる値を参照する可能性があります。したがって、起こり得るのは「スレッド2-1で参照するより先にスレッド2-2で更新する」ことで、cはウです。

プログラム3

プログラム3の処理は、各回で次の計算をします。

a [i] \leftarrow a [i - 1] + b [i]

スレッド3-1は

i = 2

から

i = 51

まで、スレッド3-2は

i = 52

から

i = 101

までを担当します。ここでも、境目にある

a [51]

を確認します。

処理	$a [51]$ に対する操作
スレッド3-1で $i = 51$ のとき	$a [51]$ を更新する
スレッド3-2で $i = 52$ のとき	$a [51]$ を参照する

繰返しを分割しない場合は、

i = 51

の処理で

a [51]

を更新した後、

i = 52

の処理でその値を参照します。

一方、並列実行では、スレッド3-2が先に動き、スレッド3-1が

a [51]

を更新する前に参照することがあります。この場合、スレッド3-2は更新前の値を使うため、元の実行順序と結果が異なる可能性があります。したがって、起こり得るのは「スレッド3-1で更新するより先にスレッド3-2で参照する」ことで、dはイです。

誤りやすいポイント

配列の添字が異なる処理ばかりだと思い込み、繰返しの境目で同じ要素が使われることを見落としやすいです。プログラム2では、スレッド2-1が $a [51]$ を読み、スレッド2-2が同じ要素を書き換えます。
「更新する処理がある」だけでなく、元の繰返し順序で更新と参照のどちらが先かを確認します。プログラム2は参照の後に更新する関係、プログラム3は更新の後に参照する関係です。
並列実行では、担当範囲が分かれていても、スレッド同士の実行順序までは保証されません。各スレッドの処理範囲だけで安全と判断しないようにします。

FAQ

Q: プログラム2では、スレッド2-1とスレッド2-2が同じ

a [51]

を更新するのですか？
A: いいえ。スレッド2-1は

a [51]

を参照し、スレッド2-2が

a [51]

を更新します。読み取る処理と書き換える処理の順序が変わることが問題です。

Q: 図1のプログラム1では、なぜ繰返し範囲を分けられるのですか？
A: スレッドごとに担当する

i

の範囲が分かれ、各処理が書き換える

a [i]

も重ならないためです。片方のスレッドの処理順序が、もう片方の結果に影響しません。

Q: スレッドを分ければ、必ず処理時間は短くなりますか？
A: 必ず短くなるとは限りません。この設問のように、処理順序が変わることで結果が変わる場合もあります。分割する前に、同じデータを使う処理の関係を確認する必要があります。

関連キーワード: スレッド、並列処理、配列、データ依存関係、競合状態

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

この設問をAIに質問する

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

設問3：

問題文を見る

　図3に示すプログラム4では、配列aにおける更新対象の位置を配列ipの要素の値で指している。このプログラムでは、配列ipの要素の値によって、スレッド並列法を適用できる場合とできない場合がある。　図4に示す配列ipであれば、スレッド並列法を適用できる。図4中のに入れる正しい答えを、解答群の中から選べ。　なお、図3において、実線の四角はプログラム、破線の四角は繰返しの処理、破線の四角から出る二つの矢印は分割を示す。

eに関する解答群

模範解答

e：エ

解説

解答の導き方

図3の処理では、繰返しの各回で「a[ip[i]] ← b[i]」を実行します。ここで、配列（値を順番に並べて扱う仕組み）ipの要素 ip[i] が、配列aのどの場所を更新するかを決めています。

スレッド（処理を分けて実行する単位）を使って並列に処理するときは、別々のスレッドが同じ場所を書き換えないことが大切です。同じ場所に同時に書き込むと、どちらの値が最後に残るかが実行順に左右され、正しい結果が保証されないからです。このように、複数の処理が同じデータの更新でぶつかることを、データ競合といいます。

図3では、処理を次のように分けています。

処理	繰返しで使う値	配列aの更新先
スレッド4-1	iが1から5	a[ip[1]]からa[ip[5]]
スレッド4-2	iが6から10	a[ip[6]]からa[ip[10]]

図4では、ip[1]からip[5]の値は、順に1、2、3、4、5です。したがって、スレッド4-1はa[1]からa[5]を更新します。

一方、スレッド4-2が更新する場所は、ip[6]からip[10]の値で決まります。スレッド4-1の更新先と重ならないためには、これらの値に1から5までが含まれてはいけません。

解答群を確かめると、次のようになります。

選択肢	ip[6]からip[10]の値	スレッド4-1の更新先との重なり
ア	1、2、8、9、10	1、2が重なります
ウ	6、7、4、9、10	4が重なります
イ	5、6、7、8、9	5が重なります
エ	6、7、8、9、10	重なりません

エなら、スレッド4-2の更新先はa[6]からa[10]です。スレッド4-1の更新先であるa[1]からa[5]とは別なので、並列に処理しても更新先が競合しません。よって、eに入るのはエです。

誤りやすいポイント

繰返しの番号iが異なれば、更新先も異なるとは限りません。更新先はiそのものではなく、ip[i]の値で決まります。
ip[6]からip[10]の値が、1から5のどれかと重なると、別々のスレッドが同じ配列aの要素を書き換える可能性があります。
ip[6]からip[10]が連続した値かどうかだけで判断しないようにします。大切なのは、スレッド4-1の更新先と重なる値があるかどうかです。

FAQ

Q: なぜipの値を確認する必要があるのですか？
A: iは繰返しの番号で、ip[i]は配列aの更新先を表す値だからです。繰返しの番号が別でも、ip[i]が同じなら同じ場所を更新することがあります。

Q: スレッドが同じ場所を更新すると、どうなりますか？
A: どちらの書込みが後になるかは、並列処理の進み方で変わることがあります。そのため、元の順番どおりに実行した場合と異なる結果になるおそれがあります。

Q: ip[6]からip[10]の値は、並び順も決まっていますか？
A: この設問で必要なのは、スレッド4-1の更新先である1から5と重ならないことです。したがって、6から10の値がどの順番で並ぶかは問いません。

関連キーワード: 配列、スレッド、並列処理、データ競合、ループ分割

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

この設問をAIに質問する

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2019年 秋期 午後 問02

スレッドを使用した並列実行に関する次の記述を読んで、設問1〜3に答えよ。

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

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2019年秋期午後問02

設問1：