《計算機系統(tǒng)結(jié)構(gòu)》電子教案(清華2版)

2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 2 教 學(xué) 計 劃 教 材 ： 計 算 機 系 統(tǒng) 結(jié) 構(gòu) （ 第 二 版 ）鄭 緯 民 等清 華 大 學(xué) 出 版 社 參 考 書 ： 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 復(fù) 習(xí) 與 考 試 指 導(dǎo) 鄭 緯 民 等高 等 教 育 出 版 社 總 學(xué) 時 ： 40 第 1章 ： 2 第 2章 ： 4 第 3章 ： 6 第 4章 ： 4 第 5章 ： 6 第 6章 ： 2 第 7章 ： 6 第 8章 ： 2 第 9、 10章 ： 2 習(xí) 題 課 ： 4 復(fù) 習(xí) 課 ： 2 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 3 第 一 章 基 本 概 念 （ P1） 本 章 介 紹 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 一 些 基 本 知 識 。 包 括 定 性 知 識 和 定 量 知識 兩 大 組 內(nèi) 容 。 為 了 便 于 學(xué) 習(xí) ， 本 章 各 節(jié) 重 新 編 號 ， 與 教 材 編 號 不 同 。 定 性 知 識 ： 本 課 程 經(jīng) 常 使 用 的 一 些 名 詞 概 念 ， 以 及 對 計 算 機 的 定 性認 識 、 分 析 方 法 。 定 量 知 識 ： 對 計 算 機 性 能 進 行 定 量 評 價 的 幾 個 重 要 公 式 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 4 1.1.1 什 么 是 計 算 機 系 統(tǒng) 結(jié) 構(gòu) ？ （ P4）別 名 ： 計 算 機 體 系 結(jié) 構(gòu) ， 英 文 名 ： Computer Architecture（ 其 中 Architecture 的 原 義 是 “ 建 筑 學(xué) ” ）學(xué) 科 定 義 ： 提 高 計 算 機 性 能 的 系 統(tǒng) 理 論特 點 ： 綜 合 性 ： 將 硬 、 軟 件 統(tǒng) 一 考 慮 ， 整 體 優(yōu) 化 ， 強 調(diào) 功 能 效 果 （ 因 為 計 算 機 是 一 種 工 具 ） ，偏 重 于 硬 件 ； 結(jié) 構(gòu) 性 ： 與 微 電 子 學(xué) 扮 演 的 角 色 不 同 ， 它 不 研 究 器 件 性 能 ， 而 研 究 系 統(tǒng) 的 結(jié) 構(gòu) ， 特 別 是并 行 處 理 結(jié) 構(gòu) ， 即 通 過 時 間 重 疊 分 配 來 縮 短 程 序 執(zhí) 行 時 間 ； 定 量 性 ： 用 數(shù) 學(xué) 建 模 方 法 ， 盡 可 能 精 確 地 計 算 各 種 技 術(shù) 的 性 能 高 低 。1.1 定 性 知 識 幾 個 基 本 概 念 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 5 實 體 定 義 ： 廣 義 定 義 ： 使 用 者 必 須 了 解 的 機 器 外 部 特 性 知 識 狹 義 定 義 ： 低 級 語 言 程 序 員 必 須 了 解 的 機 器 外 部 特 性 知 識 。 （ 這 里 的 “ 外部 特 性 ” 特 指 整 個 硬 件 的 外 部 特 性 ）（ 注 ： 速 度 /運 行 時 間 不 屬 于 系 統(tǒng) 結(jié) 構(gòu) ， 因 為 只 看 最 終 運 算 結(jié) 果 ）透 明 性 概 念 ： 使 用 者 可 以 不 了 解 的 知 識 。（ 意 義 ： 讓 一 部 分 技 術(shù) 透 明 ， 可 使 同 一 種 功 能 容 納 多 種 實 現(xiàn) 方 法 ）附 ： “ 計 算 機 系 統(tǒng) 結(jié) 構(gòu) ” 學(xué) 科 定 義 的 3個 版 本 版 本 1： 合 理 分 配 硬 軟 件 分 工 的 方 法 ； 版 本 2： 程 序 員 必 須 了 解 的 硬 件 知 識 ； 版 本 3： 提 高 計 算 機 性 能 的 理 論 。 （ 意 義 ： 目 前 流 行 的 主 要 技 術(shù) ， 都 屬 于 并 行 處 理 類 型 ， 即 通 過 時 間 重 疊 分 布 來 縮 短 總 執(zhí) 行 時間 。 課 文 各 章 都 體 現(xiàn) 了 這 一 點 ） 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 廣 義 、 狹 義 定 義 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 6 “ 計 算 機 系 統(tǒng) 結(jié) 構(gòu) ” 狹 義 定 義 包 含 的 內(nèi) 容 （ P4）1.數(shù) 據(jù) 表 示 （ 硬 件 能 夠 直 接 識 別 和 處 理 的 數(shù) 據(jù) 類 型 和 格 式 等 ） ；2.尋 址 方 式 （ 包 括 最 小 尋 址 單 位 、 尋 址 方 式 的 種 類 、 表 示 和 地 址 計 算 等 ） ；3.寄 存 器 組 織 （ 包 括 各 種 寄 存 器 的 配 置 數(shù) 目 和 功 能 定 義 ） ；4.指 令 系 統(tǒng) （ 包 括 機 器 指 令 的 操 作 類 型 和 格 式 、 指 令 間 的 排 序 方 式 和 控 制 機構(gòu) 等 ） ；5.存 儲 系 統(tǒng) （ 包 括 編 址 方 式 、 存 儲 容 量 、 最 大 編 址 空 間 等 ） ；6.中 斷 機 構(gòu) （ 中 斷 源 的 分 類 管 理 和 中 斷 服 務(wù) 功 能 設(shè) 計 ） ； 7.機 器 工 作 狀 態(tài) （ 如 管 態(tài) 、 目 態(tài) 等 ） 的 定 義 和 切 換 ；8.輸 入 /輸 出 子 系 統(tǒng) 結(jié) 構(gòu) 與 管 理 ；9.信 息 保 護 手 段 及 其 實 現(xiàn) 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 7 第 5級 專 用 應(yīng) 用 語 言 機 器 特 定 應(yīng) 用 用 戶 （ 使 用 特 定 應(yīng) 用 語 言 ） （ 經(jīng) 應(yīng) 用 程 序 翻 譯 成 高 級 語 言 ）第 4級 通 用 高 級 語 言 機 器 高 級 語 言 程 序 員 （ 使 用 通 用 高 級 語 言 ） （ 經(jīng) 編 譯 程 序 翻 譯 成 匯 編 語 言 ）第 3級 匯 編 語 言 機 器 匯 編 語 言 程 序 員 （ 使 用 匯 編 語 言 ） （ 經(jīng) 匯 編 程 序 翻 譯 成 機 器 語 言 、 操 作 系 統(tǒng) 原 語 ）第 2級 操 作 系 統(tǒng) 語 言 機 器 操 作 系 統(tǒng) 用 戶 （ 使 用 操 作 系 統(tǒng) 原 語 ） （ 經(jīng) 原 語 解 釋 子 程 序 翻 譯 成 機 器 語 言 ）第 1級 傳 統(tǒng) 機 器 語 言 機 器 傳 統(tǒng) 機 器 程 序 員 （ 使 用 二 進 制 機 器 語 言 ） （ 由 微 程 序 解 釋 成 微 指 令 序 列 ）第 0級 微 指 令 語 言 機 器 微 指 令 程 序 員 （ 使 用 微 指 令 語 言 ） （ 由 硬 件 譯 碼 器 解 釋 成 控 制 信 號 序 列 ） 圖 1.1 計 算 機 系 統(tǒng) 的 多 級 層 次 模 型 1.1.2 計 算 機 系 統(tǒng) 的 多 級 層 次 模 型 （ P3） 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 8 1.1.3 其 他 重 要 名 詞 概 念 （ 自 學(xué) ）計 算 機 組 成 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 邏 輯 實 現(xiàn) 。 （ P5）計 算 機 實 現(xiàn) 計 算 機 組 成 的 物 理 實 現(xiàn) 。 （ P5）計 算 機 系 統(tǒng) 設(shè) 計 的 3種 主 要 方 法 ： “ 由 下 往 上 ” 、 “ 由 上 往 下 ” 、 “ 由中 間 開 始 ” 。 （ P14）系 列 機 （ P23）兼 容 性 （ P24）模 擬 （ P24）仿 真 （ P24）虛 擬 機 （ P24） 宿 主 機 （ P24）并 行 性 求 解 一 個 問 題 的 若 干 操 作 在 時 間 安 排 上 的 可 重 疊 性 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 9 1.1.4 馮 .諾 依 曼 （ Von Neumann） 型 機 器 的 特 點 （ P22） 傳 統(tǒng) 計 算 機 又 稱 為 馮 .諾 依 曼 型 機 器 ， 它 由 運 算 器 、 控 制 器 、 存 儲 器 、 輸入 設(shè) 備 和 輸 出 設(shè) 備 5部 分 組 成 ， 并 具 有 如 下 特 點 ： 1.以 運 算 器 為 數(shù) 據(jù) 流 動 中 樞 ， 以 控 制 器 為 控 制 命 令 中 樞 ； 2.存 儲 程 序 并 且 執(zhí) 行 ， 程 序 象 數(shù) 據(jù) 一 樣 可 以 修 改 ； 3.存 儲 器 按 地 址 訪 問 ， 線 性 順 序 編 址 ； 4.程 序 順 序 執(zhí) 行 ； 5.指 令 由 操 作 碼 與 操 作 數(shù) 兩 部 分 組 成 ； 6.數(shù) 據(jù) 用 二 進 制 編 碼 ； 7.機 器 由 硬 件 與 軟 件 組 成 ， 硬 件 功 能 不 能 改 變 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 10 1.1.5 現(xiàn) 代 計 算 機 系 統(tǒng) 的 分 類 （ Flynn分 類 法 ， P6）按 照 指 令 流 和 數(shù) 據(jù) 流 的 多 倍 性 狀 況 把 計 算 機 分 為 ：1.單 指 令 流 單 數(shù) 據(jù) 流 （ SISD-Single Instruction Stream Single Data Stream）2.單 指 令 流 多 數(shù) 據(jù) 流 （ SIMD-Single Instruction Stream Multiple Data Stream）3.多 指 令 流 單 數(shù) 據(jù) 流 （ MISD-Multiple Instruction Stream Single Data Stream）4.多 指 令 流 多 數(shù) 據(jù) 流 （ MIMD-Multiple Instruction Stream Multiple Data Stream） 思 考 題 （ 不 交 ） ： P32， 題 7， 題 8 ， 題 9 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 11 1.2 定 量 知 識 3個 性 能 公 式1.2.1 Amdahl定 律 （ 加 快 經(jīng) 常 性 事 件 原 理 ， P9） eeenon SFFTTS )1( 1其 中 ： Sn 全 局 加 速 比 ； To 原 執(zhí) 行 時 間 （ old） ； Tn 新 執(zhí) 行 時 間 （ new） ； Se 被 改 進 部 分 的 局 部 加 速 比 ； Fe 被 改 進 部 分 原 執(zhí) 行 時 間 占 原 來 總 時 間 的 百 分 比 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 12 Amdahl定 律 的 推 導(dǎo) eeenon eeeon eeoo SFFTTS SFFTT FFTT )1( 1 )1( )1(根 據(jù) 加 速 比 定 義 ， 有 ： ：操 作 加 快 ， 總 時 間 降 為改 進 之 后 由 于 其 中 部 分 ，間 可 寫 為 ：改 進 之 前 程 序 運 行 總 時 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 13 Amdahl定 律 的 圖 形 Sn 極 限 2 = 21 1 eF 極 限 1 = 11 1 eF Fe=Fe2 Fe=Fe1 1.0 （ 設(shè) Fe2 Fe1） 0.0 1.0 Se 圖 1.2 Amdahl定 律 的 圖 形 從 圖 1.2可 以 看 出 ， 增 大 Se和 Fe對 Sn都 有 提 升 作 用 ； 但 當(dāng) Fe固 定 時， 一 味 增 大 Se對 Sn的 作 用 會 越 來 越 不 顯 著 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 14 Amdahl定 律 的 意 義 Amdahl定 律 指 出 ， 在 局 部 改 進 力 度 Se相 同 的 情 況 下 ， 選 擇 原 來 最 費 時 間（ 即 Fe最 大 ） 的 工 作 內(nèi) 容 作 為 改 進 對 象 ， 可 以 獲 得 最 大 的 全 局 改 進 效 果 Sn。 所 以 可 以 認 為 ， Amdahl定 律 （ 加 快 最 費 時 間 的 事 件 ） 是 經(jīng) 濟 學(xué) 的 “ 爛 桶板 原 理 ” （ 木 桶 的 最 大 盛 水 量 由 最 短 的 桶 板 決 定 ， 要 增 加 木 桶 盛 水 量 ， 必須 將 短 木 板 加 長 ） 的 一 個 定 量 化 詮 釋 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 15 1.2.2 CPI與 程 序 執(zhí) 行 時 間 Te（ P11）CPI是 衡 量 CPU執(zhí) 行 指 令 效 率 的 重 要 指 標(biāo) 。 讓 我 們 先 考 慮 一 個 標(biāo) 準(zhǔn)測 速 程 序 的 全 部 執(zhí) 行 時 間 Te和 其 中 所 有 第 i種 指 令 的 累 計 時 間 Ti， 易知 的 加 權(quán) 平 均 值 。為 所 有， 它 表 明）（或 者 寫 為 ）（ 的 關(guān) 系與一 式 ， 可 以 得 到比 較 上 面 第 一 式 與 最 后 寫另 一 方 面 ， 我 們 又 可 以， ini iini ii ni iini iini ie ni iiiie CPICPICPIICICCPI CPIICCPIIC CYCLECPIICCYCLECPIICTT ICICfCYCLE CYCLECPIICT CYCLECPIICT CPICPI )()( 1 其中： 11 i111 1 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 16 1.2.3 每 秒 百 萬 指 令 數(shù) MIPS與 每 秒 百 萬 浮 點 數(shù) MFLOPS（ P11）。， 主 要 用 于 向 量 計 算 機條 數(shù)每 次 浮 點 運 算 所 需 指 令 ；， 主 要 用 于 標(biāo) 量 計 算 機MIPSMFLOPS CPIfCYCLECPIIC ICTICMIPS e 666 101010 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 17 本 章 小 結(jié) 本 章 從 定 性 知 識 和 定 量 知 識 兩 個 方 面 介 紹 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概念 。 有 關(guān) 重 點 如 下 ：(1) 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 廣 義 定 義 與 狹 義 定 義 （ 9項 內(nèi) 容 ） ， 計 算 機 系 統(tǒng) 結(jié)構(gòu) 與 計 算 機 組 成 的 主 要 分 工 ；(2) 計 算 機 系 統(tǒng) 的 多 級 層 次 模 型 （ 6級 ） ， 以 及 基 于 該 模 型 的 透 明 性 判 斷方 法 ；(3) 計 算 機 實 現(xiàn) 、 計 算 機 系 統(tǒng) 設(shè) 計 的 主 要 思 路 、 模 擬 、 仿 真 、 虛 擬 機 、宿 主 機 、 系 列 機 、 兼 容 性 、 并 行 性 等 重 要 名 詞 的 含 義 ；(4) 馮 .諾 依 曼 型 機 器 的 7個 特 點 ；(5) 現(xiàn) 代 計 算 機 系 統(tǒng) 分 類 的 Flynn法 （ 4類 ） ；(6) Amdahl定 律 ；(7) 平 均 周 期 數(shù) CPI公 式 ， 程 序 執(zhí) 行 時 間 Te公 式 ； (8) 每 秒 百 萬 指 令 數(shù) MIPS公 式 ， 每 秒 百 萬 浮 點 數(shù) MFLOPS公 式 。習(xí) 題 ： P33 ， 題 12（ 快 20倍 就 是 Se=20） ， 題 15， 題 19。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 18 第 二 章 指 令 系 統(tǒng) （ P36） 本 章 介 紹 指 令 系 統(tǒng) 設(shè) 計 中 2個 最 基 本 的 內(nèi) 容 ： 數(shù) 據(jù) 表 示 、 操 作 碼 優(yōu)化 。2.1 數(shù) 據(jù) 表 示 數(shù) 據(jù) 表 示 就 是 計 算 機 硬 件 能 夠 直 接 辨 認 與 處 理 的 數(shù) 據(jù) 類 型 。人 們 通 常 使 用 的 數(shù) 據(jù) 類 型 有 整 數(shù) 、 實 數(shù) 、 邏 輯 數(shù) （ 布 爾 數(shù) ） 、 字 符 串 、隊 列 、 堆 棧 、 鏈 表 、 文 件 等 ， 它 們 的 運 算 方 法 各 不 相 同 。 所 謂 “ 硬 件 能 夠 直 接 辨 認 與 處 理 ” ， 指 的 是 對 該 數(shù) 據(jù) 類 型 的 各 種 運算 操 作 都 有 相 應(yīng) 的 實 現(xiàn) 硬 件 電 路 。 硬 件 不 能 直 接 辨 認 與 處 理 的 數(shù) 據(jù) 類 型 就 要 根 據(jù) 數(shù) 據(jù) 結(jié) 構(gòu) 的 知 識 編 制軟 件 轉(zhuǎn) 化 為 硬 件 能 處 理 的 數(shù) 據(jù) 類 型 。 下 面 介 紹 通 用 型 計 算 機 數(shù) 據(jù) 表 示 集 合 中 的 一 個 基 本 成 員 浮 點數(shù) 據(jù) 的 分 析 與 設(shè) 計 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 19 2.1.1 浮 點 數(shù) 據(jù) 表 示 （ P38， P39） 浮 點 數(shù) 據(jù) 就 是 高 級 語 言 課 程 中 所 說 的 “ 實 型 數(shù) ” 。 2.1.1.1 浮 點 數(shù) 的 組 成 浮 點 數(shù) 的 組 成 與 人 們 通 常 所 說 的 “ 科 學(xué) 記 數(shù) 法 ” 非 常 相 似 ， 唯 一 不 同 的 是 各 部 分均 為 有 限 位 數(shù) ， 如 下 所 示 emrmN 它 的 主 要 參 數(shù) 有 8個 ： m 尾 數(shù) ， 一 般 為 純 小 數(shù) ， 符 合 規(guī) 格 化 原 則 （ 即 最 高 位 的 絕 對 值 不 為 0） ，用 原 碼 或 補 碼 表 示 ； e 階 碼 ， 整 數(shù) ， 常 用 移 碼 表 示 （ 見 下 文 解 釋 ） ； r m 尾 數(shù) 的 基 值 ， 簡 稱 尾 基 ， 常 見 的 有 2進 制 、 8進 制 、 16進 制 、 10進 制 等 ，選 定 以 后 不 變 ； re 階 碼 的 基 值 ， 簡 稱 階 基 ， 目 前 都 采 用 2， 也 是 選 定 以 后 不 變 ； p 尾 數(shù) 的 位 數(shù) ， 未 將 符 號 位 計 入 ； q 階 碼 的 位 數(shù) ， 未 將 符 號 位 計 入 。 mf 尾 數(shù) 的 符 號 ， 表 示 數(shù) 的 正 負 ， 簡 稱 數(shù) 符 ； ef 階 碼 的 符 號 ， 表 示 階 碼 的 正 負 ， 簡 稱 階 符 。 但 對 移 碼 表 示 來 說 ， 這 僅 僅是 額 外 的 1位 2進 制 數(shù) ， 不 決 定 正 負 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 20 移 碼 （ P41） 移 碼 是 一 種 2進 制 記 數(shù) 方 法 ， 它 的 真 值 等 于 相 同 編 碼 的 無 符 號 數(shù) 加 上 一 個 指 定 的 偏移 量 d。 例 如 ， 同 樣 是 2進 制 編 碼 000000 111111， 看 作 6位 無 符 號 數(shù) 時 的 取 值 范 圍是 0 63， 而 看 作 6位 移 -10碼 的 取 值 范 圍 就 是 10 53。 如 下 圖 所 示 。 移 碼 是 一 種 有 符 號 數(shù) ， 但 它 的 最 高 位 通 常 不 決 定 數(shù) 的 正 負 ， 不 應(yīng) 稱 為 符 號 位 。 它 的獨 特 之 處 在 于 其 最 小 取 值 的 2進 制 編 碼 是 全 0， 這 給 機 器 零 的 判 斷 和 處 理 電 路 設(shè) 計 帶來 很 大 方 便 。 十 進 制 真 值 63 無 符 號 數(shù) 53 移 -10 碼 0 111111-10 二進制編碼圖2.1 移碼與無符號數(shù)的比較實例 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 21 2.1.1.2 浮 點 數(shù) 的 機 內(nèi) 格 式 （ P39） 一 種 浮 點 數(shù) 中 每 個 數(shù) 據(jù) 的 尾 基 rm、 階 基 re都 是 相 同 的 ， 在 設(shè) 計 運算 電 路 已 經(jīng) 作 為 默 認 值 來 使 用 ， 各 個 具 體 數(shù) 據(jù) 在 存 儲 時 只 需 要 存 入如 下 參 數(shù) 即 可 ： 各 字 段 位 數(shù) ： 1位 1位 階 碼 q位 尾 數(shù) p位 浮 點 數(shù) 字 段 ： mf ef eq-1 e0 . . m1 mp 對 應(yīng) 位 的 權(quán) ： req-1 re0 rm-1 rm-p 隱 含 小 數(shù) 點 圖2.2 浮點數(shù)的機內(nèi)格式 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 22 2.1.1.3 浮 點 數(shù) 的 性 能 （ P38） 浮 點 數(shù) 的 性 能 主 要 用 表 數(shù) 范 圍 、 表 數(shù) 精 度 和 表 數(shù) 效 率 來 刻 畫 ， 下 面 分 別 進 行 分析 。 (1) 表 數(shù) 范 圍 （ P39） 表 數(shù) 范 圍 由 這 樣 一 些 參 數(shù) 構(gòu) 成 ： 最 小 負 數(shù) 、 最 大 負 數(shù) 、 最 小 正 數(shù) 、 最 大 正 數(shù) 、最 小 絕 對 值 |N|min、 最 大 絕 對 值 |N|max。 它 們 幾 何 意 義 可 以 在 數(shù) 軸 上 表 示 ， 如 下 圖 。 - 最 小 負 數(shù) 最 大 負 數(shù) 0 最 小 正 數(shù) 最 大 正 數(shù) + 圖2.3 數(shù)軸上的表數(shù)范圍示意圖 圖 中 陰 影 部 分 為 浮 點 數(shù) 的 表 數(shù) 范 圍 。 根 據(jù) 浮 點 數(shù) 的 組 成 表 達 式 可 知 ， 圖 2.3中 4個 邊 界 值 分 別 由 尾 數(shù) m、 階 碼 e各 自 的邊 界 值 兩 兩 組 合 而 成 ， 如 下 所 示 。 最 大 正 數(shù) 最 大 正 尾 數(shù) /最 大 階 碼 ； 最 小 正 數(shù) 最 小 正 尾 數(shù) /最 小 階 碼 ； 最 大 負 數(shù) 最 大 負 尾 數(shù) /最 小 階 碼 ； 最 小 負 數(shù) 最 小 負 尾 數(shù) /最 大 階 碼 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 23 對 規(guī) 格 化 浮 點 數(shù) ， 尾 數(shù) 為 原 碼 ， 階 碼 為 移 碼 ， 寫 出 表 數(shù) 范 圍 。 （ P40）解 ： 由 于 原 碼 在 數(shù) 軸 的 零 點 兩 邊 對 稱 分 布 ， 即 最 大 正 數(shù) 與 最 小 負 數(shù) 的 絕 對 值相 等 、 最 小 正 數(shù) 與 最 大 負 數(shù) 的 絕 對 值 相 等 ， 所 以 可 以 用 最 小 、 最 大 絕 對 值 來描 述 它 的 分 布 。首 先 根 據(jù) 圖 2.2和 式 2.1以 及 移 碼 的 基 本 定 義 ， 可 以 確 定 絕 對 值 的 極 值 表 達 式： 例 2.1 11 )1( qeqe rmpmrmm rrNrr qer 。，又 ；， drmpmqepm dmmm qerrNdrerm rrNderm 12maxmaxmax 1minmin1min )1(12)1(寫 在 一 起 就 是 ： drmpmdmm qerrNrr 121 )1(再 用 階 碼 的 偏 移 量 代 換 式 中 的 -d得 ： 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 24 可 以 代 入 具 體 數(shù) 字 來 幫 助 理 解 ： ， 如 下 圖 所 示 。， ， 于 是 有 ：按 此 題 約 定 ， 。，設(shè) 3101min3min1min 3 1010 1010 10 310410 Ndem d qrpr em ， 如 下 圖 所 示 。 ， 1104max 3333max4max 310)101( 1101011021102)101( N dem 1位 1位 階 碼 3位 尾 數(shù) 4位 x 0 0 0 0 . . 1 0 0 0 1位 1位 階 碼 3位 尾 數(shù) 4位 x 1 9 9 9 . . 9 9 9 9 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 25 顯 然 它 隨 著 階 碼 ek增 大 而 迅 速 增 大 ， 即 在 不 同 區(qū) 間 里 會 有 不 同 的 值 。 表 數(shù) 精 度 用 最 大 表 數(shù) 誤 差 表 示 （ 指 相 對 誤 差） 。 而 計 算 相 對 誤 差 之 前 先 要 計 算 絕 對 誤 差 。 最 大 絕 對 誤 差 是 真 實 值 與 可 表 示 值 之 間 的 可能 最 大 距 離 ， 按 “ 舍 入 法 ” 它 等 于 相 鄰 兩 個 可 表示 值 間 距 的 1/2， 如 圖 2.4所 示 。 根 據(jù) 浮 點 數(shù) 的 組成 式 ， 可 以 寫 出 任 一 對 鄰 點 Nk與 Nk+1之 間 的 區(qū) 間內(nèi) 最 大 絕 對 誤 差 為 （ 為 了 簡 便 ， 可 先 假 設(shè) Nk與 Nk+1的 階 碼 相 同 來 推 導(dǎo) ， 其 實階 碼 不 同 的 結(jié) 果 也 一 樣 ）(2) 表 數(shù) 精 度 （ P42） 數(shù) 軸 N k 真 實 值 x N k+1 圖 2.4 區(qū) 間 最 大 絕 對 誤 差 示 意 圖 kmax kk empmemkkkkk rrrmmNN 21)(21)(21 11max 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 26 最 大 相 對 誤 差 與 階 碼 e無 關(guān) ， 但 與 尾 數(shù) m的 值 有 關(guān) 。 按 相 對 誤 差 基 本 定 義 ， 上 述 區(qū) 間 內(nèi) 的 最 大 相 對 誤 差 為 )1(maxmax 21| 1 pmrmk rmk 同 樣 也 不 是 常 數(shù) ， 各 區(qū) 間 內(nèi) 并 不 一 致 ， 只 是 它 受 的 是 尾 數(shù) 的 影 響。 為 了 找 到 所 有 區(qū) 間 中 最 大 的 （ 即 全 局 最 大 相 對 誤 差 ） ， 我 們 應(yīng) 取分 母 的 最 小 值 。 從 上 文 已 知 尾 數(shù) 取 值 范 圍 ， 這 樣 就 能 得到 kmax kmkmax maxkm 01 mkm rmr pmkemk empmk kk rmrm rrN k k 12121maxmax 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 27 (3) 表 數(shù) 效 率 （ P45）定 義 ： mmmqepm qepmmm rrrrr rrrr 11122 12)1(2)( 1 可 以 生 成 的 浮 點 數(shù) 個 數(shù)其 中 規(guī) 格 化 浮 點 數(shù) 個 數(shù) 此 式 說 明 效 率 之 所 以 低 于 100%， 是 因 為 規(guī) 格 化 的 尾 數(shù) 最 高 位 m1只 能有 rm-1種 取 值 的 緣 故 。 可 以 看 出 ， 的 極 小 值 與 極 大 值 分 別 是%100)(lim%50112)2( mr rm ， 隱 藏 位 技 術(shù) 是 一 種 提 高 表 數(shù) 效 率 的 方 法 ， 但 僅 適 用 于 rm=2的 情 況 ：尾 數(shù) 最 高 位 m1 在 二 進 制 條 件 下 只 有 0和 1兩 種 可 能 ， 按 照 規(guī) 格 化 要 求 ， m1 可 由 其 它 位 推 出 ， 。 “ 隱 藏 ” 了 m1之 后 ， 尾 數(shù) 只 存 儲 后 面 p-1位 ，它 們 中 的 任 一 位 都 有 rm種 取 值 ， 所 以 表 數(shù) 效 率 =100%。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 28 2.3 指 令 格 式 的 優(yōu) 化 （ P90）2.3.2 操 作 碼 優(yōu) 化 目 前 常 用 的 編 碼 方 法 有 3種 ： 定 長 編 碼 ， Huffman編 碼 ， 擴 展 編 碼 。2.3.2.1 定 長 編 碼 就 是 所 有 指 令 使 用 相 同 的 代 碼 位 數(shù) ， 其 最 小 碼 長 等 于 nLoglL i 2式 中 是 平 均 碼 長 ， 是 第 i種 指 令 的 碼 長 ， n是 指 令 總 數(shù) 。 例 2.2 已 知 n = 15， 求 定 長 編 碼 的 最 小 平 均 碼 長 。解 ： L il 415 2 LogL 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 29 2.3.2.2 Huffman壓 縮 編 碼 （ P91）(1) Huffman壓 縮 概 念 （ 最 佳 編 碼 定 理 ） ： 當(dāng) 用 n個 長 度 不 等 的 代 碼 分 別 代 表 n種 發(fā) 生 概 率 不 等 的 事 件 時 ， 按 照 短 代 碼 給 高 概 率 事 件 、 把 長 代 碼 給 低 概 率事 件 的 原 則 分 配 ， 可 使 平 均 碼 長 達 到 最 低 。(2) Huffman編 碼 方 法 這 種 編 碼 方 法 由 兩 個 過 程 組 成 。頻 度 合 并 ： 將 全 部 n個 事 件 （ 在 此 即 為 n條 指 令 ） 的 頻 度 值 排 序 ， 選 取其 中 最 小 的 2個 頻 度 合 并 ， 然 后 將 剩 下 的 n-1個 頻 度 再 次 排 序 ， 再 合 并 最 小的 2個 頻 度 ， 如 此 重 復(fù) ， 直 至 剩 下 1個 頻 度 為 止 。 記 錄 所 有 的 合 并 關(guān) 系 ， 形成 一 棵 二 叉 樹 Huffman樹 ， 所 有 原 始 頻 度 值 充 當(dāng) 樹 葉 ， 而 最 后 剩 下的 總 頻 度 1為 樹 根 ；碼 元 分 配 ： 從 樹 根 開 始 ， 對 每 個 中 間 結(jié) 點 的 左 右 2個 分 支 邊 各 賦 予 一 位 代 碼 “ 0” 和 “ 1” （ “ 0” 在 哪 一 側(cè) 不 限 ） 。 讀 出 從 根 結(jié) 點 到 任 一 片 樹葉 的 路 徑 上 依 次 出 現(xiàn) 的 代 碼 位 就 排 成 了 這 個 事 件 （ 即 指 令 ） 的 完 整 編 碼 。由 于 頻 度 高 的 事 件 較 晚 被 合 并 ， 它 的 編 碼 位 數(shù) 也 就 較 少 ， 符 合 Huffman壓縮 原 則 。 上 面 所 說 的 頻 度 值 就 是 各 事 件 實 際 出 現(xiàn) 次 數(shù) 的 百 分 比 ， 它 是 理 論 出 現(xiàn) 概率 的 近 似 值 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 30 2.3.2.3 擴 展 編 碼 方 法 （ 等 長 擴 展 法 ， P93） 用 碼 長 表 示 ： 例 如 4-8-12法 。 這 并 不 能 說 明 具 體 編 碼 方 法 ， 例 如下 面 兩 種 編 碼 方 法 都 是 4-8-12法 。 用 碼 點 數(shù) 表 示 ： 例 如 15/15/15法 ， 8/64/512法 15/15/15法 ， 每 一 種 碼 長 都 有 4位 可 編 碼 位 （ 前 頭 可 以 有 相 同的 擴 展 標(biāo) 識 前 綴 ） ， 可 產(chǎn) 生 16個 碼 點 （ 即 編 碼 組 合 ） ， 但 是至 多 只 能 使 用 其 中 15個 來 表 示 事 件 ， 留 下 1個 或 多 個 碼 點 組 合作 為 更 長 代 碼 的 擴 展 標(biāo) 識 前 綴 。 已 經(jīng) 用 來 表 示 事 件 的 碼 點 組合 不 能 再 作 為 其 它 更 長 代 碼 的 前 導(dǎo) 部 分 ， 否 則 接 收 者 會 混 淆 。這 就 是 “ 非 前 綴 原 則 ” 。 8/64/512法 ， 每 一 種 碼 長 按 4位 分 段 ， 每 一 段 中 至 少 要 留 下 1位 或 多 位 作 為 擴 展 標(biāo) 識 。 各 段 剩 下 的 可 編 碼 位 一 起 編 碼 ， 所 產(chǎn) 生 的 碼 點 用 來 對 應(yīng) 被 編 碼 事 件 。 每 一 段 中 的 標(biāo) 識 位 指 出 后面 還 有 沒 有 后 續(xù) 段 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 31 以 3-6-9位 為 例 36bit目 標(biāo) ： 平 均 碼 長 最 小 化 33bit平 均 碼 長 =P1l1+ P2l2+ P84l84 30bit 27bit 24bit 21bit 18bit 15bit 12bit 9bit 6bit 3bit7/7/7法 碼 長 分 布 7條 7條 7條 7條 7條 7條 7條 7條 7條 7條 7條 7條 9bit 6bit 3bit4/16/64法 碼 長 分 布 4條 16條 64條指 令 頻 度 分 布 懸 殊 P1 P84指 令 頻 度 分 布 均 勻 P 1 P84 兩 種 等 長 擴 展 碼 適 用 性 比 較 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 32 2.3.2.4 編 碼 方 法 性 能 指 標(biāo) （ P91-P93） 信 息 量 ： 根 據(jù) 信 息 論 的 基 本 知 識 ， 在 n種 可 能 發(fā) 生 的 事 件 集 合 中 ， 報 告 第 i種 事 件 發(fā) 生 的 消 息 中 包 含 的 信 息 量 為 iaiai PPI log)1(log 其 中 Pi是 第 i種 事 件 發(fā) 生 的 先 驗 概 率 ， a是 編 碼 基 值 。 信 息 量 的 單 位 是 表 示位 數(shù) （ 最 少 所 需 位 數(shù) ） 。 這 個 定 義 式 表 明 事 件 的 發(fā) 生 概 率 越 低 ， 關(guān) 于 它 的 消 息 中 的 信 息 量 越 大。 熵 （ entropy） 平 均 信 息 量 ： 一 個 消 息 源 對 n種 事 件 發(fā) 布 的 消 息 的 信 息量 平 均 值 ， 記 為 ni iaini ii PPIPH 11 )(log)( 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 33 平 均 碼 長 ： 各 事 件 編 碼 長 度 的 數(shù) 學(xué) 期 望 。 ni ii lPL 1 )( 信 息 冗 余 量 ： 它 表 明 消 息 編 碼 中 “ 無 用 成 分 ” 所 占 的 百 分 比 。%100 LHLR 從 減 少 存 儲 與 傳 輸 量 的 角 度 看 ， 編 碼 方 法 的 平 均 碼 長 越 短 越 好 。 但 是 平均 碼 長 不 可 能 無 限 制 縮 短 ， 它 的 下 限 就 是 熵 （ 即 R=0時 ） 。 如 果 短 于 熵 就 一定 會 丟 失 有 用 信 息 （ 即 混 淆 不 同 指 令 ） ， 這 是 不 允 許 的 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 34 例 2.3 1.0 0 1 0.4 0.6 0 1 0 1 0.2 0.3 0 1 0 1 0.1 0.1 0.15 0.15 0.2 0.3 圖 2.5 Huffman 樹 已 知 頻 度 序 列 為 0.1， 0.1， 0.15， 0.15， 0.2， 0.3， 求 Huffman編 碼 、 等長 擴 展 3/3/3碼 、 定 長 編 碼 、 三 者 的 平 均 碼 長 、 信 息 冗 余 量 以 及 熵 。解 ： 熵 H = (2 0.1 log20.1+2 0.15 log20.15+0.2 log20.2+0.3 log20.3)2.47 根 據(jù) Huffman編 碼 方 法 作 Huffman樹 如 圖 2.5所 示 ， 三 種 編 碼 方 法 的 結(jié) 果 列于 表 2.1中 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 35 表 2.1 Huffman編 碼 、 等 長 擴 展 3/3/3碼 及 定 長 編 碼 指 令 I1 I2 I3 I4 I5 I6 頻 度 0.1 0.1 0.15 0.15 0.2 0.3 000 001 100 101 01 11Huffman碼 平 均 碼 長 L=2.5， 信 息 冗 余 量 R 1.2% 1110 1101 1100 10 01 003/3/3碼 平 均 碼 長 L=2.7， 信 息 冗 余 量 R 7.5% 000 001 010 011 100 101定 長 編 碼 平 均 碼 長 L=3.0， 信 息 冗 余 量 R 17.7% 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 36 2.3.3 操 作 數(shù) 優(yōu) 化 尋 址 方 式 比 較 （ P95） 指 令 中 操 作 數(shù) 占 用 的 位 數(shù) 由 操 作 數(shù) 的 個 數(shù) 與 尋 址 方 式 決 定 。 按 操 作 數(shù) 的 個 數(shù) 劃 分 ， 有 零 操 作 數(shù) 指 令 、 一 操 作 數(shù) 指 令 、 二 操 作數(shù) 指 令 、 三 操 作 數(shù) 指 令 共 四 種 形 式 。 應(yīng) 該 按 機 器 用 途 來 選 擇 （ P99，表 2.20） 。 縮 短 操 作 數(shù) 長 度 的 常 用 方 法 是 間 址 和 變 址 （ P99頁 末 ） 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 37 本 章 主 要 內(nèi) 容 有 數(shù) 據(jù) 表 示 和 操 作 碼 優(yōu) 化 兩 個 部 分 。 具 體 細 節(jié) 如 下 ：(1) 浮 點 數(shù) 的 表 數(shù) 范 圍 （ 在 數(shù) 軸 上 的 4個 端 點 ） 、 表 數(shù) 精 度 、 表 數(shù) 效 率 ；(2) Huffman編 碼 方 法 ；(3) 等 長 擴 展 編 碼 方 法 （ 15/15/15法 ， 8/64/512法 ） ；(4) 編 碼 方 法 性 能 指 標(biāo) （ 熵 H， 平 均 碼 長 L， 信 息 冗 余 量 R） 。習(xí) 題 ： P124， 題 3（ 忽 略 P124倒 1行 P125第 8行 文 字 ） ， 題 13。本 章 小 結(jié) 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 38 第 三 章 存 儲 系 統(tǒng) （ P130）Memory Hirarchy 長 期 存 在 的 問 題 ： 在 合 理 的 總 價 格 限 制 下 ， 單 純 性 主 存 設(shè) 備 的 速度 跟 不 上 CPU的 發(fā) 展 ， 容 量 不 能 滿 足 軟 件 尺 寸 擴 大 。 本 章 學(xué) 習(xí) 兩 種 提 高 主 存 系 統(tǒng) 性 能 /價 格 比 的 結(jié) 構(gòu) 化 方 法 ： 并 行 存 儲器 與 存 儲 層 次 技 術(shù) 。 后 者 為 主 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 39 3.1 并 行 存 儲 器 （ P136） 并 行 存 儲 器 技 術(shù) 可 以 提 高 主 存 系 統(tǒng) 的 整 體 等 效 速 度 ， 實 際 應(yīng) 用 中 ，常 將 它 與 存 儲 層 次 技 術(shù) 組 合 使 用 ， 可 以 互 為 補 充 ， 獲 得 很 高 的 性 能 。 并 行 存 儲 器 技 術(shù) 的 基 本 思 想 是 用 多 個 獨 立 的 存 儲 部 件 組 成 主 存 系統(tǒng) ， 讓 它 們 并 行 工 作 ， 在 一 個 存 儲 周 期 內(nèi) 可 以 訪 問 到 多 個 數(shù) 據(jù) ， 從而 實 現(xiàn) 較 高 的 存 取 流 量 。 并 行 存 儲 器 包 括 多 種 類 型 ， 我 們 僅 介 紹 提 高 訪 問 速 度 效 果 最 顯 著的 低 位 交 叉 訪 問 這 一 種 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 40 低 位 交 叉 訪 問 并 行 存 儲 器 的 結(jié) 構(gòu) ： 它 由 n個 存 儲 體 組 成 （ 一 般 n為 2的 整 次 冪 ） ， 每 個 體 均 有 獨 立 的 地 址 譯碼 器 和 數(shù) 據(jù) 緩 沖 器 ， 以 主 存 地 址 低 位 字 段 （ 最 低 的 log2n位 ） 作 為 體 選 譯碼 信 號 ， 而 剩 下 的 高 位 字 段 則 是 體 內(nèi) 地 址 。 如 圖 所 示 （ 設(shè) n = 4） 。 地 址 總 線 體 0 體 1 體 2 體 3 地 址 譯 碼 器 地 址 譯 碼 器 地 址 譯 碼 器 地 址 譯 碼 器 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 數(shù) 據(jù) 緩 沖 器 數(shù) 據(jù) 緩 沖 器 數(shù) 據(jù) 緩 沖 器 數(shù) 據(jù) 緩 沖 器 數(shù) 據(jù) 總 線 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 41 主 存 地 址 與 結(jié) 構(gòu) 參 數(shù) 的 換 算 （ P139） ： nAknAj kjnA mod ，求 結(jié) 構(gòu) 參 數(shù) ：求 主 存 地 址 ：其 中 ： n 存 儲 體 個 數(shù) ， A 主 存 地 址 ， j 體 內(nèi) 地 址 ， k 體 序 號 （ k = 0， 1， 2， ， n-1 ） 例 3.1 已 知 n = 4， 問 主 存 地 址 13是 在 幾 號 體 的 幾 號 單 元 ？解 ： 由 于 n = 4， 體 選 譯 碼 信 號 使 用 主 存 地 址 的 最 低 log 2n = 2位 ， 所 以 地址 13（ 其 二 進 制 為 1101B） 對 應(yīng) 的 體 號 k = 1（ 即 01B） 、 體 內(nèi) 地 址 j = 3（即 11B） ， 也 就 是 說 ， 地 址 13位 于 1號 體 的 3號 單 元 （ 參 看 前 一 頁 插 圖 ） 。根 據(jù) 上 式 ， 所 有 k值 （ 即 體 號 ） 相 同 的 地 址 之 間 均 相 差 n的 整 倍 數(shù)， 稱 之 為 “ 模 n同 余 ” 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 42 低 位 交 叉 訪 問 并 行 存 儲 器 的 加 速 機 理 ： 我 們 衡 量 存 儲 器 件 速 度 的 常 用 指 標(biāo) 是 存 儲 周 期 Tm， 它 是 同 一 存 儲 單 元 連 續(xù)兩 次 啟 動 的 最 小 時 間 間 隔 ， 數(shù) 值 越 小 表 明 存 儲 器 件 速 度 越 快 。 傳 統(tǒng) 存 儲 系 統(tǒng) 只 有 一 套 地 址 譯 碼 器 和 數(shù) 據(jù) 緩 沖 器 ， 所 以 各 單 元 必 須 串 行 工作 ， 也 就 是 說 每 個 Tm周 期 內(nèi) 至 多 只 能 完 成 一 次 訪 問 。 由 多 個 存 儲 體 構(gòu) 成 的 并 行 存 儲 器 中 ， 各 個 存 儲 體 都 有 獨 立 的 地 址 譯 碼 器 和數(shù) 據(jù) 緩 沖 器 ， 它 們 可 以 并 行 工 作 ， 使 得 一 個 Tm周 期 內(nèi) 可 完 成 多 次 訪 問 ， 相 當(dāng) 于加 速 了 多 倍 。 最 好 情 況 下 一 個 Tm周 期 內(nèi) 可 完 成 n次 訪 問 。 當(dāng) 前 Tm周 期 中 只 要 發(fā) 現(xiàn) 有 一 個 新 的 訪 問 地 址 與 前 面 地 址 屬 于 同 一 個 存 儲 體， 該 地 址 及 其 后 面 的 地 址 就 會 被 阻 塞 （ 稱 為 訪 存 沖 突 ） ,留 到 下 一 個 Tm周 期 訪問 。 機 器 地 址 序 列 常 常 具 有 順 序 性 ， 按 照 低 位 交 叉 的 規(guī) 律 分 配 地 址 可 使 相 繼 出現(xiàn) 的 地 址 落 在 相 同 存 儲 體 的 概 率 降 到 最 低 （ 參 見 上 圖 ） 。 考 慮 到 地 址 總 線 與 數(shù) 據(jù) 總 線 的 擁 擠 問 題 ， 一 個 Tm周 期 里 發(fā) 送 的 多 個 訪 問 請求 最 好 彼 此 錯 開 Tm/n時 間 ， 如 P140圖 3.11所 示 ， 否 則 實 現(xiàn) 的 復(fù) 雜 度 會 增 加 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 43 K g=010.0 g=0.24.463.68 2.00 g=0.51.00 g=1 0 1 10 n 計 算 平 均 加 速 倍 數(shù) （ P141） ：1.只 考 慮 取 指 地 址 序 列 （ 假 設(shè) 地 址 順 序遞 增 ， 直 至 出 現(xiàn) 一 條 轉(zhuǎn) 移 指 令 ） ：倒 數(shù) 第 一 行 ）（ 141 )1(1 Pg gK n 其 中 g是 指 令 序 列 中 出 現(xiàn) 轉(zhuǎn) 移 指 令 的 概率 。 此 公 式 在 右 圖 中 用 綠 線 表 示 。2.只 考 慮 取 數(shù) 地 址 序 列 （ 假 設(shè) 地 址 完 全隨 機 ） 28.02/ nK 此 公 式 在 右 圖 中 用 紅 線 表 示 。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 44 例 題 ： P203， 題 5 。也 對 （ 文 字 理 解 差 異 ）取。向 下 取 整 ， 得 解 出，得 依 題 意 有，其 中，解 ： 已 知 161 15 28.159.0lg 2.0lg 2.09.0 2.0)1(12.0)1(1 1.0 )1(1 11 nn g gKggK gg gK n nnnn nn 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 45 3.2 存 儲 層 次 原 理 及 性 能 指 標(biāo) 3.2.1 基 本 原 理 定 義 ： （ 參 見 P131第 二 段 ） 由 2種 或 多 種 存 儲 部 件 構(gòu) 成 的 復(fù) 合 存 儲 系 統(tǒng) ， 通過 內(nèi) 部 管 理 機 構(gòu) 的 自 動 更 換 機 制 ， 能 夠 不 斷 將 大 容量 低 速 存 儲 部 件 中 的 活 躍 內(nèi) 容 復(fù) 制 到 小 容 量 高 速 存儲 部 件 中 （ 后 者 作 為 前 者 的 局 部 副 本 ） 。 它 既 能 滿 足 CPU的 快 速 存 取 需 要 ， 又 有 很 大 的 存儲 容 量 ， 平 均 單 位 價 格 也 很 低 ， 等 效 于 同 時 滿 足 3方 面 要 求 的 理 想 單 一 存 儲 部 件 。 依 據(jù) ： 程 序 訪 問 的 局 部 化 原 理 （ 時 間 局 部 化 ， 空間 局 部 化 ） 。 模 型 ： 如 右 圖 所 示 ， 存 儲 層 次 由 n層 組 成 ， 滿 足 3個 不 等 式 ： Tici+1， Si 1， 表 示 塊 內(nèi) 至 少 還 有 一 個 數(shù) 據(jù) 要 被 訪 問 ， 在 訪 問 第 一 個 數(shù)據(jù) 時 將 它 提 前 調(diào) 入 ， 會 使 它 的 第 一 次 訪 問 由 不 命 中 變 成 命 中 ， 所 以 H H。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 52 教 材 P134的 3.1.1節(jié) 末 尾 有 一 個 例 子 ， 已 知 塊 的 大 小 為 4個 字 ， 每 個 數(shù) 據(jù) 使用 次 數(shù) 為 5。 先 直 接 計 算 命 中 率 ， 不 預(yù) 取 時 每 個 數(shù) 據(jù) 的 頭 1次 訪 問 不 命 中 ， 后 4次 訪 問 都命 中 ， 所 以 命 中 率 ， 而 預(yù) 取 時 只 有 第 一 個 數(shù) 據(jù) 的 第 1次訪 問 不 命 中 ， 后 面 19次 訪 問 都 命 中 ， 所 以 命 中 率 。 再 通 過 公 式 計 算 命 中 率 ， 教 材 上 取 n = 20， 算 出 ，而 。 這 顯 然 是 不 正 確 的 。 如 果 取 n = 4， 同 樣 算 出 H = 0.8， 而 。 與 直 接 計 算 結(jié) 果 相 符 ， 才 是 正 確 的 。 例 題 分 析 8.054 44 H 95.054 154 H 8.054 44 H 99.020 1208.01 nnHH 95.04 148.01 nnHH 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 53 加 速 比 （ P193） Cache-主 存 層 次 的 主 要 作 用 是 提 高 訪 問 速 度 ， 系 統(tǒng) 的 等 效 速 度 應(yīng)高 于 主 存 （ 即 M2） 的 原 有 速 度 ， 兩 個 速 度 之 比 稱 為 加 速 比 。 rHH THTH T TTMMSp /)1( 1 )1( 21 2 222 等 效 時 間時 間速 度等 效 速 度 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 54 M1 103B T1=1us 103B M2 106B TB2=10usM3 109B TB3=100us 109B (a) (b) 例 3.2 有 一 個 109字 節(jié) 的 程 序 被 裝入 右 圖 所 示 的 M3準(zhǔn) 備 運 行 。假 定 指 令 字 長 =1字 節(jié) ， 程 序中 無 轉(zhuǎn) 移 指 令 和 內(nèi) 存 讀 /寫 指令 。 (1)按 圖 (a)求 T和 e； 增 加 中 間 層 對 e的 影 響(2)按 圖 (b)推 導(dǎo) 三 層 體 系 的 T公 式 ；(3)按 圖 (b)求 T和 e；(4)比 較 (1)(3)結(jié) 果 ， 有 何 結(jié) 論 ？ 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 55 解 ： 32122111 3222111 32222 2111 1 13 23333 3111 31331 )1()1()1( )1()1( 2 )1( )1( )2( %91 %)101(10 11010100101110 110 )1( 1011 10 110 )1( BB BBBB B THHTHHTH THTHHTHT THTHT THTHT TTe Tsss THTHT HH 式 有由 上 面 ， 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 56效 率 提 高 。層 間 速 度 差 減 少 ， 訪 問結(jié) 論 ： 插 入 中 間 層 后 ， )4( %99 %)11(10 1010101010 1001011010 110101110 110 1011 ,10 110 )3( 1 16 2346 333333 32332 TTe Ts sssT HH 習(xí) 題 ： P202， 題 3。 2006.3.20 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 57 存 儲 層 次 的 管 理 方 式 (P148) 根 據(jù) 程 序 的 局 部 化 性 質(zhì) ， 存 儲 層 次 機 構(gòu) 對 用 戶 文 件 的 管 理 應(yīng) 該 劃 分 成