「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には演算装置が含まれる。
演算ユニット自体はさらにパイプライン化されていて、命令のフェッチ(読み出し)、デコード(解読)、
エグゼキュータ(実行)
というような典型的な機能別にモジュール化されていて、処理が各機能ごとに平行して実行
される。
従来は、一つの演算ユニットが、命令のフェッチ、デコード、エグゼキュータを処理し、兼用していた。
回路が簡単で複雑でなく、実装しやすいが１命令ずつ処理する。
これらは命令のフェッチ中はデコードが出来ないし、デコードが完了しなければエグゼキュート
出来ない。
それぞれの処理シーケンスごとに機能を区分し、インストラクションを機能から分離し、
流れ作業のようにして命令をフェッチ、デコード、エグゼキュートすれば、処理が速くなる。
例えば下記のような抽象的な、無限ループの加算コードがあったとする。
label1:
i++;
j++;
k++;
goto label1;
このコードのようなインストラクションがパイプ無しのプロセッサで動作していた場合、フェッチ、デコード、
エグゼキュータが一つの演算ユニットで動作している。
パイプライン化されていないプロセッサの場合、i++;を実行するために、フェッチ、デコードし、
エグゼキュータの段階で演算が完了する。この間、i++
を処理するためにフェッチ、デコード、エグゼギュートという3ステートが消費される事になる。
全体で、三つのインクリメントを処理するループには、おおよそ9ステート(サイクル)必要であることが判る。
これに対し、パイプライン化されている場合、初期動作は実行時ペナルティがあるものの、
無限ループ処理なので、i++をフェッチ、j++をデコード、k++をエグゼキュート、という順に処理が
パイプライン化されている。
処理は無限ループなので、パイプラインがストールせず、うまく回っている場合、
見かけ上、i++をフェッチしている間、k++は処理が完了している。全体として、3ステートのみで
一回のループが処理できている。
i++をフェッチしている間、j++はデコードされ、k++は演算器によって実行されている。
次のステートでは、i++はデコード、j++は演算器で実行されているが、k++は次のループサイクル
の命令をフェッチしている。
パイプラインが停止しなければ、この一連のサイクルは見かけ上、１命令１ステートで動作して
いるように見え、ループ全体ではi++がプロセッサに投入されればk++が帰ってくるという、流れ作業が
実現している。この時、i++の実行に必要なステートは1ステートで、ループ全体を3ステートで
処理可能となっている。
パイプライン化されていなプロセッサと比較では、おおよそ1/3程度早いだろうと判る。
インストラクション的に見れば命令実行パイプラインはFILOや命令キューのようなものだ。
このような視点はクラシカルなCISC系のプロセッサには現れなかった発想で、CISC系であるPentium
ですらRISC的な設計を取り入れている現在では一般的な概念となっている。
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:
分岐命令をフェッチしても、パイプラインが、k++/k--どちらの命令を先読みするかは分岐条件
が判明するデコード後でなければ不明なので、パイプラインが機能しない。
単純に考えて、brch/jmpは演算器を使わず、フェッチ、デコード、エグゼキュートの3ステート
を使い分岐するから、それまでパイプライン上にあった命令を終わらせ一旦フラッシュする事が
必要になる。(五段パイプラインの、左側の階段状の部分のように再スタートする必要がある)
全体として演算のためのパイプライン動作が効率的に動作しているとは言いがたい。
ループ全体で考えれば、見かけ上１命令１ステートという理想的なパイプラインが動作しない。
本当に正確に言えばjump命令(goto)なども分岐なのでパイプラインをストール(失速)させる。
その他、分岐先の命令が該当する。しかし分岐予測機能を持つプロセッサであれば、ジャンプ先
のインストラクションが判るのでパイプラインをストールさせる事は無いし、
分岐予測機能がないプロセッサであれば、遅延スロットと呼ぶ擬似命令をパイプに流し込んで
パイプをストールさせないような仕組みがあるものが多い。パイプラインを止めるより無関係な命令を
流して回した方が良いという戦略である。
また、別の発想としてパイプラインを停止させる事態が発生した場合、異なるスレッドを実行
してパイプライン自体を停止させないというアイデアも考えられる。この種のプロセッサ機能は一つの物理コア
に対して二つのスレッドが実行可能で、二つの物理CPUとして認識される。
本来のデュアルコアではないが、OSからはデュアルコアとして認識される。
PentiumやAMDのプロセッサは分岐予測が含まれるし、組み込み機器のCPUでは分岐予測は複雑なので
遅延スロットを使う例がある(組み込みではSH1/SH2DSP)。
パイプラインを止めない為に複数のスレッドを実行可能とする機能はハイパースレッドと呼ばれ、Intelの
プロセッサに搭載されているほか、Power等ではSMT等とも呼ばれる。
UltraSparc T1プロセッサは、ひとつのコア上のパイプラインを停止させない為に4つのスレッドを切り替え
物理的に4CPUとして動作する。
(このようなスレッド？アプローチの対向にあるのが動的コンパイラによる最適化である)
その他、遅延スロットはMIPS,SPARCなども備えているがMIPS/SPARCは異なる世代で分岐予測機能を持ち、
Power等も分岐予測を持つ。ARMも同様だがアーキテクチャの設計や世代によって異なる。
MIPS系マイクロプロセッサの名前の由来、"Microprocessor without Interlocked Pipeline Stages"
の意味が、パイプラインがインターロックしない云々、という名前から採られたという話は覚えて
置きたい。
また、ARMの命令語のブランチ命令を含む特徴が、単にコード密度を上げるのではなく、パイプライン動作
に関する問題で、これによって分岐にどのようなメリットがあるかという点も忘れてはならない。
goto(ブランチやジャンプ)は、プロセッサのインストラクションレベルでは命令パイプラインの動作や
振る舞いに大きく関係する。
BASICのif,gotoステートメントは、プロセッサ固有のアセンブラインストラクションにコンパイル
されると直接、ジャンプ(jmp)やブランチ(brch)インストラクションとなる。
BASICコンパイラがどのようなコードを出力するかは、コンパイラの構造や最適化の程度による。
一般的なプログラミング言語のコードでは、goto,if,for-next,while文などでは分岐予測が成功する
確率が高く、関数ポインタを使った間接アドレス参照では、分岐予測が失敗する確立が高いと
言われている。この差は命令実行時にはレイテンシの差となって現れるだろう。
関数ポインタを使う例では、関数やプロシージャへのポインタを配列へ保存、参照する場合
などがある。その他、オブジェクト指向言語のVirtual関数などが該当する。
分岐先アドレスが間接参照となっているので、予測しにくいからだ。
これらを使うと、分岐予測が失敗し、パイプラインが失速する。(PentiumMに搭載されている分岐
予測回路では、ループ条件下では間接参照時でも高い確率で予測されるらしい)
コードを最適化する場合は注意が必要だ。
ABはコンパイラなので多少関係があるが、コンパイラ最適化に頼らずifや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には演算装置が含まれる。
演算ユニット自体はさらに[[パイプライン]]化されていて、命令のフェッチ(読み出し)、デコード(解読)、
エグゼキュータ(実行)
というような典型的な機能別にモジュール化されていて、処理が各機能ごとに平行して実行
される。
従来は、一つの演算ユニットが、命令のフェッチ、デコード、エグゼキュータを処理し、兼用していた。
回路が簡単で複雑でなく、[[実装]]しやすいが１命令ずつ処理する。
これらは命令のフェッチ中はデコードが出来ないし、デコードが完了しなければエグゼキュート
出来ない。
それぞれの処理[[シーケンス]]ごとに機能を区分し、インストラクションを機能から分離し、
流れ作業のようにして命令をフェッチ、デコード、エグゼキュートすれば、処理が速くなる。
例えば下記のような抽象的な、無限ループの加算コードがあったとする。
label1:
i++;
j++;
k++;
goto label1;
このコードのようなインストラクションがパイプ無しのプロセッサで動作していた場合、フェッチ、デコード、
エグゼキュータが一つの演算ユニットで動作している。
パイプライン化されていないプロセッサの場合、[[i++]];を実行するために、フェッチ、デコードし、
エグゼキュータの段階で演算が完了する。この間、i++
を処理するためにフェッチ、デコード、エグゼギュートという3ステートが消費される事になる。
全体で、三つのインクリメントを処理するループには、おおよそ9ステート(サイクル)必要であることが判る。
これに対し、パイプライン化されている場合、初期動作は実行時ペナルティがあるものの、
無限ループ処理なので、i++をフェッチ、j++をデコード、k++をエグゼキュート、という順に処理が
パイプライン化されている。
処理は無限ループなので、パイプラインがストールせず、うまく回っている場合、
見かけ上、i++をフェッチしている間、k++は処理が完了している。全体として、3ステートのみで
一回のループが処理できている。
i++をフェッチしている間、j++はデコードされ、k++は演算器によって実行されている。
次のステートでは、i++はデコード、j++は演算器で実行されているが、k++は次のループサイクル
の命令をフェッチしている。
パイプラインが停止しなければ、この一連のサイクルは見かけ上、１命令１ステートで動作して
いるように見え、ループ全体ではi++がプロセッサに投入されればk++が帰ってくるという、流れ作業が
実現している。この時、i++の実行に必要なステートは1ステートで、ループ全体を3ステートで
処理可能となっている。
パイプライン化されていなプロセッサと比較では、おおよそ1/3程度早いだろうと判る。
インストラクション的に見れば命令実行パイプラインはFILOや命令キューのようなものだ。
このような視点はクラシカルなCISC系のプロセッサには現れなかった発想で、CISC系であるPentium
ですらRISC的な設計を取り入れている現在では一般的な概念となっている。
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:
分岐命令をフェッチしても、パイプラインが、k++/k--どちらの命令を先読みするかは分岐条件
が判明するデコード後でなければ不明なので、パイプラインが機能しない。
単純に考えて、brch/jmpは演算器を使わず、フェッチ、デコード、エグゼキュートの3ステート
を使い分岐するから、それまでパイプライン上にあった命令を終わらせ一旦フラッシュする事が
必要になる。(五段パイプラインの、左側の階段状の部分のように再スタートする必要がある)
全体として演算のためのパイプライン動作が効率的に動作しているとは言いがたい。
ループ全体で考えれば、見かけ上１命令１ステートという理想的なパイプラインが動作しない。
本当に正確に言えばjump命令(goto)なども分岐なのでパイプラインをストール(失速)させる。
その他、分岐先の命令が該当する。しかし分岐予測機能を持つプロセッサであれば、ジャンプ先
のインストラクションが判るのでパイプラインをストールさせる事は無いし、
分岐予測機能がないプロセッサであれば、遅延スロットと呼ぶ擬似命令をパイプに流し込んで
パイプをストールさせないような仕組みがあるものが多い。パイプラインを止めるより無関係な命令を
流して回した方が良いという戦略である。
また、別の発想としてパイプラインを停止させる事態が発生した場合、異なる[[スレッド]]を実行
してパイプライン自体を停止させないというアイデアも考えられる。この種のプロセッサ機能は一つの物理コア
に対して二つのスレッドが実行可能で、二つの物理CPUとして認識される。
本来のデュアルコアではないが、OSからはデュアルコアとして認識される。
PentiumやAMDのプロセッサは分岐予測が含まれるし、組み込み機器のCPUでは分岐予測は複雑なので
遅延スロットを使う例がある(組み込みではSH1/SH2DSP)。
パイプラインを止めない為に複数のスレッドを実行可能とする機能はハイパースレッドと呼ばれ、Intelの
プロセッサに搭載されているほか、Power等ではSMT等とも呼ばれる。
UltraSparc T1プロセッサは、ひとつのコア上のパイプラインを停止させない為に4つのスレッドを切り替え
物理的に4CPUとして動作する。
(このようなスレッド？アプローチの対向にあるのが動的コンパイラによる最適化である)
その他、遅延スロットはMIPS,SPARCなども備えているがMIPS/SPARCは異なる世代で分岐予測機能を持ち、
Power等も分岐予測を持つ。ARMも同様だがアーキテクチャの設計や世代によって異なる。
MIPS系マイクロプロセッサの名前の由来、"Microprocessor without Interlocked Pipeline Stages"
の意味が、パイプラインがインターロックしない云々、という名前から採られたという話は覚えて
置きたい。
また、ARMの命令語のブランチ命令を含む特徴が、単にコード密度を上げるのではなく、パイプライン動作
に関する問題で、これによって分岐にどのようなメリットがあるかという点も忘れてはならない。
goto(ブランチやジャンプ)は、プロセッサのインストラクションレベルでは命令パイプラインの動作や
振る舞いに大きく関係する。
BASICのif,gotoステートメントは、プロセッサ固有のアセンブラインストラクションにコンパイル
されると直接、ジャンプ(jmp)やブランチ(brch)インストラクションとなる。
BASICコンパイラがどのようなコードを出力するかは、コンパイラの構造や最適化の程度による。
一般的なプログラミング言語のコードでは、goto,if,for-next,while文などでは分岐予測が成功する
確率が高く、[[関数]]ポインタを使った間接アドレス参照では、分岐予測が失敗する確率が高いと
言われている。この差は命令実行時にはレイテンシの差となって現れるだろう。
関数ポインタを使う例では、関数やプロシージャへのポインタを配列へ保存、参照する場合
などがある。その他、オブジェクト指向言語のVirtual関数などが該当する。
分岐先アドレスが間接参照となっているので、予測しにくいからだ。
これらを使うと、分岐予測が失敗し、パイプラインが失速する。(PentiumMに搭載されている分岐
予測回路では、ループ条件下では間接参照時でも高い確率で予測されるらしい)
コードを最適化する場合は注意が必要だ。
ABはコンパイラなので多少関係があるが、コンパイラ最適化に頼らずifやgotoステートメントで
パイプラインをどれだけ[[ストール]]させずにコードを書けるかは興味ある[[テーマ]]である。
