計算機システム II ・第 6 回 2015 年 10 月 29 日 今回の内容 6.1 機械語命令の実行 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6–1 6.2 パイプライン処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6–2 6.3 付録 : Intel Core i3-4330T プロセッサのパイプライン処理 . . . . . . . . . . . 6–7 6.1 機械語命令の実行 CPU はメモリから機械語命令を読み取っては、その命令を実行する、という作業を繰り返します が、この作業を細かくみるといくつかの段階に分かれていることに気づきます。たとえば、Intel 64 アーキテクチャの add 0x12(%rax), %rbx という機械語命令は、%rbx という 64 bit レジスタの内容と、%rax をベースレジスタとした変位 0x12 のレジスタ相対アドレッシングで指定されるメモリ中のデータ (64 bit) を加算して、その結 果をレジスタ %rbx に書き込む作業を行いますが、この過程は以下のようになります。 1. フェッチ メモリ (あるいはキャッシュメモリ) からこの機械語命令を読み取る。この作業を命 令のフェッチ (fetch) と呼びます。 CPU によっては、機械語命令の長さが固定されていない 場合もありますので、その場合は、命令ごとに分割する作業が伴います。通常、命令をフェッ チするとプログラムカウンタの値を進める作業が行われます。 2. デコード 命令の内容を解析して、細かな手順に分解する。フェッチされた命令のビット列を 解析して、その命令に対して行わなければならない細かな操作の並びに分解します。この作 業を命令のデコード (decode) と呼びます。この add 0x12(%rax), %rbx という命令の場合 では、たとえば、 (a) レジスタ %rax の内容を加算器の入力の 1 つへ送る。 (b) この命令のビット列から抽出した (レジスタ相対アドレッシングにおける) 変位 0x12 を 同じ加算器のもう一方の入力へ送る。 (c) この加算器の出力をアドレスとして、メモリから (キャッシュメモリを介して) 64 bit の データを読み込む。 (d) (c) でメモリから読み込まれたデータを加算器の入力の 1 つへ送る。 (e) レジスタ %rbx の内容を同じ加算器のもう一方の入力へ送る。 (f) この加算器の出力をレジスタ %rbx へ書き込む。 といった細かな操作に分解します。これらの細かな操作を行う手順を CPU 内に組み込まれ たプログラムの一種で設定することができるようになっている場合、これらの操作の 1 つ 1 つはマイクロ命令 (micro-instruction) と呼ばれることもあります。 6–1 3. 実行 命令のデコードで得られた細かな操作 (マイクロ命令) をそれぞれ実行する。この例の 場合、最終的には (a) ∼ (f) の 6 つの操作を行わなければなりませんが、命令の最終的な効果 を確定する (f) を別扱いにして、(a) から (e) までの 5 つの実行を行います。 このとき、(a) ∼ (e) の操作は、必ずしもこの順番で実行する必要はありません。この例では、 (c) は (a) や (b) の後に、(d) は (c) の後に実行しなければなりませんが、この 2 つの条件を満 してさえいれば、複数の操作 (マイクロ命令) を、同時並行的に実行することもできます。た とえば、(e) はいつでも実行することができます1 。 4. 書き戻し (確定) 実行結果を所定のレジスタやメモリアドレスに書き込んで、この命令の効果 を確定します。この例の場合では、最後の操作である (f) の実行を行います。 命令ごとに、以上のようなフェッチ、デコード、実行、書き戻しの 4 つの段階を繰り返すのが CPU の基本的な動作となります。たとえば、上で例に挙げたような命令のフェッチに 1 クロックサイク ル、デコードに 1 クロックサイクル、実行に 4 クロックサイクル、書き戻しに 1 クロックサイクル 掛かるとすると、この種の命令は、7 クロックサイクルに 1 命令のペースで実行していけることに なります。 6.2 パイプライン処理 命令のフェッチ、デコード、細かな操作 (マイクロ命令) の実行 (書き戻しを含む) の 3 つの処理はそ れぞれ、独立に作業することができますので、たとえば、機械語命令 α、β 、γ を CPU が順に実行 して行くとき、これら 3 つの処理を少しずつずらしながら、 - 時間の流れ α フェッチ デコード 実行と書き戻し β フェッチ デコード γ フェッチ 実行と書き戻し デコード 実行と書き戻し のような流れ作業の形で実行していくことができます。このような形態での機械語命令の処理を パイプライン処理と呼びます。パイプライン処理を行うことで、CPU の処理能力を向上させるこ とが可能です。1 つの命令のフェッチを開始してから、その命令の実行が完了するまでの時間 (レイ テンシ) が短くなることはありません2 が、単位時間あたりに CPU が処理できる命令の数 (スルー プット) を増やすことができます。 上のパイプライン処理の例では、命令のフェッチやデコード、各操作 (マイクロ命令群) の実行 を、一度に 1 つの命令についてのみ行っていましたが、複数の命令のフェッチを並行して行う仕組 みや、命令のデコードや加算などの演算を行う回路を複数 CPU 内に用意できれば、次の図のよう に、CPU の処理能力をさらに向上させることも可能です。 1 この命令で 2 回使用されている加算器が独立している場合はそうですが、1 つの加算器しかない場合は、(e) は (b) より後に行わなければならないことになります。 2 どちらかと言うと、むしろ長くなります。 6–2 - 時間の流れ α フェッチ β デコード フェッチ γ 実行と書き戻し デコード フェッチ 実行と書き戻し デコード 実行と書き戻し パイプラインの乱れ この図では、3 つの命令それぞれをデコードして得られた細かな操作 (マイクロ命令) を、一部並行 して実行していますが、常にそれが可能とは限りません。たとえば、α での書き戻し段階で、ある レジスタの値が変更されて、β の実行段階の最初の操作 (マイクロ命令) でそのレジスタの値を参 照する場合、これら 2 つの操作 (マイクロ命令) を実行する順序は入れ替えることができませんの で、α と β が実行される様子は - 時間の流れ α フェッチ β デコード フェッチ 実行と書き戻し デコード 実行と書き戻し のようにならざるを得ません。このような場合を含めて、次のようないくつかの要因でパイプライ ン処理の効率が低下してしまうことがあります。機械語命令のデコードで得られた細かな操作 (マ イクロ命令) の実行が遅れてしまう要因をハザード (hazard) と呼びます。 データの依存関係による乱れ (data hazard) 先に例のように、レジスタやメモリ中の同一のデー タが複数の操作 (マイクロ命令) によって扱われる場合、読み書きの順序が入れ替わらないように しなければなりません。本来は、A、B の順に実行されるべき 2 つの操作 (マイクロ命令) による同 じ場所のデータへのアクセスには、次の 4 通りの組み合わせが考えられます。 A B ケース 1: read after read 読む 読む ケース 2: write after read 読む 書く ケース 3: read after write 書く 読む ケース 4: write after write 書く 書く この内、ケース 1 を除けば、A、B の実行順序を入れ替えることはできませんので、B の実行は、A の完了を待たなければならないことになります。 現実の CPU には、このデータの依存関係による乱れを最小限に押さえるための様々な工夫が採 り入れられています。 フォワーディング (forwarding) ケース 3 に対して、レジスタやメモリに書き込まれるデータ を、実際の書き込みが起る前に、そこから読み出されたものとして使用します。このために、 A が書き込むデータが確定した段階で (書き込みが完了していなくても)、B に相当する作業 を行うことができるようになります。 レジスタの名前の付け替え (register renaming) たとえば、Intel 64 アーキテクチャにおいて 6–3 add mov sub mov %rax, %rbx $0x1234, %rax 0x56(%rax), %rcx $0x5678, %rax (%rax を %rbx へ足し込む) (定数 0x1234 を %rax へ格納) (メモリアドレス %rax + 0x56 のデータを %rcx から引く) (定数 0x5678 を %rax へ格納) というような 4 つの命令が順に実行される場合、最初の add 命令における %rax の読み出し が終わらないと、次の mov 命令による %rax への書き込みをすることはできませんので、こ こでハザードが発生する可能性があります。しかし、この一連の命令の列をよく見てみると、 mov $0x1234, %rax や次の sub 0x56(%rax), %rcx で使用されている %rax は、特に %rax である必要はなく、別のレジスタを使っても構わないことに気づきます。 CPU がこのこと に気づくことができれば、%rax の代りに別の (通常は名前のない隠れた) レジスタを使用し て、この 2 つの命令を実行することで、ハザードを回避することができます。 他にも、ケース 4 での A の書き込みを取りやめて、B の実行を早めるなどの工夫が行われます。 このような工夫を一般化していくと、機械語プログラム上は、α、β 、γ の順に並んでいる機械語 命令が、次の図のように異なる順番で実行されていくことになります3 。 - 時間の流れ α フェッチ β デコード フェッチ γ 実行 デコード フェッチ デコード 書き戻し 実行 書き戻し 実行 書き戻し このような実行の形態を、機械語命令のアウトオブオーダー実行 (out-of-order execution) と呼び ます。実行順の入れ替えが起っても、本来の順番での実行と等価な動作が保証されますから、機械 語プログラムのプログラマ (あるいはコンパイラ) は、それを特に意識する必要はありません。 資源の競合による乱れ (structural hazard) CPU 内の資源4 に関する競合が起こることで操 作 (マイクロ命令) の実行が遅れてしまうことがあります。たとえば、加算器を 2 つしか持たない CPU では、3 つ以上の加算を同時に行うことはできません。加算器を使用する 2 つの操作 (マイク ロ命令) は同時に実行できますが、3 つ目は待たされることになります。加算器などの演算回路以 外にも、命令のフェッチ、デコード、レジスタの読み書き、アクセスするメモリアドレスの計算やア ドレス変換、メモリの読み書きなどを行う回路の能力 (や個数) によって、同種の回路を同時に使用 できる操作 (マイクロ命令) の個数が制限されてしまいます。キャッシュミスによってメモリアク セスが待たされるのも資源の競合によるハザードの一種と考えることができます。 資源の競合による乱れを少なくする方法は、CPU 内に十分な資源を用意することと、同種の資 源を使用する時期をうまく調整して競合が起こり難くすることの 2 つです。命令キャッシュとデー タキャッシュを分離するのもこのような対策の一つと考えることができます。 3 CPU の内部で、実質的には本来とは異なる順に実行が完了していても、その影響が確定する時期を調整して、機械語 プログラム的には、本来の順番で完了しているように見えるようにします。これをインオーダー確定 (in-order commit) と呼びます。 4 計算機システムが動作するときに利用される限られた量や数しかないものを、一般に、資源 (resource) と呼びます。 6–4 分岐による乱れ (control hazard) パイプラインが大きく乱れる原因の 1 つに、分岐命令 (特に 条件分岐命令が) あります。分岐が発生すると、次に実行される命令が変わってしまいますので、 分岐が発生するか否か、発生するのなら分岐先のアドレスはどこかが確定するまで、次の命令を実 行することができません。命令のフェッチやデコード、一部の操作 (マイクロ命令) の実行について は、分岐が起らないものとして、その作業に取り掛かることはできますが、もし分岐が起ってしま うと、分岐先の命令のフェッチからやり直さなければなりませんので時間の無駄が非常に大きくな ります5 。分岐命令によるパイプラインの乱れを最小限に押さえるため、多くの CPU で、以下の ような工夫が採用されています。 遅延分岐 通常、分岐命令は、次に実行する命令のアドレスを変更しますが、分岐の影響を最小 限に押さえるため、分岐命令の動作の仕様を変更して、分岐が起こる時期をたとえば 1 命令 分遅らせます。つまり、分岐命令の次の命令は必ず実行され、さらにその次の命令に進むか、 それとも別のアドレスに分岐するかを分岐命令が制御します。 CPU は、実行の流れを先読 みすることができますので、これによりパイプラインの乱れを少なくすることができます。 遅延分岐命令の動作は、通常の分岐命令とは異なりますので、そのつもりで機械語プログ ラムを作成する必要があります。遅延分岐命令の次のアドレスに置かれる命令に適当な仕事 (分岐するしないに関わらず行わなければならない仕事) を割り振ることができれば効果を発 揮しますが、そのような仕事がないと遅延分岐は無意味になってしまいます。最近の CPU アーキテクチャでで遅延分岐が採用されることはあまりありません。 分岐 (先) 予測 分岐命令による分岐の発生や分岐先を予測して、その予測結果に従ってパイプ ライン処理を行います。分岐が発生するかどうかの予測を分岐予測、発生したとしてその分 岐先アドレスを予測するのを分岐先予測と呼びます。機械語プログラムに現れる多くの分岐 命令の分岐先アドレスは、プログラムカウンタ相対アドレッシングで指定されますので、分 岐予測だけでも正確に行うことができれば、パイプラインの乱れをかなり抑えることができ ます。 分岐予測の基本は、機械語プログラム中に置かれた分岐命令ごとに、そこで分岐が発生し たかどうかの履歴を CPU 内部に記録しておき、その履歴を調べて分岐の発生を予測するこ とです。実際には、すべての分岐命令のすべての履歴を保存することはできませんので、最 近実行された6 分岐命令に対象を絞るとともに、分岐が起こったどうかで次の図のように状態 遷移する飽和カウンタなどを利用した簡易的な記録に基づいて分岐予測を行います。 分岐しない 分岐した- 分岐しない 分岐した可能性が 可能性が 非常に大 大 しなかった しなかった 6 分岐しなかった 5 分岐する 可能性が 大 - 分岐する 分岐した しなかった 4 状態 (2 bit) の飽和カウンタ 可能性が 非常に大 6 分岐した パイプライン処理により、たとえば 1 クロックサイクルあたり 1 つの命令を処理するスループットを持っている CPU でも、1 つの命令のフェッチから実行完了までに掛かる時間 (レイテンシー) は、(たとえキャッシュミスがなくても) 10 クロックサイクルを越えてしまう場合があります。分岐が発生すると、この時間が無駄になることになります。 6 分岐したという意味ではありません。 6–5 CPU が分岐命令をフェッチすると分岐予測を行い、分岐しない可能性が高いと判断すれば 次 のアドレスに置かれた命令の、分岐する可能性が高いと判断すれば分岐先のアドレスの命令 のフェッチやデコードへ進みます。このとき、次に実行すると予測した命令をフェッチやデ コードを行うだけでなく、パイプライン処理の中で、その命令から得られた細かな操作 (マイ クロ命令) の実行を始めてしまう場合もあります。これを投機的実行 (speculative execution) と呼びます7 。予測が当たっていれば、特にパイプラインの乱れは生じませんが、外れれば、 投機的実行は無駄になり、すでに実行してしまっている操作 (マイクロ命令) の結果は無視す るようにしなければなりません。 条件付き命令 条件分岐命令によるパイプラインの乱れを防止するため、データ転送や演算な ど、分岐以外の仕事を条件付きで行うような命令が (CPU の命令セット内に) 用意されるこ ともあります。このような命令を、一般に条件付き命令8 と呼びます。条件付き命令は、条件 分岐命令と同様に、状態フラグなどに関する一定の条件を満した場合にのみ、データ転送や 演算 (結果の書き戻し) を行います。これらの命令では分岐は発生しませんので、パイプライ ンの乱れを最小限に抑えることができます。 以上のように、さまざまな要因で発生するパイプライン処理の乱れに対して、現在の CPU は、 それぞれ工夫を凝らして乱れを抑止したり、その影響を最小限に抑えようとしています。また、高 級言語で書かれたプログラムを機械語に変換するコンパイラも、ターゲットとなる CPU のパイプ ライン処理が効率よく働けるような機械語命令の並びを生成しようとします。 7 分岐予測や分岐先予測に伴うもの以外にも、データの依存関係の予測に伴うものなど、不確かな予測に基づいて行 われる先取りした処理一般を投機的実行と呼びます。 8 プレディケート付き命令 (predicated instruction) と呼ぶこともあります。 6–6 6.3 付録 : Intel Core i3-4330T プロセッサのパイプライン処理 瀬田学舎の情報処理実習室の PC に搭載されている Intel 社の Core i3-4330T プロセッサは、2 つ の CPU コアを内蔵していますが、各コアは次のようなパイプライン処理を行います。 1. 命令のフェッチ (fetch) と分割 (predecode) CPU コアごとに用意された 32 KiB の命令キ ャッシュを介して、主記憶装置 (メモリ) から命令を読み込みます。このとき、分岐の履歴を利 用した分岐 (先) 予測も行います。読み込まれた命令は、命令ごとに分割して命令キュー (実 行待ちの命令を並べておく待ち行列) に送ります。このとき、命令の種類に応じて (たとえば 分岐命令であるなど) 命令に印が付けられます。 2. 命令のデコード (decode) 命令キューから命令を取り出し、1 個から数個のマイクロ命令に 分割します。このとき、高速化を図るため、2 つの連続する機械語命令 (たとえば比較命令と 条件分岐命令の連続) を 1 つのマイクロ命令に合体させたりする場合もあります。生成され たマイクロ命令は、マイクロ命令キュー (実行待ちのマイクロ命令を並べておく待ち行列) に 最大 56 個保持されます。 3. マイクロ命令の実行 (out-of-order execution) 命令のデコードで得られたマイクロ命令を アウトオブオーダー実行します。1 つの CPU コアには、4 つの整数データ用 ALU が搭載さ れるなどしていますので、1 クロックサイクルごとに最大 8 個のマイクロ命令の実行を開始 することが可能です。また、最大 192 個のマイクロ命令を同時並行的に実行することができ ます。データの依存関係によるパイプラインの乱れを抑えるために、隠れたレジスタを用い たレジスタの名前の付け替えや、データ書き込み時のフォワーディング、分岐 (先) 予測に基 づく投機的実行が行われます。 4. 命令の実行結果の確定 (in-order retirement) 元の機械語命令の順番と同じ順番で、レジ スタや状態フラグ群、主記憶装置 (メモリ) 中のデータの更新を行います。分岐予測が当たっ たかどうかは、この更新 (実行結果の確定) の前に判定しておかなければなりません。 計算機システム II ・第 6 回・終り 6–7
© Copyright 2024 ExpyDoc
