[平成２６年度春] 午後 問3解説

[問題文・解答]

平成２６年度４月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H26春 午後 問題文]　　　[H26春 午後 解答]

[問題概要]

この問題は、選択問題で問2〜問7のうち4問を選択する必要があります。
出題分野はソフトウェアで、問題の題材はプログラムの並列実行です。
スレッドを使用したプログラムの並列実行について問われます。プログラムのfor文の動作さえ理解していれば後は数学的な問題です。

[設問1]

設問より、プログラムAのデータ作成、計算処理、結果出力の処理時間の割合が7：90：3なので、r = 90/(7+90+3) = 0.9となります。
よって、高速化率E≥5となるためには以下の不等式を解けばOKです。
1/( 1 - 0.9 + ( 0.9/n ) ) ≥ 5
1 ≥ 5 ( 0.1 - (0.9/n) )
0.5 ≥ 4.5/n
n≥9
従ってCPU9個以上が必要となるため「オ」が正解です。

[答] オ

[設問2]

b) プログラム1のように配列の１つ前の要素(a[i-1])を基にa[i]を更新する場合、次の繰り返しでは先ほど更新したa[i]を参照してa[i+1]を更新することになります。この場合、ループを分割してしまうと、分割された2つのループ間で更新と参照の順序が入れ替わる可能性があるため並列実行出来ません。よって、「ア」が正解です。

c) プログラム2のように配列の１つ後の要素(a[i+1])を基にa[i]を更新する場合、次の繰り返しでは、a[i+2]を基に先ほど参照したa[i+1]を更新することになります。この場合、ループを分割してしまうと、分割された２つのループ間で参照と更新の順序が入れ替わる可能性があるため並列実行出来ません。よって、「ウ」が正解です。

d) プログラム1や2のように参照・更新を行った要素に対してその後の繰り返し中で更に更新や参照を行う場合は並列実行不可能です。プログラム3で更新が行われるのは、1≤i≤nよりa[1]〜a[n]となります。従って、a[i+m]がこの範囲に入らなければ並列実行可能となるためm≥nであればOKです。よって「イ」が正解です。

[答] b) ア　c) ウ　d) イ

[設問3]

配列ipの各要素で重複がなければループの中で配列aの各要素を更新するのは最大で１回となるため、更新順序が関係なく並列実行可能となります。例えば、配列ipに1〜20までの数字が順に格納されている場合は、i=ip[i]となり、図3と同様に並列実行可能なプログラムになります。解答群のうち、重複を含まないのは「イ」のみなのでこれが正解です。

[答] イ

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。