2008　電気通信大学　夜間総合問題・後期MathJax

【４】　$\mathrm{DNA}$解析など，コンピュータ上で処理する大きな仕事について考えよう．$1.00$単位の仕事を$\mathrm{A}$という$1$個の$\mathrm{CPU}$で実行すると，$1.00$時間かかるプログラムがある．この仕事の$40\mathrm{\%}$は複数の$\mathrm{CPU}$で同時並行に実行できるが，$60\mathrm{\%}$は単一の$\mathrm{CPU}$でしか実行できない．この$40\mathrm{\%}$を並列化可能部分と呼び，$60\mathrm{\%}$を並列化不能部分と呼ぶ．

　例えばこの仕事を$2$個の$\mathrm{CPU}\mathrm{A}$で並列に実行すると，この仕事は$0.80$時間で終了する．この時，$1.00$単位の仕事を$0.80$時間で実行しているので，実行速度は$1.25$（単位/時間）となる．すなわち，この仕事を$2$個の$\mathrm{CPU}\mathrm{A}$で並列に実行すると，$1$個の$\mathrm{CPU}\mathrm{A}$で実行した時に比べ，実行速度は$1.25$倍となる．

　以下の問いに答えよ．

(1)　このプログラムを$4$個の$\mathrm{CPU}\mathrm{A}$で並列に実行すると，何時間かかるか．また$1$個の$\mathrm{CPU}\mathrm{A}$で実行した時に比べ，実行速度は何倍になるか．

(2)　このプログラムを$N$個の$\mathrm{CPU}\mathrm{A}$で並列に実行する場合の実行速度のグラフの概形を描け．ただし，縦軸を実行速度，横軸を$\mathrm{CPU}\mathrm{A}$の個数$N$とせよ．また，漸近線および漸近値も書き入れること．

(3)　実行速度が$\mathrm{CPU}\mathrm{A}$の$99.00$倍の$\mathrm{CPU}\mathrm{B}$がある．このプログラムを$\mathrm{CPU}\mathrm{A}$と$\mathrm{CPU}\mathrm{B}$で並列に実行すると，何時間かかるか．また実行速度は$1$個の$\mathrm{CPU}\mathrm{A}$で実行した時に比べ，何倍になるか．ただし並列化不能部分は$\mathrm{CPU}\mathrm{A}$で実行するものとする．

　ここで，コンピュータシステムの価格を$\mathrm{CPU}$の価格で近似しよう．$1$個の$\mathrm{CPU}\mathrm{A}$で実行した場合と$2$個の$\mathrm{CPU}\mathrm{A}$で実行した場合とを比較すると，価格は倍となる．しかし実行速度は$1.25$倍にしか増加しない．したがって価格に対する実行速度の比率は$0.63$倍となる．言い換えると，$2$倍の費用を投入しても$1.25$倍の見返りしか得られず，その比率が$0.63$倍にしかならないということになる．もちろん，価格に対する実行速度の比率は，大きいほど良い．

(4)　$1$個の$\mathrm{CPU}\mathrm{A}$で実行した場合に対し，$4$個の$\mathrm{CPU}\mathrm{A}$で実行した場合の価格に対する実行速度の比率は何倍となるか．

(5)　さらに，このプログラムに対し$1$個の$\mathrm{CPU}\mathrm{A}$と同じだけの価格を費やして改造することを考えよう．改造の費用もコンピュータシステムの価格に含まれるものとする．この改造では，並列化不能部分の仕事の処理を$2$倍に高速化する．改造後のプログラムを$3$個の$\mathrm{CPU}\mathrm{A}$で実行すると何時間かかり，改造前のプログラムを$1$個の$\mathrm{CPU}\mathrm{A}$で実行した時に比べ実行速度は何倍になるか．また価格に対する実行速度の比率は何倍となるか．