基本情報技術者 2012年 春期 午後 問02
コンパイラの最適化に関する次の記述を読んで、設問1〜3に答えよ。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
表2において、最適化の方法を①、②、③の順で適用するとき、②で適用される最適化の方法はaであり、③で適用される最適化の方法はbである。
a, bに関する解答群
ア：関数のインライン展開
イ：共通部分式の削除
ウ：定数の畳込み
エ：定数伝播
オ：無用命令の削除
カ：ループ内不変式の移動
キ：ループのアンローリング
模範解答
a：カ、b：キ
解説
解答の導き方
表2では、①から②、②から③へと、プログラムの形が変わっています。それぞれの変化を比べると、適用された最適化の方法が分かります。
まず、①では「t ← m + n」がループ（同じ処理を繰り返す部分）の中にあります。②では、この文がループの外、つまりループの前に移動しています。
表1には、ループ内不変式の移動について「ループ中で値の変化しない式」があるとき、その式をループの外に移動するとあります。ここでは、ループの中で変数mとnの値が変わらないため、m + nの計算結果も毎回同じです。そこで、繰返しのたびに計算するのではなく、ループが始まる前に一度だけ計算する形にしています。この変化から、②の方法はカ：ループ内不変式の移動です。
次に、②では「■ i: 0, i ≤ 1, 1」で始まるループがあります。これは、iを0から始めて、iが1以下の間、1ずつ増やしながら処理する指定です。したがって、ループ内の処理は、iが0のときと1のときの計2回行われます。
③ではループの形がなくなり、iが0のときの処理と、iが1のときの処理がそれぞれ書き出されています。ループの繰返し処理を展開しているので、③の方法はキ：ループのアンローリングです。最後の「i ← 2」は、2回目の処理後にiが2となり、条件「i ≤ 1」を満たさなくなることを表しています。
誤りやすいポイント
- ②は「m + nを定数として計算した」のではありません。mとnは変数なので、値が分からない限り計算結果を決められません。ループの中で値が変わらないため、計算する位置を移動しています。
- ③ではiの値が0と1に置き換わっていますが、主な変化は、ループの繰返し処理を展開したことです。そのため、方法は定数伝播ではなく、ループのアンローリングです。
- ①から②への変化と、②から③への変化は別々に判断します。まず「t ← m + n」の位置に注目し、次にループが展開されていることに注目します。
FAQ
Q: ループの外に移動しても、処理結果が変わらないのはなぜですか？
A: ループ中にmとnの値が変わらなければ、m + nの結果も変わりません。そのため、先に一度計算して、その結果を繰返し利用できます。
A: ループ中にmとnの値が変わらなければ、m + nの結果も変わりません。そのため、先に一度計算して、その結果を繰返し利用できます。
Q: ループのアンローリングをすると、なぜループがなくなるのですか？
A: 繰返し回数が分かる場合、繰返しの各回で行う処理を順番に書き出せるためです。表2の③では、iが0と1の場合の処理を個別に記述しています。
A: 繰返し回数が分かる場合、繰返しの各回で行う処理を順番に書き出せるためです。表2の③では、iが0と1の場合の処理を個別に記述しています。
Q: ③の最後に「i ← 2」があるのはなぜですか？
A: ループでは、iが0と1のときに処理した後、iが2になります。iが2になると条件「i ≤ 1」を満たさないので、ループが終了します。
A: ループでは、iが0と1のときに処理した後、iが2になります。iが2になると条件「i ≤ 1」を満たさないので、ループが終了します。
関連キーワード: ループ内不変式の移動、ループのアンローリング、共通部分式の削除、定数伝播、コンパイラ最適化
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
関数のインライン展開の例を図1に示す。図1の関数funcをインライン展開した場合、実引数10の値が仮引数pに代入され、その値10が関数func内の変数pの値になる（図1①）。次に、cの方法を適用することによって、条件式p ≧ 10の判定結果やpを含んだ計算式の計算結果がコンパイル時に確定する（図1②）。その結果、func(10)を値15に置き換えることができる（図1③）。
なお、#wはコンパイラが最適化をしたときに生成した整数型の変数である。
cに関する解答群
ア：共通部分式の削除
イ：定数の畳込み
ウ：定数伝播
エ：無用命令の削除
オ：ループ内不変式の移動
カ：ループのアンローリング
模範解答
c：イ
解説
解答の導き方
まず、図1①では関数のインライン展開をしています。インライン展開とは、関数を呼び出す場所に、その関数の処理を展開する方法です。呼び出しに使われた実引数の値10が、関数側で受け取る仮引数pの値になります。
このため、関数内の条件式「p ≧ 10」は、値を当てはめると「10 ≧ 10」です。また、計算式「p + 5」は「10 + 5」、「p + 15」は「10 + 15」になります。
ここで行うのは、定数だけでできた式を実際に計算する処理です。表1の「定数の畳込み」には、「プログラム中の定数同士の計算式を、その計算結果で置き換える」とあります。したがって、条件式はtrueに、計算式はそれぞれ15と25に置き換わります。図1②で示されている処理に当たるので、cには「定数の畳込み」が入ります。
条件がtrueなので、実際に選ばれるのはp + 5の側です。計算結果は15となるため、図1③では関数呼出しの結果が15に置き換わっています。
誤りやすいポイント
- 「定数伝播」と「定数の畳込み」を混同しやすいです。定数伝播は、変数を定数で置き換える方法です。一方、定数の畳込みは、定数だけの式を計算結果に置き換える方法です。この設問では、条件式や計算式の結果を確定させる処理が問われています。
- p + 5の計算結果だけを見て15と決めるのではなく、先に条件式がtrueになることを確認します。条件がtrueなので、p + 15の側ではなくp + 5の側が選ばれます。
- 共通部分式の削除は、値が変わらない同じ式を繰り返し計算しないようにする方法です。今回のように定数の式を計算する方法とは異なります。
FAQ
Q: pの値が10になるなら、定数伝播ではないのですか？
A: pを10に置き換えること自体は、定数伝播に当たります。ただし、この設問で問われているのは、値が分かった後に「10 ≧ 10」や「10 + 5」を計算する処理です。そのため、答えは定数の畳込みです。実際の最適化では、複数の方法が続けて使われることがあります。
A: pを10に置き換えること自体は、定数伝播に当たります。ただし、この設問で問われているのは、値が分かった後に「10 ≧ 10」や「10 + 5」を計算する処理です。そのため、答えは定数の畳込みです。実際の最適化では、複数の方法が続けて使われることがあります。
Q: なぜ関数の結果は25ではなく15なのですか？
A: 条件式がtrueになるため、p + 5の側が選ばれます。pの値は10なので、10 + 5を計算した15が関数の結果です。
A: 条件式がtrueになるため、p + 5の側が選ばれます。pの値は10なので、10 + 5を計算した15が関数の結果です。
Q: コンパイル時に計算すると、何がよいのですか？
A: プログラムを実行するときに行う計算を減らせます。実行前に答えが分かる計算を済ませておくことで、実行時間を短くできます。
A: プログラムを実行するときに行う計算を減らせます。実行前に答えが分かる計算を済ませておくことで、実行時間を短くできます。
関連キーワード: コンパイラ最適化、関数のインライン展開、定数の畳込み、定数伝播
設問3：
問題文を見る 次の記述中のに入れる適切な答えを、解答群の中から選べ。
最適化をしないときと最適化をしたときとで浮動小数点数の演算の結果が異なる場合がある。プログラム1に対して表2の最適化をしなかったものと、最適化をしたものとに、y[0] = 307000000.0、y[1] = 305000000.0、m = −303000000.0、n = 4.0を与えて実行した。その結果のx[0]、x[1]が次のとおりになった。ここで、同一優先順位の算術演算子は、左から順に演算する。
最適化をしないとき：x[0] = 4000004.0、x[1] = 2000004.0
最適化をしたとき：x[0] = 4000000.0、x[1] = 2000000.0
この実行結果が異なる原因としては、dの方法の適用によって演算順序が変化したことで、eが発生したからである。ここで、浮動小数点数の演算は単精度（仮数部は23ビット）で計算しているものとする。
dに関する解答群
ア：関数のインライン展開
イ：共通部分式の削除
ウ：定数の畳込み
エ：定数伝播
オ：無用命令の削除
カ：ループ内不変式の移動
キ：ループのアンローリング
eに関する解答群
ア：桁あふれ
イ：桁落ち
ウ：情報落ち
エ：丸め誤差
模範解答
d：イ、e：ウ
解説
解答の導き方
この問題では、最適化の前後で計算の順番が変わり、その結果として浮動小数点数の値に差が出た理由を考えます。浮動小数点数は、コンピュータが限られたビット数で表す数です。そのため、計算結果を正確に表せない場合があります。
まず、最適化をしないときの計算を見ます。問題文には「同一優先順位の算術演算子は、左から順に演算する」とあります。そのため、たとえば は次の順で計算されます。
同じように、 は次のとおりです。
次に、表2の①を見ると、 を計算して作業用変数 に入れ、その を使っています。表1の「共通部分式の削除」は、同じ計算を作業用変数に格納し、複数箇所で再利用する方法です。したがって、 に入るのは「共通部分式の削除」です。
この変換により、 の順だった計算が、先に を計算してから を計算する順に変わります。つまり、括弧の付け方が変わります。
ここで、 の正確な値は次のとおりです。
しかし、単精度では、この大きさの数を表すとき、隣り合う表現可能な数の間隔は です。 は正確に表せないため、近い値である に丸められます。すると、足したはずの が結果に残りません。
このように、小さな値を大きな値に加えたとき、小さな値の影響が結果から失われる現象を「情報落ち」といいます。したがって、 に入るのは「情報落ち」です。
誤りやすいポイント
- 最適化によって計算をまとめても、浮動小数点数では計算結果が変わることがあります。実数として同じ式でも、計算する順序が異なると、途中で丸められる位置が変わるためです。
- 「桁落ち」と「情報落ち」は別の現象です。桁落ちは、近い値どうしを引き算したときに、有効な桁が失われる現象です。この問題で直接起きているのは、 の計算で小さい が大きな数に吸収される情報落ちです。
- 表2の②では、ループの外に計算を移しています。しかし、計算順序を変えるきっかけになったのは、表2の①で をまとめて作業用変数に入れたことです。
FAQ
Q: 浮動小数点数の計算では、いつも誤差が出るのですか？
A: いつも目に見える誤差が出るわけではありません。ただし、表現できる数には限りがあります。計算結果を正確に表せない場合は、近い値に丸められます。
A: いつも目に見える誤差が出るわけではありません。ただし、表現できる数には限りがあります。計算結果を正確に表せない場合は、近い値に丸められます。
Q: この問題で起きているのは「丸め誤差」ではないのですか？
A: を近い値に丸める処理はあります。ただし、設問が尋ねているのは、その結果として小さな の影響が失われた現象です。その現象を表す答えが「情報落ち」です。
A: を近い値に丸める処理はあります。ただし、設問が尋ねているのは、その結果として小さな の影響が失われた現象です。その現象を表す答えが「情報落ち」です。
Q: なぜ最適化で計算順序を変えるのですか？
A: 同じ計算を何度も行わず、作業用変数に保存した値を再利用するためです。計算回数を減らす目的には役立ちますが、浮動小数点数では結果が変わることがあります。
A: 同じ計算を何度も行わず、作業用変数に保存した値を再利用するためです。計算回数を減らす目的には役立ちますが、浮動小数点数では結果が変わることがあります。
関連キーワード: 浮動小数点数、単精度、共通部分式の削除、情報落ち、桁落ち
