計 算 機 システムⅡ 試 験 問 題 学 科 学 籍 番 号 氏 名 1. 以 下 の 分 の 空 白 を 埋 めなさい.( 各 1 点 : 合 計 34 点 ) チャールズ バベッジによる 解 析 機 関,コンラッド ツーゼによる Z1, 初 期 の ENIAC,のうち, 条 件 分 岐 命 令 を 備 えていたものは, 解 析 機 関 である. ハワード エイケンが 作 成 した ASCC(ハーバード マークⅠ)は, リレー と 歯 車 が 用 いられ た 電 気 機 械 式 の 計 算 機 であるが. 後 になって 条 件 分 岐 命 令 が 組 み 込 まれている. 戦 時 中 に 暗 号 解 読 器 として 作 成 された コロッサス ( 巨 人 )にも, 条 件 分 岐 命 令 が 含 まれていな かった. コンデンサに 電 荷 を 溜 め 込 み, 電 荷 が 漏 洩 しきる 前 に 再 度 電 荷 を 貯 める ダイナミックメモリ は, 現 在 も 主 記 憶 に 使 われるメモリである.これが 最 初 に 用 いられたのは, ABC マシン である. メモリ 上 にプログラムを 配 置 する 方 式 の 計 算 機 を フォン ノイマン 型 計 算 機 と 呼 ぶが,この 計 算 機 において, 命 令 を 読 み 取 る 場 所 を 指 すレジスタは, プログラムカウンタ と 呼 ばれる. 条 件 分 岐 命 令 は,このレジスタの 値 を 計 算 結 果 に 応 じて 変 更 することで 実 現 されている. 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 種 類 の 方 法 が 用 いられる. 2. 下 図 に 示 す 命 令 フィールドを 持 つ3 種 類 の 命 令 語 があるものとする. 各 命 令 語 は 40-bit, 命 令 の 個 数 が 32,レジスタの 個 数 が 64 であるとき,このとき,aux, imm/dpl, addr にはそれ ぞれ 何 ビットが 割 り 当 てられるか? 理 由 とともに 答 えなさい.(15 点 ) dpl 命 令 の 個 数 が 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 になる. 3. あるプログラムの 中 でのロードストア 命 令 の 割 合 が 0.3 である 場 合, 下 記 の 表 の 実 行 時 間 相 対 値 はいくらになるか? 全 て 埋 めなさい.(16 点 )
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 5. インオーダ 実 行,インオーダ 完 了 のタイムチャートが 下 図 であるとき,アウトオブオーダ 実 行 ア ウトオブオーダ 完 了 をするとどうなるか 図 で 説 明 しなさい.(15 点 )
計 算 機 システムⅡ 試 験 問 題 解 答 例 学 科 学 籍 番 号 氏 名 1. 以 下 の 分 の 空 白 を 埋 めなさい.( 各 1 点 : 合 計 34 点 ) チャールズ バベッジによる 解 析 機 関,コンラッド ツーゼによる Z1, 初 期 の ENIAC,のうち, 条 件 分 岐 命 令 を 備 えていたものは, 解 析 機 関 である. ハワード エイケンが 作 成 した ASCC(ハーバード マークⅠ)は, リレー と 歯 車 が 用 いられ た 電 気 機 械 式 の 計 算 機 であるが. 後 になって 条 件 分 岐 命 令 が 組 み 込 まれている. 戦 時 中 に 暗 号 解 読 器 として 作 成 された コロッサス ( 巨 人 )にも, 条 件 分 岐 命 令 が 含 まれていな かった. コンデンサに 電 荷 を 溜 め 込 み, 電 荷 が 漏 洩 しきる 前 に 再 度 電 荷 を 貯 める ダイナミックメモリ は, 現 在 も 主 記 憶 に 使 われるメモリである.これが 最 初 に 用 いられたのは, ABC マシン である. メモリ 上 にプログラムを 配 置 する 方 式 の 計 算 機 を フォン ノイマン 型 計 算 機 と 呼 ぶが,この 計 算 機 において, 命 令 を 読 み 取 る 場 所 を 指 すレジスタは, プログラムカウンタ と 呼 ばれる. 条 件 分 岐 命 令 は,このレジスタの 値 を 計 算 結 果 に 応 じて 変 更 することで 実 現 されている. 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 種 類 の 方 法 が 用 いられる. 2. 下 図 に 示 す 命 令 フィールドを 持 つ3 種 類 の 命 令 語 があるものとする. 各 命 令 語 は 40-bit, 命 令 の 個 数 が 32,レジスタの 個 数 が 64 であるとき,このとき,aux, imm/dpl, addr にはそれ ぞれ 何 ビットが 割 り 当 てられるか? 理 由 とともに 答 えなさい.(15 点 ) dpl 命 令 の 個 数 が 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 になる. 3. あるプログラムの 中 でのロードストア 命 令 の 割 合 が 0.3 である 場 合, 下 記 の 表 の 実 行 時 間 相 対 値 はいくらになるか? 全 て 埋 めなさい.(16 点 )
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 5. インオーダ 実 行,インオーダ 完 了 のタイムチャートが 下 図 であるとき,アウトオブオーダ 実 行 ア ウトオブオーダ 完 了 をするとどうなるか 図 で 説 明 しなさい.(15 点 )