「Gotoによる最適化;分岐予測およびキャッシュヒット率の向上」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
昨今CPUではますます分岐予測やキャッシュヒット率の向上が、大きな要素を占めている。
-[[分岐予測>http://ja.wikipedia.org/wiki/分岐予測]]
-[[キャッシュメモリ>http://ja.wikipedia.org/wiki/キャッシュメモリ]]
[[Goto]]はうまく使うことで、ループや分岐のの単純化出来る場合がある。
処理の大半はループ(とそれに絡む分岐)なので、Gotoは積極的につかうべきである。
昨今CPUではますます分岐予測やキャッシュヒット率の向上が、大きな要素を占めている。
-[[分岐予測>http://ja.wikipedia.org/wiki/分岐予測]]
-[[キャッシュメモリ>http://ja.wikipedia.org/wiki/キャッシュメモリ]]
[[Goto]]はうまく使うことで、ループや分岐のの単純化出来る場合がある。
処理の大半はループ(とそれに絡む分岐)なので、Gotoは積極的につかうべきである。
-キャッシュコンシステンシイ
プロセッサのキャッシュメモリに入るコードか、そうでないコードでのレイテンシの問題のこと。
もし、ループ構文の中でロングジャンプが発生していた場合、キャッシュメモリの範囲を
超えたアドレスに頻繁にジャンプする事になる。
この振る舞いは、命令キャッシュの範囲を超えているので、命令キャッシュのコンシステンシイ
に問題が生じキャッシュレイテンシに差が生じる。
一例としてはCore2マイクロアーキテクチャでは、一次命令キャッシュ内に収まるような小さな
ジャンプ(goto)では、キャッシュレイテンシは3サイクル程度だが、キャッシュ範囲を超えると
20-30サイクルのレイテンシが生じる事が報告されている。
同様なことはデータキャッシュにも当てはまり、特定の変数群、あるいはヒープから確保された変数
ブロックが、異なるアドレスに存在するとき、キャッシュメモリの範囲を超えている場合には
キャッシュのスラッシングが発生する。
ABはコンパイラで、出力されるオブジェクトコードの変数はメモリに割り当てられる。
従って変数の参照はメモリアクセスが生じるので、キャッシュメモリーのレイテンシ差によって
処理速度が変化する。
コードを書く場合は、実行する実マシンのキャッシュ容量に注意して書くと良いだろう。
-ブランチと分岐予測
コンピュータと呼ばれる機械は、メモリーとI/Oがあり、CPUと呼ばれる演算装置によって構成
されている。
通常、CPUはメモリーからデータを読み取り、実行し、メモリやI/Oにデータを出力するなどの
動作をする。動作はプログラムと呼ばれるシーケンスによって動作する。CPUには演算装置が含まれる。
演算ユニット自体はさらにパイプライン化されていて、命令のフェッチ(読み出し)、デコード(解読)、
エグゼキュータ(実行)
というような典型的な機能別にモジュール化されていて、処理が各機能ごとに平行して実行
される。
従来は、一つの演算ユニットが、命令のフェッチ、デコード、エグゼキュータを処理し、兼用していた。
回路が簡単で複雑でなく、実装しやすいが1命令ずつ処理する。
これらは命令のフェッチ中はデコードが出来ないし、デコードが完了しなければエグゼキュート
出来ない。
それぞれの処理シーケンスごとに機能を区分し、インストラクションを機能から分離し、
流れ作業のようにして命令をフェッチ、デコード、エグゼキュートすれば、処理が速くなる。
例えば下記のような抽象的な、無限ループの加算コードがあったとする。
label1:
i++;
j++;
k++;
goto label1;
このコードのようなインストラクションがパイプ無しのプロセッサで動作していた場合、フェッチ、デコード、
エグゼキュータが一つの演算ユニットで動作している。
パイプライン化されていないプロセッサの場合、i++;を実行するために、フェッチ、デコードし、
エグゼキュータの段階で演算が完了する。この間、i++
を処理するためにフェッチ、デコード、エグゼギュートという3ステートが消費される事になる。
全体で、三つのインクリメントを処理するループには、おおよそ9ステート(サイクル)必要であることが判る。
これに対し、パイプライン化されている場合、初期動作は実行時ペナルティがあるものの、
無限ループ処理なので、i++をフェッチ、j++をデコード、k++をエグゼキュート、という順に処理が
パイプライン化されている。
処理は無限ループなので、パイプラインがストールせず、うまく回っている場合、
見かけ上、i++をフェッチしている間、k++は処理が完了している。全体として、3ステートのみで
一回のループが処理できている。
i++をフェッチしている間、j++はデコードされ、k++は演算器によって実行されている。
次のステートでは、i++はデコード、j++は演算器で実行されているが、k++は次のループサイクル
の命令をフェッチしている。
パイプラインが停止しなければ、この一連のサイクルは見かけ上、1命令1ステートで動作して
いるように見え、ループ全体ではi++がプロセッサに投入されればk++が帰ってくるという、流れ作業が
実現している。この時、i++の実行に必要なステートは1ステートで、ループ全体を3ステートで
処理可能となっている。
パイプライン化されていなプロセッサと比較では、おおよそ1/3程度早いだろうと判る。
インストラクション的に見れば命令実行パイプラインはFILOや命令キューのようなものだ。
このような視点はクラシカルなCISC系のプロセッサには現れなかった発想で、CISC系であるPentium
ですらRISC的な設計を取り入れている現在では一般的な概念となっている。
例として五段パイプラインの説明で図示されるひし形のブロックのダイアグラムは、左右の階段状の部分が
パイプのStart/End部分を示し、真中の中心の縦方向の五つのブロックが、まさにパイプが密に
詰まって実行されている状態を示している。この状態が長く維持されればパイプラインが効率的に
動作しているという事になる。
もし、無限ループ内にif等のブランチがあった場合、パイプラインの振る舞いは異なってくる。
label1:
i++;
j++;
if (i>n) {
k++;
} else {
k--;
}
goto label1;
上記をより抽象的なコードにすれば以下のようになる。
start:
i++
j++
brch i
k++
jmp end:
k--
jmp end:
end:
jmp start:
単純に考えて、brch/jmpは演算器を使わず、フェッチ、デコード、エグゼキュートの3ステート
を使い分岐するから、それまでパイプライン上にあった命令を終わらせ一旦フラッシュする事が
必要になる。(五段パイプラインの、左側の階段状の部分のように再スタートする必要がある)
全体として演算のためのパイプライン動作が効率的に動作しているとは言いがたい。
ループ全体で考えれば、見かけ上1命令1ステートという理想的なパイプラインが動作しない。
本当に正確に言えばjump命令(goto)なども分岐なのでパイプラインをストール(失速)させる。
その他、分岐先の命令が該当する。しかし分岐予測機能を持つプロセッサであれば、ジャンプ先
のインストラクションが判るのでパイプラインをストールさせる事は無いし、
分岐予測機能がないプロセッサであれば、遅延スロットと呼ぶ擬似命令をパイプに流し込んで
パイプをストールさせないような仕組みがあるものが多い。パイプラインを止めるより無関係な命令を
流して回した方が良いという戦略である。
PentiumやAMDのプロセッサは分岐予測が含まれるし、組み込み機器のCPUでは分岐予測は複雑なので
遅延スロットを使う例がある(組み込みではSH1/SH2DSP)。
その他、遅延スロットはMIPS,SPARCなども備えているがMIPS/SPARCは異なる世代で分岐予測機能を持ち、
Power等も分岐予測を持つ。ARMも同様だがアーキテクチャの設計や世代によって異なる。
MIPS系マイクロプロセッサの名前の由来、"Microprocessor without Interlocked Pipeline Stages"
の意味が、パイプラインがインターロックしない云々、という名前から採られたという話は覚えて
置きたい。
goto(ブランチやジャンプ)は、プロセッサのインストラクションレベルでは命令パイプラインの動作や
振る舞いに大きく関係する。
BASICのif,gotoステートメントは、プロセッサ固有のアセンブラインストラクションにコンパイル
されると直接、ジャンプ(jmp)やブランチ(brch)インストラクションとなる。
BASICコンパイラがどのようなコードを出力するかは、コンパイラの構造や最適化の程度による。
ABはコンパイラなので多少関係があるが、コンパイラ最適化に頼らずifやgotoステートメントで
パイプラインをどれだけストールさせずにコードを書けるかは興味あるテーマである。