の内容の一貫性 )を保つために用いられるのがスヌープキャッシュ方式である. キャッシュメモリにおいて, 主記憶のアドレスの下部 (インデックス)を用いてキャッシュメモリ上のインデックスを求める方法をダイレクトマッピングと呼ぶ.キャッシ

(1)

計算機システムⅡ試験問題学科学籍番号氏名１．以下の分の空白を埋めなさい．(各 1 点:合計 34 点)  チャールズ・バベッジによる解析機関，コンラッド・ツーゼによる Z1，初期の ENIAC，のうち，条件分岐命令を備えていたものは，解析機関である．  ハワード・エイケンが作成した ASCC（ハーバードマークⅠ）は，リレーと歯車が用いられた電気機械式の計算機であるが．後になって条件分岐命令が組み込まれている．  戦時中に暗号解読器として作成されたコロッサス（巨人）にも，条件分岐命令が含まれていなかった．  コンデンサに電荷を溜め込み，電荷が漏洩しきる前に再度電荷を貯めるダイナミックメモリは，現在も主記憶に使われるメモリである．これが最初に用いられたのは， ABC マシンである．  メモリ上にプログラムを配置する方式の計算機をフォン・ノイマン型計算機と呼ぶが，この計算機において，命令を読み取る場所を指すレジスタは，プログラムカウンタと呼ばれる．  条件分岐命令は，このレジスタの値を計算結果に応じて変更することで実現されている．  ＣＰＵは，命令フェッチ(F)，命令デコード(D)，実行(E)，計算結果の書き戻し(W)，の異なるステージの処理を反復実行するが，ある命令の計算結果の書き戻しをするまで，次の命令のフェッチをしない場合，スループット（単位時間当たりに実行できる命令数）が低くなる．これを解決するために考案されたのがパイプライン処理である．  パイプライン処理がうまく実行できなくなる状態をハザードと呼ぶ．ハザードには，・構造ハザード，・データハザード，・制御ハザード，の3 つがある．  直前の計算結果をワンクロック遅れた実行ステージで参照することができるようにするフォワーディングはデータハザードを解消するためのものである．  制御ハザードはを回避する方法として，条件分岐によってどちらの命令が読み取られるかを推定する分岐予測がある．これが的中した場合にはストールは一切生じず，外れた場合にリカバーのために必要となるクロック数は分岐予測をしない場合に生じるストールのクロック数と同じである．  制御ハザードのもう一つの解消方法は，遅延分岐である．これは，どういう条件でどこに分岐すべきかの命令を与えた後，即座には分岐せず，分岐先で共通に行う命令を先に実行してから分岐するものである．  キャッシュメモリとは，メモリと CPU の間に置かれた高速なメモリであり，主記憶装置のメモリの内容をコピーして，高速にアクセスすることが出来る．  キャッシュメモリに対して書き込みを行うとき，元のメインメモリまで書き換える方式をライトスルー方式，キャッシュラインをメモリに書き戻すまで，メモリの内容を変更しないライトバック方式がある．  特に，マルチコアの共有メモリ型計算機において，キャッシュコヒーレンシ（複数キャッシュ

(2)

の内容の一貫性）を保つために用いられるのがスヌープキャッシュ方式である．  キャッシュメモリにおいて，主記憶のアドレスの下部（インデックス）を用いてキャッシュメモリ上のインデックスを求める方法をダイレクトマッピングと呼ぶ．キャッシュが正しくヒットしたかどうかは，主記憶のアドレスのうち，インデックスを除いたタグの部分が一致するかどうかで判定する．  この方法では，複数のアドレスが同じインデックスに対応づけられる可能性があるため，キャッシュラインのコピーと書き戻しが交互に起きる競合性のミスが発生する可能性がある．  これを回避するために考案されたのが，連想メモリアクセスができるフルアソシアティブ形キャッシュである．この方式は，キャッシュに余裕がある限り主記憶の内容をコピーして使うことが出来るが，回路が複雑になりすぎるという欠点がある．  これら 2 つの方法の中間に位置づけられるのが，セットアソシアティブ形キャッシュである．  先に述べたハザードの回避のために，命令用メモリとデータ用メモリを分割するという策が示されていたが，実際には単一のメモリ空間を使用し，キャッシュメモリを命令用とデータ用に分けることで回避することが多い．  仮想記憶ではキャッシュメモリと同じように，低速なメモリを高速なメモリに一端溜め込んで主記憶の容量を大きく見せかける．但し，主記憶と２次記憶では後者のアクセス速度のほうが圧倒的に遅いため，可能な限りミスを避けなければならない．このため，フルアソシアティブ方式のページ管理が用いられる．  仮想アドレスを与えて，物理アドレスを求める機構は，連想記憶へのアクセスを伴うため，一般に低速である．これを回避するために，仮想アドレスから物理アドレスへの変換を一度行うとその対応関係を覚えておく TLB という仕組みがある．  キャッシュと仮想記憶の組み合わせ方としては，直列形物理アドレスキャッシュ，並列形物理アドレスキャッシュ，仮想アドレスキャッシュの３通りがある．キャッシュメモリの容量制限がある点を除いて，ハードウエア的な複雑さや動作速度の点から見て，並列形物理アドレスキャッシュが一般的に用いられている．  命令レベル並列処理では，命令レジスタや ALU 等が複数用いられるが，特にフォワーディングの機構が複雑化する．  並列化には二つのアプローチがあり，コンパイラによって並列実行しやすい長い命令語を生成してそれを実行するVLIW（Very Long Instruction Word）や，CPU が命令間の依存関係を調べて，実行可能な順序で並列実行可能な複数の命令をパイプラインに投入するスーパスカラがある．  スーパスカラプロセッサで，命令ステージの処理順序を入れ替えることをアウトオブオーダ処理と言う．これは実行と結果の書き込みについて命令の順序を無視した処理ステージの実行を行うことを指し，これにより命令の実行クロック数が短縮される．  スーパスカラプロセッサにおいて，逆依存と出力依存関係を解消する方法としてレジスタリネーミングがある．これはマッピングテーブルを用いた手法とリオーダバッファを用いる手法の二つ

(3)

がある．  CPU が周辺機器からの入出力要求の有無を調べる方法にはポーリングと割り込みがある．  複数の割り込みが同時に発生しうる環境では，割り込みの調停機構（アービタ）が必要になる．デイジーチェーン形のアービタは，簡便な構造であるが，常に CPU に近いデバイスで発生した割り込みが優先的に処理されるという欠点がある．  実際に入出力を行う段階では，入出力用ポートを用いる専用命令で入出力を行う方法と，Memory Mapped I/O, DMA の３種類の方法が用いられる．

2. 下図に示す命令フィールドを持つ３種類の命令語があるものとする．各命令語は 40-bit，命

令の個数が

32，レジスタの個数が 64 であるとき，このとき，aux, imm/dpl, addr にはそれ

ぞれ何ビットが割り当てられるか？理由とともに答えなさい．

（１５点）

３．あるプログラムの中でのロードストア命令の割合が 0.3 である場合，下記の表の実行時間相対値はいくらになるか？全て埋めなさい．（16 点）

命令の個数が

32=2

5

_{個なので，}

_{op には 5-bit が割りあてられる．レジスタは 64=2}

6

_{個なので，}

各レジスタには

6-bit が割り当てられる．したがって，R 型の場合は，40-5-3*6=17 で，aux

は

17bit．I 型の場合は，40-5-2*6=23 で imm/dpl は 23-bit．A 型の命令では，40-5=35 で，

addr は 35-bit になる．

(4)

４．次のプログラムをソフトウエアパイプライニングで書き直すとどのようになるか？（20 点） 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 ５．インオーダ実行，インオーダ完了のタイムチャートが下図であるとき，アウトオブオーダ実行アウトオブオーダ完了をするとどうなるか図で説明しなさい．（15 点）

(5)

計算機システムⅡ試験問題解答例学科学籍番号氏名１．以下の分の空白を埋めなさい．(各 1 点:合計 34 点)  チャールズ・バベッジによる解析機関，コンラッド・ツーゼによる Z1，初期の ENIAC，のうち，条件分岐命令を備えていたものは，解析機関である．  ハワード・エイケンが作成した ASCC（ハーバードマークⅠ）は，リレーと歯車が用いられた電気機械式の計算機であるが．後になって条件分岐命令が組み込まれている．  戦時中に暗号解読器として作成されたコロッサス（巨人）にも，条件分岐命令が含まれていなかった．  コンデンサに電荷を溜め込み，電荷が漏洩しきる前に再度電荷を貯めるダイナミックメモリは，現在も主記憶に使われるメモリである．これが最初に用いられたのは， ABC マシンである．  メモリ上にプログラムを配置する方式の計算機をフォン・ノイマン型計算機と呼ぶが，この計算機において，命令を読み取る場所を指すレジスタは，プログラムカウンタと呼ばれる．  条件分岐命令は，このレジスタの値を計算結果に応じて変更することで実現されている．  ＣＰＵは，命令フェッチ(F)，命令デコード(D)，実行(E)，計算結果の書き戻し(W)，の異なるステージの処理を反復実行するが，ある命令の計算結果の書き戻しをするまで，次の命令のフェッチをしない場合，スループット（単位時間当たりに実行できる命令数）が低くなる．これを解決するために考案されたのがパイプライン処理である．  パイプライン処理がうまく実行できなくなる状態をハザードと呼ぶ．ハザードには，・構造ハザード，・データハザード，・制御ハザード，の3 つがある．  直前の計算結果をワンクロック遅れた実行ステージで参照することができるようにするフォワーディングはデータハザードを解消するためのものである．  制御ハザードはを回避する方法として，条件分岐によってどちらの命令が読み取られるかを推定する分岐予測がある．これが的中した場合にはストールは一切生じず，外れた場合にリカバーのために必要となるクロック数は分岐予測をしない場合に生じるストールのクロック数と同じである．  制御ハザードのもう一つの解消方法は，遅延分岐である．これは，どういう条件でどこに分岐すべきかの命令を与えた後，即座には分岐せず，分岐先で共通に行う命令を先に実行してから分岐するものである．  キャッシュメモリとは，メモリと CPU の間に置かれた高速なメモリであり，主記憶装置のメモリの内容をコピーして，高速にアクセスすることが出来る．  キャッシュメモリに対して書き込みを行うとき，元のメインメモリまで書き換える方式をライトスルー方式，キャッシュラインをメモリに書き戻すまで，メモリの内容を変更しないライトバック方式がある．  特に，マルチコアの共有メモリ型計算機において，キャッシュコヒーレンシ（複数キャッシュ

(6)

の内容の一貫性）を保つために用いられるのがスヌープキャッシュ方式である．  キャッシュメモリにおいて，主記憶のアドレスの下部（インデックス）を用いてキャッシュメモリ上のインデックスを求める方法をダイレクトマッピングと呼ぶ．キャッシュが正しくヒットしたかどうかは，主記憶のアドレスのうち，インデックスを除いたタグの部分が一致するかどうかで判定する．  この方法では，複数のアドレスが同じインデックスに対応づけられる可能性があるため，キャッシュラインのコピーと書き戻しが交互に起きる競合性のミスが発生する可能性がある．  これを回避するために考案されたのが，連想メモリアクセスができるフルアソシアティブ形キャッシュである．この方式は，キャッシュに余裕がある限り主記憶の内容をコピーして使うことが出来るが，回路が複雑になりすぎるという欠点がある．  これら 2 つの方法の中間に位置づけられるのが，セットアソシアティブ形キャッシュである．  先に述べたハザードの回避のために，命令用メモリとデータ用メモリを分割するという策が示されていたが，実際には単一のメモリ空間を使用し，キャッシュメモリを命令用とデータ用に分けることで回避することが多い．  仮想記憶ではキャッシュメモリと同じように，低速なメモリを高速なメモリに一端溜め込んで主記憶の容量を大きく見せかける．但し，主記憶と２次記憶では後者のアクセス速度のほうが圧倒的に遅いため，可能な限りミスを避けなければならない．このため，フルアソシアティブ方式のページ管理が用いられる．  仮想アドレスを与えて，物理アドレスを求める機構は，連想記憶へのアクセスを伴うため，一般に低速である．これを回避するために，仮想アドレスから物理アドレスへの変換を一度行うとその対応関係を覚えておく TLB という仕組みがある．  キャッシュと仮想記憶の組み合わせ方としては，直列形物理アドレスキャッシュ，並列形物理アドレスキャッシュ，仮想アドレスキャッシュの３通りがある．キャッシュメモリの容量制限がある点を除いて，ハードウエア的な複雑さや動作速度の点から見て，並列形物理アドレスキャッシュが一般的に用いられている．  命令レベル並列処理では，命令レジスタや ALU 等が複数用いられるが，特にフォワーディングの機構が複雑化する．  並列化には二つのアプローチがあり，コンパイラによって並列実行しやすい長い命令語を生成してそれを実行するVLIW（Very Long Instruction Word）や，CPU が命令間の依存関係を調べて，実行可能な順序で並列実行可能な複数の命令をパイプラインに投入するスーパスカラがある．  スーパスカラプロセッサで，命令ステージの処理順序を入れ替えることをアウトオブオーダ処理と言う．これは実行と結果の書き込みについて命令の順序を無視した処理ステージの実行を行うことを指し，これにより命令の実行クロック数が短縮される．  スーパスカラプロセッサにおいて，逆依存と出力依存関係を解消する方法としてレジスタリネーミングがある．これはマッピングテーブルを用いた手法とリオーダバッファを用いる手法の二つ

(7)

がある．  CPU が周辺機器からの入出力要求の有無を調べる方法にはポーリングと割り込みがある．  複数の割り込みが同時に発生しうる環境では，割り込みの調停機構（アービタ）が必要になる．デイジーチェーン形のアービタは，簡便な構造であるが，常に CPU に近いデバイスで発生した割り込みが優先的に処理されるという欠点がある．  実際に入出力を行う段階では，入出力用ポートを用いる専用命令で入出力を行う方法と，Memory Mapped I/O, DMA の３種類の方法が用いられる．

2. 下図に示す命令フィールドを持つ３種類の命令語があるものとする．各命令語は 40-bit，命

令の個数が

32，レジスタの個数が 64 であるとき，このとき，aux, imm/dpl, addr にはそれ

ぞれ何ビットが割り当てられるか？理由とともに答えなさい．（１５点）

３．あるプログラムの中でのロードストア命令の割合が 0.3 である場合，下記の表の実行時間相対値はいくらになるか？全て埋めなさい．（16 点）

命令の個数が

32=2

5

_{個なので，}

_{op には 5-bit が割りあてられる．レジスタは 64=2}

6

_{個なので，}

各レジスタには

6-bit が割り当てられる．したがって，R 型の場合は，40-5-3*6=17 で，aux

は

17bit．I 型の場合は，40-5-2*6=23 で imm/dpl は 23-bit．A 型の命令では，40-5=35 で，

addr は 35-bit になる．

(8)

４．次のプログラムをソフトウエアパイプライニングで書き直すとどのようになるか？（20 点） 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 ５．インオーダ実行，インオーダ完了のタイムチャートが下図であるとき，アウトオブオーダ実行アウトオブオーダ完了をするとどうなるか図で説明しなさい．（15 点）