公務員試験 H24年 国家一般職(電気・電子・情報) No.38解説

　問 題　　　　　

任意のプロセッサ数で並列実行可能な部分P と、単一プロセッサのみで実行可能な部分 Q から構成されP と Q が並列に実行できないプログラムを考える。

単一プロセッサで実行した場合の P と Q の実行時間の比率が 4 : 1 であるとき、N₀ 個のプロセッサを用いてこのプログラムを実行したところ、単一プロセッサを用いる場合に対して実行速度が 2.5 倍になった。

同じ N₀ 個のプロセッサを用いて、単一プロセッサを用いる場合に対して実行速度を 3.5 倍にするために P と Q の割合を変更するとき、単一プロセッサで実行した場合の P と Q の実行時間の比率として最も妥当なのはどれか。

1. 7 : 1
2. 9 : 1
3. 12 :
4. 18 : 1
5. 20 : 1

 

 

 

 

 

　解 説　　　　　

問題文から、P,Qのイメージは以下のように考えられます。

P の部分は、プロセッサ数を 2 倍 3 倍にすれば、1/2,1/3 倍の時間で終わらせることができます。一方 Q の部分は、絶対幅１分の時間かかります。今幅 5 で、実行速度が 2.5 倍になったのであれば、5 ÷ 2.5 = 2 の時間で実行終了ということです。 Q で絶対 1 かかるので、P の部分を 1 で終わらせる必要があります。従って、N₀ は ４ とわかります。

次に、P の比率を変える　ということなので、P の占める幅を Xp とおきます。残りの部分が Q の幅なので、それを ５ーXp とおきます。ちなみに、プロセッサ数は変わらないのだから、より実行時間が速くなるということは、全体における 「P の比率が増える」とわかります。以下のようなイメージになります。

この時かかる時間は Xp/4 + 5-Xp です。これが 5 ÷ 3.5 = 5 × 2/7 = 10/7 です。解くと以下のようになり、Xp = 100/21 とわかります。

従って、５－Xp = 105/21 ー 100/21 = 5/21 です。よって、P と Q の、単一プロセッサで実行した時間の比率は「100/21：5/21 = 100：５＝『20：１』」です。

以上より、正解は 5 です。