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