計算機システム Ⅱ 演習問題学科学籍番号氏名 1. 以下の分の空白を埋めなさい. CPUは, 命令フェッチ (F), 命令デコード (D), 実行 (E), 計算結果の書き戻し (W), の異なるステージの処理を反復実行するが, ある命令の計算結果の書き戻しをするまで, 次の命令のフェッチをしない場合, ( 単位時間当たりに実行できる命令数 ) が低くなる. これを解決するために考案されたのがパイプライン処理である. パイプライン処理では, 各ステージの実行結果をパイプラインレジスタに格納しながら, 各ステージの処理結果が次のステージの入力として送られる. パイプライン処理がうまく実行できなくなる状態をハザードと呼ぶ. ハザードには, ハザード, データハザード, 制御ハザード, の 3 つがある. ハザードはコンピュータの内部構成が原因で生じるハザードである. 例えば, メモリアクセス機構が単一の計算機上で, 命令フェッチと, ロード ストアが同時に起きる場合にストールが起きるのは, このハザードに起因する現象であり, 計算資源の多重化をすることで解決すべき問題である. 先の問題では, 命令用メモリとデータ用メモリを分割することで, ハザードを回避することが出来る. ハザードは, 直前の計算結果を直後の命令が参照する場合等に生じる問題である. 命令レベル並列処理が導入されていなければ, 直前の計算結果をワンクロック遅れた実行ステージで参照することができるようにするによって, 解消することが出来る. ハザードは, 条件分岐命令を読み込むと, 次にどのアドレスに格納された命令を実行すれば良いのかが判断できなくなるために生じるハザードである. これを回避する方法として, 条件分岐によってどちらの命令が読み取られるかを予測する分岐予測がある. これが的中した場合にはストールは一切生じず, 外れた場合にリカバーのために必要となるクロック数は分岐予測をしない場合に生じるストールのクロック数とである. 制御ハザードのもう一つの解消方法は, である. これは, どういう条件でどこに分岐すべきかの命令を与えた後, 即座には分岐せず, 分岐先で共通に行う命令を先に実行してから分岐するものである. キャッシュメモリとは, メモリとの間に置かれた高速なメモリであり, 主記憶装置のメモリの内容をコピーして, 高速にアクセスすることが出来る. キャッシュメモリにおいて, 主記憶のアドレスの下部 ( インデックス ) を用いてキャッシュメモリ上のインデックスを求める方法をと呼ぶ. キャッシュが正しくヒットしたかどうかは, 主記憶のアドレスのうち, インデックスを除いたの部分が一致するかどうかで判定する.
この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができる形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の内容をコピーして使うことが出来るが, 回路が複雑になりすぎるという欠点がある. これら 2 つの方法の中間に位置づけられるのが, 形キャッシュである. 先に述べたハザードの回避のために, 命令用メモリとデータ用メモリを分割するという策が示されていたが, 実際には単一のメモリ空間を使用し, を命令用とデータ用に分けることで回避することが多い. 仮想記憶ではキャッシュメモリと同じように, 低速なメモリを高速なメモリに一端溜め込んで主記憶の容量を大きく見せかける. 但し, 主記憶と2 次記憶では後者のアクセス速度のほうが圧倒的に遅いため, 可能な限りミスを避けなければならない. このため, 方式のページ管理が用いられる. 仮想アドレスを与えて, 物理アドレスを求める機構は, 連想記憶へのアクセスを伴うため, 一般に低速である. これを回避するために, 仮想アドレスから物理アドレスへの変換を一度行うとその対応関係を覚えておくという仕組みがある. キャッシュと仮想記憶の組み合わせ方としては, 直列形物理アドレスキャッシュ, 並列形物理アドレスキャッシュ, 仮想アドレスキャッシュの3 通りがある. キャッシュメモリの容量制限がある点を除いて, ハードウエア的な複雑さや動作速度の点から見て, アドレスキャッシュが一般的に用いられている. 命令レベル並列処理では, 命令レジスタや ALU 等が複数用いられるが, 特にの機構が複雑化する. 並列化には二つのアプローチがあり, コンパイラによって並列実行しやすい長い命令語を生成してそれを実行する VLIW(Very Instruction Word) や,CPU が命令間の依存関係を調べて, 実行可能な順序で並列実行可能な複数の命令をパイプラインに投入するスーパスカラがある. スーパスカラであっても, 静的な最適化は必要であり, ループアンローリングや, ソフトウエアパイプライニング, トレーススケジューリングなどの最適化技法が用いられる. スーパスカラプロセッサにおいて, 命令のステージの処理順序を入れ替えることを _ 処理と言う. これは実行と結果の書き込みについて命令の順序を無視した処理ステージの実行を行うことを指し, これにより命令の実行クロック数が短縮される. スーパスカラプロセッサにおいて, はデータ依存関係のうち, 逆依存と出力依存関係を解消することができる機構である. これはを用いた手法とリオーダバッファを用いる手法の二つがある.
CPU が周辺機器からの入出力要求の有無を調べる方法には と割り込みがある. 複数の割り込みが同時に発生しうる環境では, 割り込みの調停機構 ( ) が必要 になる. デイジーチェーン形のアービタは, 簡便な構造であるが, 常に に近いデバイスで 発生した割り込みが優先的に処理されるという欠点がある. 実際に入出力を行う段階では, 入出力用ポートを用いる専用命令で入出力を行う方法 と,, DMA の3 種類の方法が用いられる. 大量のデータを高速に転送するためには が適している. 2. 次のプログラムを, 条件分岐の回数を 1/4 になるようにループアンローリングで書き直すとど のようになるか? blt r1, r2,
3. 次のプログラムをソフトウエアパイプライニングで書き直すとどのようになるか? blt r1, r2, addi r1, r0, 0 4. 次のプログラムのレジスタリネーミングを行いたい. どのレジスタを新たなレジスタにすれば良いかを考えてプログラムを書き直しなさい. mul r1, r2, r3 add r4, r1, r5 add r5, r6, r7 add r4, r8, r9 add r10, r4, r11 add r12, r10, r13 5. プロセッサの概略性能は, クロック当たりの数 クロックである.
計算機システム Ⅱ 演習問題解答例学科学籍番号氏名 1. 以下の分の空白を埋めなさい. CPUは, 命令フェッチ (F), 命令デコード (D), 実行 (E), 計算結果の書き戻し (W), の異なるステージの処理を反復実行するが, ある命令の計算結果の書き戻しをするまで, 次の命令のフェッチをしない場合, スループット ( 単位時間当たりに実行できる命令数 ) が低くなる. これを解決するために考案されたのがパイプライン処理である. パイプライン処理では, 各ステージの実行結果をパイプラインレジスタに格納しながら, 各ステージの処理結果が次のステージの入力として送られる. パイプライン処理がうまく実行できなくなる状態をハザードと呼ぶ. ハザードには, 構造ハザード, データハザード, 制御ハザード, の 3 つがある. 構造ハザードはコンピュータの内部構成が原因で生じるハザードである. 例えば, メモリアクセス機構が単一の計算機上で, 命令フェッチと, ロード ストアが同時に起きる場合にストールが起きるのは, このハザードに起因する現象であり, 計算資源の多重化をすることで解決すべき問題である. 先の問題では, 命令用メモリとデータ用メモリを分割することで, ハザードを回避することが出来る. データハザードは, 直前の計算結果を直後の命令が参照する場合等に生じる問題である. 命令レベル並列処理が導入されていなければ, 直前の計算結果をワンクロック遅れた実行ステージで参照することができるようにするフォワーディングによって, 解消することが出来る. 制御ハザードは, 条件分岐命令を読み込むと, 次にどのアドレスに格納された命令を実行すれば良いのかが判断できなくなるために生じるハザードである. これを回避する方法として, 条件分岐によってどちらの命令が読み取られるかを予測する分岐予測がある. これが的中した場合にはストールは一切生じず, 外れた場合にリカバーのために必要となるクロック数は分岐予測をしない場合に生じるストールのクロック数と同じである. 制御ハザードのもう一つの解消方法は, 遅延分岐である. これは, どういう条件でどこに分岐すべきかの命令を与えた後, 即座には分岐せず, 分岐先で共通に行う命令を先に実行してから分岐するものである. キャッシュメモリとは, メモリと CPU の間に置かれた高速なメモリであり, 主記憶装置のメモリの内容をコピーして, 高速にアクセスすることが出来る. キャッシュメモリにおいて, 主記憶のアドレスの下部 ( インデックス ) を用いてキャッシュメモリ上のインデックスを求める方法をダイレクトマッピングと呼ぶ. キャッシュが正しくヒットしたかどうかは, 主記憶のアドレスのうち, インデックスを除いたタグの部分が一致するかどうかで判定する.
この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる競合性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができるフルアソシアティブ形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の内容をコピーして使うことが出来るが, 回路が複雑になりすぎるという欠点がある. これら 2 つの方法の中間に位置づけられるのが, セットアソシアティブ形キャッシュである. 先に述べたハザードの回避のために, 命令用メモリとデータ用メモリを分割するという策が示されていたが, 実際には単一のメモリ空間を使用し, キャッシュメモリを命令用とデータ用に分けることで回避することが多い. 仮想記憶ではキャッシュメモリと同じように, 低速なメモリを高速なメモリに一端溜め込んで主記憶の容量を大きく見せかける. 但し, 主記憶と2 次記憶では後者のアクセス速度のほうが圧倒的に遅いため, 可能な限りミスを避けなければならない. このため, フルアソシアティブ方式のページ管理が用いられる. 仮想アドレスを与えて, 物理アドレスを求める機構は, 連想記憶へのアクセスを伴うため, 一般に低速である. これを回避するために, 仮想アドレスから物理アドレスへの変換を一度行うとその対応関係を覚えておく TLB という仕組みがある. キャッシュと仮想記憶の組み合わせ方としては, 直列形物理アドレスキャッシュ, 並列形物理アドレスキャッシュ, 仮想アドレスキャッシュの3 通りがある. キャッシュメモリの容量制限がある点を除いて, ハードウエア的な複雑さや動作速度の点から見て, 並列形物理アドレスキャッシュが一般的に用いられている. 命令レベル並列処理では, 命令レジスタや ALU 等が複数用いられるが, 特にフォワーディングの機構が複雑化する. 並列化には二つのアプローチがあり, コンパイラによって並列実行しやすい長い命令語を生成してそれを実行する VLIW(Very Long Instruction Word) や,CPU が命令間の依存関係を調べて, 実行可能な順序で並列実行可能な複数の命令をパイプラインに投入するスーパスカラがある. スーパスカラであっても, 静的な最適化は必要であり, ループアンローリングや, ソフトウエアパイプライニング, トレーススケジューリングなどの最適化技法が用いられる. スーパスカラプロセッサにおいて, 命令のステージの処理順序を入れ替えることをアウトオブオーダ処理と言う. これは実行と結果の書き込みについて命令の順序を無視した処理ステージの実行を行うことを指し, これにより命令の実行クロック数が短縮される. スーパスカラプロセッサにおいて, レジスタリネーミングはデータ依存関係のうち, 逆依存と出力依存関係を解消することができる機構である. これはマッピングテーブルを用いた手法とリオーダバッファを用いる手法の二つがある.
CPU が周辺機器からの入出力要求の有無を調べる方法にはポーリングと割り込みがある. 複数の割り込みが同時に発生しうる環境では, 割り込みの調停機構 ( アービタ ) が必要になる. デイジーチェーン形のアービタは, 簡便な構造であるが, 常に CPU に近いデバイスで発生した割り込みが優先的に処理されるという欠点がある. 実際に入出力を行う段階では, 入出力用ポートを用いる専用命令で入出力を行う方法と,Memory Mapped I/O, DMA の3 種類の方法が用いられる. 大量のデータを高速に転送するためには DMA が適している. 2. 次のプログラムを, 条件分岐の回数を 1/4 になるようにループアンローリングで書き直すとど のようになるか? blt r1, r2, lw r5, 4(r3) lw r6, 8(r3) lw r7, 12(r3) addi r5, 5, r5 addi r6, 5, r6 addi r7, 5, r7 sw r5, 4(r3) sw r6, 8(r3) sw r7, 12(r3) addi r1, r1, 4 addi r3, r3, 16 blt r1, r2,
3. 次のプログラムをソフトウエアパイプライニングで書き直すとどのようになるか? blt r1, r2, addi r1, r0, 0 addi r5, 5, r4 lw r4, 4(r3) sw r5, 0(r3) addi r5, r4, 5 lw r4, 4(r3) blt r1, r2, 4. 次のプログラムのレジスタリネーミングを行いたい. どのレジスタを新たなレジスタにすれば良 いかを考えてプログラムを書き直しなさい. mul r1, r2, r3 add r4, r1, r5 add r5, r6, r7 add r4, r8, r9 add r10, r4, r11 add r12, r10, r13 mul r1, r2, r3 add r4, r1, r5 add r14, r6, r7 add r15 r8, r9 add r10, r4, r11 add r12, r10, r13 5. プロセッサの概略性能は, クロック当たりの平均実行命令数 クロック周波数である.