《計算機系統(tǒng)結(jié)構(gòu)》習(xí)題課及答案全套

《《計算機系統(tǒng)結(jié)構(gòu)》習(xí)題課及答案全套》由會員分享，可在線閱讀，更多相關(guān)《《計算機系統(tǒng)結(jié)構(gòu)》習(xí)題課及答案全套（126頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 習(xí) 題 課 目 錄 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念 2 指 令 系 統(tǒng) 3 存 儲 系 統(tǒng) 返 回 總 目 錄 4 輸 入 輸 出 系 統(tǒng) 5 標(biāo) 量 處 理 機 7 互 連 網(wǎng) 絡(luò) 基 本 要 求 ： ） 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念 ， 定 量 原 理 ， 指令 的 格 式 設(shè) 計 ， CISC與 RISC， 虛 擬 存 儲 頁 面 替 換算 法 ， Cache映 象 ， 通 道 流 量 分 析 ， 數(shù) 據(jù) 相 關(guān) ，線 性 與 非 線 性 流 水 線 技 術(shù) 及 性 能 分 析 ， 互 連 網(wǎng) 絡(luò)基 本 概 念 ；學(xué) 習(xí) 重 點 ： ） 定 量 原

2、 理 ， 指 令 格 式 設(shè) 計 ， RISC， 頁 面 替 換算 法 ， Cache映 象 ， 流 水 線 性 能 分 析 ； 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.1 名 詞 解 釋 返 回 目 錄 1. 計 算 機 體 系 結(jié) 構(gòu) 的 定 義 ： 程 序 員 所 看 到 的 計 算 機的 屬 性 ， 即 概 念 性 結(jié) 構(gòu) 與 功 能 特 性 。 Amdahl提 出 的 體 系 結(jié) 構(gòu) ： 是 指 傳 統(tǒng) 機 器 級 的 體 系結(jié) 構(gòu) 。 即 一 般 所 說 的 機 器 語 言 程 序 員 所 看 到 的 傳 統(tǒng) 機器 級 所 具 有 的 屬 性 。 2. 透 明 性 在

3、 計 算 機 技 術(shù) 中 ， 對 這 種 本 來 是 存 在 的 事 物 或 屬 性 ， 但 從 某 種 角 度 看 又 好 象 不 存 在 。 3. 大 概 率 事 件 優(yōu) 先 原 則 ： 即 對 于 大 概 率 事 件 （ 最 常 見 事件 ） ， 賦 予 它 優(yōu) 先 的 處 理 權(quán) 和 資 源 使 用 權(quán) ， 以 獲 得 全 局 的最 優(yōu) 結(jié) 果 。4. Amdahl定 律 ： 加 快 某 部 件 執(zhí) 行 速 度 所 獲 得 的 系 統(tǒng) 性 能 加速 比 ， 受 限 于 該 部 件 在 系 統(tǒng) 中 所 占 的 重 要 性 。5. 程 序 的 局 部 性 原 理 ： 程 序 在 執(zhí) 行 時

4、 所 訪 問 地 址 的 分 布 不是 隨 機 的 ， 而 是 相 對 地 簇 聚 ； 這 種 簇 聚 包 括 指 令 和 數(shù) 據(jù) 兩部 分 。 程 序 局 部 性 包 括 程 序 的 時 間 局 部 性 和 空 間 局 部 性 。 時 間 局 部 性 ： 程 序 即 將 用 到 的 信 息 很 可 能 就 是 目 前 正 在使 用 的 信 息 空 間 局 部 性 ： 程 序 即 將 用 到 的 信 息 很 可 能 與 目 前 正 在 使用 的 信 息 相 鄰 或 臨 近 。 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.1 名 詞 解 釋 6. 系 統(tǒng) 加 速 比 ： 系 統(tǒng) 改 進

5、 前 與 改 進 后 總 執(zhí) 行 時 間 之 比7. CPI： 指 令 周 期 數(shù) （ Cycles of Instruction)8. 并 行 性 ： 在 同 一 時 刻 或 同 一 時 間 間 隔 內(nèi) 完 成 兩 種 或 兩 種以 上 的 性 質(zhì) 相 同 或 不 同 的 工 作 。9. 翻 譯 ： 先 把 N 1級 程 序 全 部 變 換 成 N級 程 序 之 后 ， 再 去執(zhí) 行 N級 程 序 ， 在 執(zhí) 行 過 程 中 ， N 1級 程 序 不 再 被 訪 問（ 基 于 層 次 結(jié) 構(gòu) ）10. 解 釋 ： 每 當(dāng) 一 條 N 1級 指 令 被 譯 碼 后 ， 就 直 接 去 執(zhí) 行

6、一串 等 效 的 N級 指 令 ， 然 后 再 去 取 下 一 條 N 1級 指 令 ， 依此 重 復(fù) 進 行 。1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.1 名 詞 解 釋 例 ：設(shè) 某 程 序 中 FP操 作 占 20%， 其 平 均 CPI=4.0, FPSQR操 作 的 比 例 占 4%， 其 平 均 CPI=20.0, 其 它 指 令 平 均 CPI=1.20， 現(xiàn) 采 用 兩 種 方 法 進 行 優(yōu) 化 : a. 將 FP操 作 的 CPI減 為 2;b. 將 FPSQR操 作 的 CPI減 少 為 12;問 1： 哪 一 種 方 法 更 優(yōu) ?問 2： 若 同 時 采

7、 用 a、 b方 法 ， 系 統(tǒng) 的 加 速 比 為 多 少 ？1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.2 問 1解 ： 比 較 2方 案 的 CPI即 可 CPIa =（ 1-20%-4%） CPI其 他 +（ 20% CPIFP ） +（ 4% CPIFPSQR） = 76% 1.20 + 20% 2+ 4% 20 =2.11 CPIb =（ 1-20%-4%） CPI其 他 +（ 20% CPIFP ） +（ 4% CPIFPSQR） = 76% 1.20 + 20% 4 +4% 12 =2.3 所 以 ， 采 用 方 法 a更 優(yōu) 。1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基

8、 本 概 念1.2 問 2解 ： 加 速 比 ： 4.112%42%2020.1%76 20%44%2020.1%76 %4%20%)4%201( %4%20%)4%201( )( )()( )()( )( ICICU RFPQSPF FPQSRFP CPICPICPI CPICPICPI CPICPICPICPICPCPUS 其 它其 它 新原時 鐘 周 期 長新 時 鐘 周 期 長原新時 間 原時 間 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.2 例 ： 假 設(shè) 我 們 考 慮 條 件 分 支 指 令 的 兩 種 不 同 設(shè) 計 方 法 如 下 ： (1) CPUA： 通 過

9、比 較 指 令 設(shè) 置 條 件 碼 ， 然 后 測 試 條 件 碼 進 行 分 支(2) CPUB： 在 分 支 指 令 中 包 括 比 較 過 程 在 兩 種 CPU中 ， 條 件 分 支 指 令 都 占 用 2個 時 鐘 周 期 而 所 有 其 它 指 令占 用 1個 時 鐘 周 期 ， 對 于 CPUA， 執(zhí) 行 的 指 令 中 分 支 指 令 占 20%； 由 于每 個 分 支 指 令 之 前 都 需 要 有 比 較 指 令 ， 因 此 比 較 指 令 也 占 20%。 由于 CPUB在 分 支 時 需 要 比 較 ， 因 此 假 設(shè) 它 的 時 鐘 周 期 時 間 是 CPUA的1.

10、25倍 。問 1： 哪 一 個 CPU更 快 ？1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.3 我 們 不 考 慮 所 有 系 統(tǒng) 問 題 ， 所 以 可 用 CPU性 能 公 式 。 占 用 2個 時 鐘 周 期 的 分 支 指 令 占 總 指 令 的 20%， 剩 下 的 指 令 占 用 1個 時 鐘 周 期 。 所 以 CPIA = 20% 2 + 80% 1 = 1.2則 CPU性 能 為 ： 總 CPU時 間 A = ICA 1.2 時 鐘 周 期 A解 1： 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.3 根 據(jù) 假 設(shè) ， 有 ： 時 鐘 周 期 B = 1.

11、25 時 鐘 周 期 A在 CPUB中 沒 有 獨 立 的 比 較 指 令 ， 所 以 CPUB的 程 序 量 為CPUA的 80%， 分 支 指 令 的 比 例 為 ： 20%/80% = 25%這 些 分 支 指 令 占 用 2個 時 鐘 周 期 ， 而 剩 下 的 75%的 指 令占 用 1個 時 鐘 周 期 ， 因 此 ： CPIB = 0.25 2 + 0.75 1 = 1.25因 為 CPU B不 執(zhí) 行 比 較 ， 故 ： ICB = 0.8 ICA 解 1： 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.3 因 此 CPUB性 能 為 ： 總 CPU時 間 B = IC

12、B CPIB 時 鐘 周 期 B = 0.8 ICA 1.25 (1.25 時 鐘 周 期 A) = 1.25 ICA 時 鐘 周 期 A在 這 些 假 設(shè) 之 下 ， 盡 管 CPUB執(zhí) 行 指 令 條 數(shù) 較 少 ， CPUA因 為 有 著 更 短 的 時 鐘 周 期 ， 所 以 比 CPUB快 。解 1： 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.3 例 ： 我 們 分 析 一 個 用 于 Web服 務(wù) 器 系 統(tǒng) 的 處 理 器 的 性 能 。假 定 采 用 某 增 強 方 式 使 新 的 CPU處 理 Web服 務(wù) 器 應(yīng) 用 程 序 的運 行 速 度 是 原 來 處 理

13、 器 中 的 10倍 ， 同 時 假 定 此 CPU有 40%的時 間 用 于 計 算 ， 另 外 60%的 時 間 用 于 I/O操 作 。 那 么 增 強 性能 后 總 的 加 速 比 是 多 少 ？ 解 ： 增 強 比 例 = 0.4 增 強 加 速 比 = 10總 加 速 比 = 10.6 + 0.410 = 0.64 = 1.5611 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.4 例 ： 設(shè) 某 計 算 機 系 統(tǒng) 執(zhí) 行 程 序 中 ， 可 向 量 化 部 分 最 大 可 達 70%。一 種 實 現(xiàn) 方 法 是 采 用 陳 列 多 處 理 機 即 硬 件 方 式 實 現(xiàn) ，

14、 使 60%的向 量 化 指 令 執(zhí) 行 速 度 加 快 到 原 來 的 10倍 ， 另 一 種 方 法 是 采 用 優(yōu)化 編 譯 系 統(tǒng) 的 方 法 實 現(xiàn) ， 使 向 量 化 程 序 可 達 70%， 且 速 度 可 增加 3倍 。 請 比 較 這 兩 種 方 案 哪 種 更 優(yōu) 。 解 ：通 過 計 算 加 速 比 知 ， 硬 件 方 案 較 優(yōu) ！ 53.013/7.0%)701( 1 46.0110/6.0%)601( 1 編 譯硬 件SS 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.5 Assume a simple load/store machine with the

15、 following instruction frequency: Instruction type Frequency CyclesLoads 25% 2Stores 15% 2Branches 20% 2ALU 40% 1conditional branches currently use simple test against 0Should we add complex comparison/branch combination (BEQ Rn,Rm,LOC or BNE Rn,Rm,LOC) -25% of branches can use the complex scheme an

16、d save(節(jié) 省 了 ） the preceding ALU instruction -The CPU cycle time(CCT) of the machine has to be 10% longer -Will this increase CPU performance? 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.6 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.6 使 用 40MHz時 鐘 速 率 的 處 理 機 執(zhí) 行 一 個 測 試 程 序 ，它 的 主 要 指 令 類 型 所 執(zhí) 行 的 指 令 數(shù) 及 所 需 的 時 鐘 周 期數(shù) 如 下 ， 試 計

17、算 執(zhí) 行 此 程 序 的 有 效 CPI， MIPS速 率及 總 的 CPU時 間 。 （ p33習(xí) 題 1.19)指 令 類 型 指 令 數(shù) 時 鐘 周 期 數(shù)整 數(shù) 算 術(shù) 45000 1數(shù) 據(jù) 傳 送 32000 2浮 點 15000 2控 制 轉(zhuǎn) 移 8000 21 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.7 p33習(xí) 題 1.19 總 時 鐘 周 期 數(shù)=45000*1+32000*2+15000*2+8000*2 =155000 總 指 令 數(shù)=45000+32000+15000+8000=100000 CPI=總 時 鐘 周 期 數(shù) /總 指 令 數(shù) =1.55 總

18、CPU執(zhí) 行 時 間 =155000/40* 10-6=0.003875s MIPS=總 指 令 數(shù) *10-6/總 時 間=0.1/0.003875=25.81 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.7 p33習(xí) 題 1.19 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.8 p33習(xí) 題 1.20 某 工 作 站 采 用 時 鐘 頻 率 為 15MHz， 處 理 速 率 為10MIPS的 處 理 機 來 執(zhí) 行 一 個 已 知 混 合 程 序 。 假 定每 次 存 儲 器 存 取 為 1周 期 延 遲 ， 試 問 ： （ 1） 此 計 算 機 的 有 效 CPI是 多

19、少 ？ （ 2） 時 鐘 提 高 到 30MHz， 但 存 儲 器 子 系 統(tǒng) 速 率 不變 。 這 樣 ， 每 次 存 儲 器 存 取 需 要 2個 時 鐘 周 期 。 如果 30%指 令 每 條 只 需 要 1次 存 儲 存 取 ， 而 另 外 5%每 條 需 要 2次 存 儲 存 取 ， 還 假 定 已 知 混 合 程 序 的 指令 數(shù) 不 變 ， 并 與 原 工 作 站 兼 容 ， 試 求 改 進 后 的 處 理機 性 能 。 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.8 p33習(xí) 題 1.20 解 ： （ 1） 設(shè) 該 程 序 執(zhí) 行 時 間 為 t， 則 CPI = 總

20、 時 鐘 周 期 數(shù) /總 指 令 數(shù) = (t*15M)/(t*10M) = 1.5 （ 2） 公 式 ： CPU time=IC*CPI*CCT 即 有 ： CPUtime=指 令 數(shù) 指 令 周 期 數(shù) cpu周 期 時 間 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.8 p33習(xí) 題 1.20 1 計 算 機 系 統(tǒng) 結(jié) 構(gòu) 的 基 本 概 念1.9 p34習(xí) 題 1.21 24.21.0812.0418.026.01 CPI 86.171024.2 104010 666 CPIfMIPS 解 ： 2 指 令 系 統(tǒng)2.1 名 詞 解 釋 1. CISC:復(fù) 雜 指 令 集

21、計 算 機 （ Complex Instruction Set Computer） 。 強 化 指 令 功 能 ， 設(shè) 置 一 些 功 能 復(fù)雜 的 指 令 ， 把 一 些 原 來 由 軟 件 實 現(xiàn) 的 、 常 用 的 功 能改 用 硬 件 的 指 令 系 統(tǒng) 來 實 現(xiàn) ， 基 于 這 種 指 令 集 結(jié) 構(gòu)而 設(shè) 計 實 現(xiàn) 的 計 算 機 系 統(tǒng) 稱 為 CISC計 算 機 。2. RISC:精 簡 指 令 集 計 算 機 （ Reduced Instruction Set Computer） 。 盡 量 簡 化 指 令 功 能 ， 只 保 留 那 些功 能 簡 單 ， 能 在 一 個

22、 周 期 內(nèi) 執(zhí) 行 完 成 的 指 令 ， 較 復(fù)雜 的 功 能 用 一 段 子 程 序 來 實 現(xiàn) ， 這 種 計 算 機 系 統(tǒng) 稱為 RISC計 算 機 。 返 回 目 錄 2 指 令 系 統(tǒng)2.2 簡 答 1. RISC的 關(guān) 鍵 技 術(shù) 有 哪 些 ？ 延 時 轉(zhuǎn) 移 技 術(shù) 指 令 取 消 技 術(shù) 重 疊 寄 存 器 窗 口 技 術(shù) 指 令 流 調(diào) 整 技 術(shù) 硬 件 為 主 ， 固 件 為 輔 2 指 令 系 統(tǒng)2.3 例 : 某 計 算 機 有 10條 指 令 ， 它 們 的 使 用 頻率 分 別 為 0.30, 0.20, 0.16, 0.09, 0.08, 0.07, 0

23、.04, 0.03, 0.02, 0.01(1) 用 霍 夫 曼 編 碼 對 它 們 的 操 作 碼 進 行 編 碼 ， 并計 算 平 均 代 碼 長 度 。(2) 用 擴 展 霍 夫 曼 編 碼 法 對 操 作 碼 進 行 編 碼 ， 限兩 種 操 作 碼 長 度 ， 并 計 算 平 均 代 碼 長 度 。 2 指 令 系 統(tǒng)2.3 0.15 1.00 0.39 0.19 0.10 0.06 0.03 0.31 0.61 0.010.020.030.040.070.080.090.160.200.30 答 ： (1) 霍 夫 曼 樹 如 下 ： 2 指 令 系 統(tǒng)2.3 霍 夫 曼 編 碼

24、的 結(jié) 果 以 及 各 編 碼 的 長 度 如 下 所 示 ：0.30 0.20 0.16 0.09 0.08 0.07 0.04 0.03 0.02 0.0111 01 101 001 1001 1000 0001 00001 000001 000002 2 3 3 4 4 4 5 6 6平 均 代 碼 長 度 為(0.30+0.20) 2 + (0.16+0.09) 3 + (0.08+0.07+0.04) 4 + 0.03 5 + (0.02+0.01) 6 = 1 + 0.75 + 0.76 + 0.15 + 0.18 = 2.84 2 指 令 系 統(tǒng)2.3 (2) 用 擴 展 霍 夫

25、 曼 編 碼 法 對 操 作 碼 進 行 編 碼 ， 限 兩 種操 作 碼 長 度 ， 采 用 長 度 為 2和 長 度 為 4兩 種 編 碼 ： 0.30 0.20 0.16 0.09 0.08 0.07 0.04 0.03 0.02 0.01 00 01 1000 1001 1010 1011 1100 1101 1110 1111平 均 代 碼 長 度 為 (0.30+0.20) 2 + (1-0.30-0.20) 4 = 3.0 2 指 令 系 統(tǒng)2.4 P127頁 習(xí) 題 2.13出 現(xiàn) 的 概 率 Huffman編 碼 2/8擴 展 碼 3/7擴 展 碼0.25 10 00 000

26、.20 00 01 010.15 110 1000 100.10 010 1001 110000.08 0111 1010 110010.08 1110 1011 110100.05 0110 1100 11011 0.04 11110 1101 111000.03 111111 1110 111010.02 111110 1111 11110 解 ： 2 指 令 系 統(tǒng)2.4 P127頁 習(xí) 題 2.13 解 ：出 現(xiàn) 的 概 率 Huffman編 碼 2/8擴 展 碼 3/7擴 展 碼操 作 碼 平 均長 度 2.99 3.1 3.2操 作 碼 的 信息 冗 余 量 n1i ii lp平

27、均 長 度 956635.2.log*1 2 ni ii ppH 2 指 令 系 統(tǒng)2.4 P127頁 習(xí) 題 2.13 解 ： 度本 編 碼 操 作 碼 的 平 均 長編 碼 操 作 碼 的 平 均 長 度最 優(yōu) HHuffmanR 1出 現(xiàn) 的 概 率 Huffman編 碼 2/8擴 展 碼 3/7擴 展 碼操 作 碼 平 均長 度 2.99 3.1 3.2操 作 碼 的 信息 冗 余 量 1.10% 4.61% 7.59% 2 指 令 系 統(tǒng)2.5 P127頁 習(xí) 題 2.14 2 指 令 系 統(tǒng)2.5 P127頁 習(xí) 題 2.14 解 :（ 1） 應(yīng) 采 用 Huffman編 碼 ，

28、構(gòu) 造 Huffman樹 如 下 ： 2 指 令 系 統(tǒng)2.5 P127頁 習(xí) 題 2.14 2 指 令 系 統(tǒng)2.5 P127頁 習(xí) 題 2.14 2 指 令 系 統(tǒng)2.5 P127頁 習(xí) 題 2.14 2 指 令 系 統(tǒng)2.6 P128頁 習(xí) 題 2.15 2 指 令 系 統(tǒng)2.6 P128頁 習(xí) 題 2.15 解 :（ 1） 首 先 ， 我 們 可 以 根 據(jù) 指 令 地 址 的 數(shù) 量 來 決 定 各 種 指 令在 指 令 空 間 上 的 分 布 ： 2 指 令 系 統(tǒng)2.6 P128頁 習(xí) 題 2.15 2 指 令 系 統(tǒng)2.6 P128頁 習(xí) 題 2.15 2 指 令 系 統(tǒng)2.7

29、 P129頁 習(xí) 題 2.20 解 ：START: MOVE AS, R1 MOVE NUM, R2LOOP: MOVE (R1), AD-AS(R1) INC R1 DEC R2 BGT LOOP HALTNUM: N HALT指 令 共 取 100次 ， 但 前 99次 都被 取 消 。 2 指 令 系 統(tǒng)2.7 P129頁 習(xí) 題 2.20 解 ： (1)START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1)LOOP: INC R1 DEC R2 BGT LOOP _ _ MOVE (R1), AD-AS(R1) _ _ HALTNUM:

30、 N MOVE指 令 共 取100次 ， 但 前 99次 都 被 正 常 執(zhí)行 ， 只 有 最 后 1次 被 取 消 。 2 指 令 系 統(tǒng)2.7 P129頁 習(xí) 題 2.20 解 ： (2)因 為 采 用 指 令 取 消 技 術(shù) 前 ， 取 消 指 令 次 數(shù) 為 99次 ，而 在 采 用 指 令 取 消 技 術(shù) 后 ， 取 消 指 令 次 數(shù) 為 1次 ，所 以 節(jié) 省 的 指 令 周 期 數(shù) 為 ： 99 1 98 2 指 令 系 統(tǒng)2.7 P129頁 習(xí) 題 2.20START: MOVE AS, R1 MOVE NUM, R2 MOVE (R1), AD-AS(R1) INC R1L

31、OOP: DEC R2 BGT LOOP _ _ _ MOVE (R1), AD-AS(R1) _ _ _ INC R1 _ _ _ HALTNUM: N 解 ： (3) 3 存 儲 系 統(tǒng)3.1 名 詞 解 釋 返 回 目 錄 1. 存 儲 系 統(tǒng) :由 多 個 不 同 性 能 的 存 儲 器 組 成 的 有 機 的 一體 化 的 存 儲 體 。2. LRU:近 期 最 少 使 用 算 法 (Least Recently Used Algorithm)。 一 種 頁 面 替 換 算 法 ， 這 種 算 法 選 擇 近期 最 少 訪 問 的 頁 面 作 為 被 替 換 的 頁 面 。3. LF

32、U： 最 久 沒 用 使 用 的 算 法 LFU（ Least Frequently Used Algorithm） 。 一 種 頁 面 替 換 算 法 ，這 種 算 法 把 近 期 最 久 沒 有 訪 問 過 的 頁 面 作 為 被 替 換的 頁 面 。 3 存 儲 系 統(tǒng)3.1 名 詞 解 釋 4. “顛 簸 ” 現(xiàn) 象 (thrashing)： 下 次 就 要 使 用 的 頁 面 本次 被 替 換 出 去 ， 這 種 現(xiàn) 象 稱 為 。5. 全 相 聯(lián) 映 象 ： 主 存 中 的 任 一 塊 可 以 被 放 置 到 Cache中的 任 意 一 個 位 置 。6. 直 接 映 象 ： 主

33、存 中 的 每 一 塊 只 能 被 放 置 到 Cache中 唯一 的 一 個 位 置 。 7. 組 相 聯(lián) ： 主 存 中 的 每 一 塊 可 以 被 放 置 到 Cache中 唯 一的 一 個 組 中 的 任 何 一 個 位 置 。 3 存 儲 系 統(tǒng)3.1 名 詞 解 釋 8. 寫 直 達 法 ： 執(zhí) 行 “ 寫 ” 操 作 時 ， 不 僅 寫 入 Cache， 而且 也 寫 入 下 一 級 存 儲 器 。9. 寫 回 法 ： 執(zhí) 行 “ 寫 ” 操 作 時 ， 只 寫 入 Cache。 僅 當(dāng)Cache中 相 應(yīng) 的 塊 被 替 換 時 ， 才 寫 回 主 存 。10.按 寫 分 配

34、(寫 時 取 )： 寫 失 效 時 ， 先 把 所 寫 單 元 所 在的 塊 調(diào) 入 Cache， 再 行 寫 入 .11.不 按 寫 分 配 (繞 寫 法 )： 寫 失 效 時 ， 直 接 寫 入 下 一 級存 儲 器 而 不 調(diào) 塊 。 3 存 儲 系 統(tǒng)3.2 簡 答 1. 常 用 的 頁 面 替 換 算 法 有 哪 些 ？ 隨 機 算 法 RAND算 法 (random Algorithm) FIFO算 法 （ first in first out Algorithm) 近 期 最 少 使 用 LRU算 法 (Least Recently Used Algorithm) 最 久 沒 用

35、 使 用 的 算 法 LFU（ Least Frequently Used Algorithm） 最 優(yōu) 替 換 算 法 ， 即 OPT算 法 （ Optional Replacement algorithm） 3 存 儲 系 統(tǒng)3.2 簡 答 2. 虛 擬 存 儲 器 中 ， 影 響 主 存 命 中 率 的 主 要 因 素 有 ？ 程 序 在 執(zhí) 行 過 程 中 的 頁 地 址 流 的 分 布 情 況 ； 所 采 用 的 頁 面 替 換 算 法 ； 頁 面 的 大 小 主 存 容 量 頁 面 調(diào) 度 算 法 3 存 儲 系 統(tǒng)3.2 簡 答 3. 簡 要 介 紹 Cache與 主 存 的 三

36、 種 地 址 映 象 方 式 ， 并 舉 例加 以 說 明 ？(略 ) 3 存 儲 系 統(tǒng)3.3 P205頁 習(xí) 題 3.14 解 ： (1)頁 地址 流 p2 p3 p2 p1 p5 p2 p4 p5 p3 p2 p5 p2 命 中次 數(shù)3個主 存頁 面FIFO 2 2 2 2 5 5 5 5 3 3 3 3 33 3 3 3 2 2 2 2 2 5 51 1 1 4 4 4 4 4 2調(diào)入 調(diào)入 命中 調(diào)入 替換 替換 替換 命中 替換 命中 替換 替換 3 存 儲 系 統(tǒng)3.3 P205頁 習(xí) 題 3.14 解 ： (1)頁 地址 流 p2 p3 p2 p1 p5 p2 p4 p5 p3

37、 p2 p5 p2 命 中次 數(shù)3個主 存頁 面LFU 2 2 2 2 2 2 2 2 3 3 3 3 53 3 3 5 5 5 5 5 5 5 51 1 1 4 4 4 2 2 2調(diào)入 調(diào)入 命中 調(diào)入 替換 命中 替換 命中 替換 替換 命中 命中 3 存 儲 系 統(tǒng)3.3 P205頁 習(xí) 題 3.14 解 ： (1)頁 地址 流 p2 p3 p2 p1 p5 p2 p4 p5 p3 p2 p5 p2 命 中次 數(shù)3個主 存頁 面OPT 2 2 2 2 2 2 4 4 4 2 2 2 63 3 3 3 3 3 3 3 3 3 31 5 5 5 5 5 5 5 5調(diào)入 調(diào)入 命中 調(diào)入 替換

38、 命中 替換 命中 命中 替換 命中 命中 3 存 儲 系 統(tǒng)3.3 P205頁 習(xí) 題 3.14 解 ： (2)FIFO頁 面 替 換 算 法 的 頁 命 中 率 ： 3/12LFU頁 面 替 換 算 法 的 頁 命 中 率 ： 5/12OPT頁 面 替 換 算 法 的 頁 命 中 率 ： 6/12 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.15 解 ： (1)可 能 的 最 高 頁 命 中 率 出 現(xiàn) 在 : 頁 地 址 流 中 每 一 種 都 可 以 單 獨 占 一 個 頁 面 時 ，因 為 對 于 各 種 頁 地 址 流 ， 都 是 第 一 次 “ 調(diào) 入 ” ， 其后 各 次

39、 都 是 “ 命 中 ” 。 在 此 例 中 ， 需 5個 頁 面 。 因 此 ：可 能 的 最 高 頁 命 中 率 （ 頁 地 址 流 個 數(shù) 頁 地 址 流 種 數(shù) ） /頁 地 址 流 個 數(shù) （ 12 5） /12= 7/12 3 存 儲 系 統(tǒng) 解 ： (1)或 通 過 “ 堆 棧 模 擬 法 ” ， 求 得 命 中 次 數(shù) 隨 主 存 頁 數(shù) 變 化 的 函數(shù) 關(guān) 系 。 下 圖 就 是 “ 堆 棧 模 擬 圖 ” ， 其 中 “ ” 表 示 命 中 。 Hmax=7/12 58.3%3.4 P205頁 習(xí) 題 3.15 3 存 儲 系 統(tǒng) 解 ： (2)至 少 分 配 4個 頁

40、面 才 能 獲 得 最 高 的 命 中 率 7/12 .3.4 P205頁 習(xí) 題 3.15 3 存 儲 系 統(tǒng) 解 ： (3)訪 問 存 儲 單 元 的 命 中 率 命 中 次 數(shù) /總 訪 問 次 數(shù) (12 1024-5)/(12 1024) 12283/12288 99.96% 分 析 ： 頁 “ 不 命 中 ” 時 ， 僅 第 1次 不 命 中 ， 其 它 1023次都 是 命 中 的 。 而 在 頁 “ 命 中 ” 時 ， 1024次 都 是 命 中 的 。所 以 總 訪 問 次 數(shù) 為 12*1024， 不 命 中 次 數(shù) 為 53.4 P205頁 習(xí) 題 3.15 3 存 儲

41、系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 1） 主 存 地 址區(qū) 號 組 號 塊 號 塊 內(nèi) 地 址 6 5 4 3 0 組 號 塊 號 塊 內(nèi) 地 址 5 4 3 0 解 ： （ 2） 緩 存 地 址 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 3） 主 存 與 Cache的 塊 映 象 關(guān) 系 C0C1C2C3B0B1B2B3B4B5B6B7 Cache主 存 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 3） 主 存 與 Cache的 塊 映 象 關(guān) 系 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 4）

42、通 過 作 “ 實 存 狀 況 圖 ” 模 擬 各 虛 塊 的 調(diào) 度情 況 ， 可 獲 得 Cache的 塊 地 址 流 序 列 。此 問 最 容 易 出 錯 的 地 方 是 忽 略 “ 組 相 聯(lián) ” 地 址 約 束 ，將 虛 頁 裝 錯 實 組 。 另 外 沒 有 及 時 標(biāo) 注 “ *” 號 也 容 易導(dǎo) 致 淘 汰 對 象 錯 誤 。 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 5） 采 用 LFU替 換 算 法 ， 命 中 率 為 4/12頁 地址 流 B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 命 中率C0C1 C2C3 4 4

43、 4 4 4 4 4 4 4 41 1 1 1 0 0 5 5 5 4/126 6 6 6 6 6 6 6 6 6 7 72 2 2 2 2 3 3 3 3 3 3調(diào)入 調(diào)入 調(diào)入 調(diào)入 命中 命中 替換 替換 命中 替換 替換 命中 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 6） 采 用 FIFO替 換 算 法 ， 命 中 率 為 3/12頁 地址 流 B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 命 中率C0C1 C2C3 4 4 4 4 4 0 0 5 5 41 1 1 1 1 4 4 4 5 3/126 6 6 6 6 6 3 3 3

44、 3 3 32 2 2 2 2 2 2 2 2 7 7調(diào)入 調(diào)入 調(diào)入 調(diào)入 命中 命中 替換 替換 替換 替換 替換 命中 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 7） 1采 用 LFU替 換 算 法 (全 相 聯(lián) )， 命 中 率 3/12頁 地址 流 B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 命 中率C0C1 C2C3 6 6 6 6 6 6 6 6 6 5 5 52 2 2 2 2 3 3 3 3 7 7 3/124 4 4 4 4 4 4 4 4 41 1 1 1 0 0 0 0 3調(diào)入 調(diào)入 調(diào)入 調(diào)入 命中 命中 替換 替

45、換 命中 替換 替換 替換 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （ 7） 2采 用 FIFO替 換 算 法 (全 相 聯(lián) )， 命 中 率 4/12頁 地址 流 B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 命 中率C0C1 C2C3 6 6 6 6 6 6 3 3 3 3 3 32 2 2 2 2 2 0 0 0 0 0 4/124 4 4 4 4 4 4 4 7 71 1 1 1 1 1 5 5 5調(diào)入 調(diào)入 調(diào)入 調(diào)入 命中 命中 替換 替換 命中 替換 替換 替換 3 存 儲 系 統(tǒng)3.4 P205頁 習(xí) 題 3.19 解 ： （

46、8）訪 問 存 儲 單 元 的 命 中 率 命 中 次 數(shù) /總 訪 問 次 數(shù) (12 16-8)/(12 16) 184/192 95.8% 分 析 ： 頁 “ 不 命 中 ” 時 ， 僅 第 1次 不 命 中 ， 其 它 15次 都是 命 中 的 。 而 在 頁 “ 命 中 ” 時 ， 16次 都 是 命 中 的 。 所以 總 訪 問 次 數(shù) 為 12*16， 不 命 中 次 數(shù) 為 8 4 輸 入 輸 出 系 統(tǒng)4.1 名 詞 解 釋 1. 通 道 處 理 機 ： 一 種 能 夠 執(zhí) 行 有 限 輸 入 輸 出 指 令 ， 并且 能 夠 被 多 臺 外 圍 設(shè) 備 共 享 的 小 型

47、DMA專 用 處 理 機 。 4 輸 入 輸 出 系 統(tǒng)4.2 簡 答 1. 通 道 的 分 類 ？ 4 輸 入 輸 出 系 統(tǒng)4.3 P251頁 習(xí) 題 4.7 解 ： （ 1） 字 節(jié) 多 路 通 道 的 實 際 工 作 流 量 為 ： fBYTE=100+33.3+33.3+20+10=196.6(KB/s) （ 2） 在 設(shè) 計 最 大 通 道 流 量 時 ， 應(yīng) 留 有 一 定 的 余 量 ，對 于 字 節(jié) 多 路 通 道 ， 通 道 的 最 大 流 量 應(yīng) 略 大 于 所 有連 接 在 這 個 通 道 上 的 設(shè) 備 的 流 量 之 和 。 因 此 設(shè) 計 ： a) 通 道 的 最

48、 大 流 量 f MAX BYTE=200(KB/s) b) 通 道 的 工 作 周 期 T 1/200 000=5us/byte 4 輸 入 輸 出 系 統(tǒng)4.3 P251頁 習(xí) 題 4.7 （ 3） 由 于 通 道 工 作 在 最 大 流 量 ， 故 工 作 周 期 為 5us,由 時 間 關(guān) 系 圖 可 知 ， 通 道 處 理 完 各 臺 設(shè) 備 的 第 一 次數(shù) 據(jù) 服 務(wù) 請 求 的 時 刻 如 下 ：D1： 5usD2： 10usD3： 20usD4： 30usD5： 90us 通 道 分 時 為 各 臺 設(shè) 備 服 務(wù) 的 時 間 關(guān) 系 圖 （ 略 ） 解 ： 4 輸 入 輸

49、出 系 統(tǒng)4.4 P252頁 習(xí) 題 4.8 解 ：（ 1） 字 節(jié) 多 路 通 道 的 實 際 工 作 流 量 為 ： fBYTE=1/10+1/75+1/15+1/50=200(KB/s)通 道 的 工 作 周 期 為 ：T 1/200 000=5us/byte 4 輸 入 輸 出 系 統(tǒng)4.4 P252頁 習(xí) 題 4.8 解 ：（ 2） Ts+Td=5us， 通 道 時 間 圖 如 下 。 作 圖 時 注 意 ： 至 少 要畫 到 最 慢 設(shè) 備 的 第 二 次 請 求 出 現(xiàn) ， 才 能 確 定 是 否 丟 失 數(shù) 據(jù)（ 因 為 響 應(yīng) 優(yōu) 先 級 低 的 設(shè) 備 較 易 丟 失 數(shù)

50、據(jù) ） 。 4 輸 入 輸 出 系 統(tǒng)4.4 P252頁 習(xí) 題 4.8 解 ：（ 3） 5， 160， 20， 40；（ 4） D2丟 失 第 一 次 請 求 的 數(shù) 據(jù) ； （ 5） 可 用 以 下 三 種 方 法 解 決 ： （ 見 P245） 增 加 通 道 的 最 大 流 量 ， 保 證 連 接 在 通 道 上 的 所 有 設(shè) 備 的數(shù) 據(jù) 傳 送 請 求 能 夠 及 時 得 到 通 道 的 響 應(yīng) 。 動 態(tài) 改 變 設(shè) 備 的 優(yōu) 先 級 。 增 加 一 定 數(shù) 量 的 數(shù) 據(jù) 緩 沖 器 ， 特 別 是 對 優(yōu) 先 級 比 較 低 的設(shè) 備 。 如 例 中 ， 為 D5增 加

51、一 數(shù) 據(jù) 緩 沖 器 ， 則 其 第 一 次 數(shù)據(jù) 傳 送 請 求 可 以 在 第 85微 秒 處 得 到 通 道 的 響 應(yīng) ， 第 二 次在 145微 秒 處 響 應(yīng) 。 所 有 設(shè) 備 的 數(shù) 據(jù) 都 不 會 丟 失 。 5 標(biāo) 量 處 理 機5.1 名 詞 解 釋 1. 流 水 線 技 術(shù) ： 指 將 一 個 重 復(fù) 的 時 序 過 程 分 解 成 為 若干 個 子 過 程 ， 而 每 個 子 過 程 都 可 有 效 地 在 其 專 用 功能 段 上 與 其 他 子 過 程 同 時 執(zhí) 行 。2. 靜 態(tài) 流 水 線 ： 在 同 一 時 刻 ， 流 水 線 的 各 段 只 能 按 同

52、一 種 功 能 的 連 接 方 式 工 作 。3. 動 態(tài) 流 水 線 ： 在 同 一 時 刻 ， 流 水 線 的 各 段 可 以 按 不同 功 能 的 連 接 方 式 工 作 。 5 標(biāo) 量 處 理 機5.1 名 詞 解 釋 4. 吞 吐 率 ： 吞 吐 率 是 指 單 位 時 間 內(nèi) 流 水 線 所 完 成 的 任務(wù) 數(shù) 或 輸 出 結(jié) 果 的 數(shù) 量 。5. 通 過 時 間 ： 第 1個 任 務(wù) 從 進 入 流 水 線 到 流 出 流 水 線 的時 間 稱 為 通 過 時 間 。6. 排 空 時 間 ： 最 后 1個 任 務(wù) 從 進 入 流 水 線 到 流 出 流 水 線的 時 間 稱

53、為 排 空 時 間 。 5.2 簡 答 5 標(biāo) 量 處 理 機1. 衡 量 流 水 線 性 能 的 主 要 指 標(biāo) 有 哪 些 ？吞 吐 率 、 加 速 比 和 效 率 。吞 吐 率 是 指 單 位 時 間 內(nèi) 流 水 線 所 完 成 的 任 務(wù) 數(shù) 或輸 出 結(jié) 果 的 數(shù) 量 。加 速 比 是 指 流 水 線 的 速 度 與 等 功 能 非 流 水 線 的 速 度之 比 。效 率 是 指 流 水 線 的 設(shè) 備 利 用 率 。 5.2 簡 答 5 標(biāo) 量 處 理 機2. 流 水 線 各 段 執(zhí) 行 時 間 不 相 等 時 ， 消 除 瓶 頸 的 方 法 ？3. 數(shù) 據(jù) 相 關(guān) 有 哪 幾

54、類 ？ 細(xì) 分 瓶 頸 段 重 復(fù) 設(shè) 置 瓶 頸 段 寫 后 讀 讀 后 寫 寫 寫 5.3 例 5.1 5 標(biāo) 量 處 理 機例 5.1 在 靜 態(tài) 流 水 線 上 計 算 求 ： 吞 吐 率 ， 加 速 比 ， 效 率 。 41i ii BA 5.3 例 5.1 5 標(biāo) 量 處 理 機用 教 材 P283圖 5.32所 示 的 TI-ASC計 算 機 的 多 功 能 靜 態(tài) 流 水 線 計 算 . 5.3 例 5.1 5 標(biāo) 量 處 理 機解 ： (1) 確 定 適 合 于 流 水 處 理 的 計 算 過 程(2) 畫 時 空 圖 (3) 計 算 性 能 吞 吐 率 TP 7 (20 t

55、) 加 速 比 S (34 t) (20 t) 1.7 效 率 E (4 4 3 6) (8 20) 0.21 5.3 例 5.1 5 標(biāo) 量 處 理 機 5.3 例 5.1 5 標(biāo) 量 處 理 機 5.3 例 5.1 5 標(biāo) 量 處 理 機 5.4 例 5.2 5 標(biāo) 量 處 理 機例 5.2 在 用 一 條 4段 浮 點 加 法 器 流 水 線 計算 8個 浮 點 浮 點 數(shù) 的 和 ：Z A B C D E F G H 求 ： 吞 吐 率 ， 加 速 比 ， 效 率 。 5.4 例 5.2 5 標(biāo) 量 處 理 機 5.4 例 5.2 5 標(biāo) 量 處 理 機 5.5 5 標(biāo) 量 處 理 機

56、 5.5 5 標(biāo) 量 處 理 機 5.5 5 標(biāo) 量 處 理 機 5.5 5 標(biāo) 量 處 理 機 5.6 5 標(biāo) 量 處 理 機 一 個 流 水 線 由 四 段 組 成 ， 其 中 每 當(dāng) 流 經(jīng) 第 三 段 時 ，總 要 在 該 段 循 環(huán) 一 次 才 能 流 到 第 四 段 。 如 果 每 段經(jīng) 過 一 次 的 時 間 都 是 t， 問 ： 當(dāng) 在 流 水 線 的 輸 入 端 每 t時 間 輸 入 任 務(wù) 時 ， 該 流 水 線 會發(fā) 生 什 么 情 況 ？ 此 流 水 線 的 最 大 吞 吐 率 為 多 少 ？ 如 果 每 2 t輸 入 一 個 任 務(wù) ，連 續(xù) 處 理 10個 任 務(wù)

57、的 實 際 吞 吐 率 和 效 率 是 多 少 ？ 當(dāng) 每 段 時 間 不 變 時 ， 如 何 提 高 該 流 水 線 的 吞 吐 率 ？ 仍 連 續(xù)處 理 10個 任 務(wù) 時 ， 其 吞 吐 率 提 高 多 少 ？ 題 ： 5.6 5 標(biāo) 量 處 理 機 解 ： （ 1） 會 發(fā) 生 流 水 線 阻 塞 情 況 。 5.6 5 標(biāo) 量 處 理 機 解 ： 5.6 5 標(biāo) 量 處 理 機 解 ： Stage Time12 34 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9

58、9 9 9 10 10 10 10 10 t23 t 21TPmax 5.6 5 標(biāo) 量 處 理 機 解 ： 54.35%925045TPE 2310TnTp 23T pipelinepipeline t tt Stage Time12 34 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 t23 5.6 5 標(biāo) 量 處 理 機 解 ： （ 3） 重 復(fù) 設(shè) 置 部 件 1 2 3_1 3_2 4 t t t t t 5.6 5 標(biāo)

59、量 處 理 機 解 ： Stage Time11 2 3_1 3_2 4 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 t14 tt 751410TnTP pipeline tt231075吞 吐 率 提 高 倍 數(shù) 1.64 5.7 P342頁 習(xí) 題 5.35 標(biāo) 量 處 理 機 題 ： 5.7 P342頁 習(xí) 題 5.35 標(biāo) 量 處 理 機 解 ：（ 1） 順 序 執(zhí) 行 方 式 ： tnttt tttT nini iii 6)

60、32( )(11 執(zhí) 行分 析取 指 令 5.7 P342頁 習(xí) 題 5.35 標(biāo) 量 處 理 機 解 ：（ 2） 僅 “ 取 指 令 ” 和 “ 執(zhí) 行 ” 重 疊 ：tn tntT )15( 5)1(6 5.7 P342頁 習(xí) 題 5.35 標(biāo) 量 處 理 機 解 ：（ 2） 僅 “ 取 指 令 ” 和 “ 執(zhí) 行 ” 重 疊 ： tn tntT )33( 3)1(6 5.8 P343頁 習(xí) 題 5.75 標(biāo) 量 處 理 機 題 ： 5.8 P343頁 習(xí) 題 5.75 標(biāo) 量 處 理 機 解 ： 段 時 間4321 0 1 2 3 4 5 6 7 8 9 10 11 t 任 務(wù) 輸 入

61、周 期 5.8 P343頁 習(xí) 題 5.75 標(biāo) 量 處 理 機 解 ： （ 下 面 圖 片 中 的 所 有 11均 改 為 7） 5.9 P343頁 習(xí) 題 5.85 標(biāo) 量 處 理 機 題 ： 5.9 P343頁 習(xí) 題 5.85 標(biāo) 量 處 理 機 解 ： 5.9 P343頁 習(xí) 題 5.85 標(biāo) 量 處 理 機 解 ： 5.9 P343頁 習(xí) 題 5.85 標(biāo) 量 處 理 機 解 ： 5.9 P343頁 習(xí) 題 5.85 標(biāo) 量 處 理 機 解 ： 5.10 P343頁 習(xí) 題 5.95 標(biāo) 量 處 理 機 解 ：為 了 縮 短 運 算 時 間 ， 首 先 應(yīng) 考 慮 “ 最 少 切

62、換 算 法 ” ，即 先 執(zhí) 行 完 所 有 乘 法 （ 任 務(wù) 編 號 1-6） 再 執(zhí) 行 加 法 （任 務(wù) 編 號 7-11） ， 其 次 在 加 法 中 采 用 “ 最 少 相 關(guān) 算 法” （ 即 二 叉 樹 算 法 ） 。記 c1=A1 B1， ， c6=A6 B6， 下 圖 (a)是 加 法 的計 算 順 序 二 叉 樹 ， 注 意 任 務(wù) 10應(yīng) 該 用 前 一 級 最 早 完 成的 任 務(wù) 7和 8的 結(jié) 果 ， 如 果 用 任 務(wù) 9的 結(jié) 果 則 要 推 遲 1拍啟 動 ， 使 總 時 間 增 加 1拍 。 5.10 P343頁 習(xí) 題 5.95 標(biāo) 量 處 理 機 解

63、： 5.10 P343頁 習(xí) 題 5.95 標(biāo) 量 處 理 機 解 ： 5.10 P343頁 習(xí) 題 5.95 標(biāo) 量 處 理 機 解 ：根 據(jù) 時 空 圖 得 ：TP = 11/(22 t) = 1/(2 t)S = (6 4 t + 5 4 t)/(22 t) = 2E = (6 4 t + 5 4 t)/(6 22 t) = 1/3 5.11 5 標(biāo) 量 處 理 機 題 ：有 一 條 流 水 線 如 下 所 示 。求 :1） 連 續(xù) 輸 入 10條 指 令 ,該 流 水 線 的 實 際 吞 吐 率 和 效 率 ;2） 該 流 水 線 的 瓶 頸 在 哪 一 段 ？ 請 采 取 三 種 不

64、 同 的 措 施消 除 此 “ 瓶 頸 ” 。 對 于 你 所 給 出 的 新 流 水 線 ， 計 算連 續(xù) 輸 入 10條 指 令 時 ， 其 實 際 吞 吐 率 和 效 率 。 1 2 3 4 50ns 50ns 100ns 200ns 入 出 5.11 5 標(biāo) 量 處 理 機 解 ： （ 1）2200(ns) 2009200)10050(50 t)1n(tT maxm1i ipipeline )(ns2201TnTP 1pipeline 45.45%1154400TPm tTPE m1i i 5.11 5 標(biāo) 量 處 理 機 解 ： （ 2） 瓶 頸 在 3、 4段措 施 1： 變 成

65、八 級 流 水 線 （ 細(xì) 分 ） 1 2 3_1 3_2 4_1 4_4入 出 50ns 50ns 50ns 50ns 50ns 50ns850(ns) 509850 t1)(ntT maxm1i ipipeline )(ns851TnTP 1pipeline 58.82%17108400TPm tiTPE m1i 5.11 5 標(biāo) 量 處 理 機 解 ： （ 2） 瓶 頸 在 3、 4段措 施 2： 變 成 兩 級 流 水 線 （ 合 并 ） 123 4入 出200ns 200ns2200(ns) 20092200 t1)(ntT maxm1i ipipeline )(ns2201TnTP

66、 1pipeline 90.91%11102400TPm tiTPE m 1i 5.11 5 標(biāo) 量 處 理 機 解 ： （ 2） 瓶 頸 在 3、 4段措 施 3： 重 復(fù) 設(shè) 置 硬 件1 2 3-13-2 4-14-24-34-4 5.11 5 標(biāo) 量 處 理 機 解 ： （ 2） 瓶 頸 在 3、 4段措 施 3： 重 復(fù) 設(shè) 置 硬 件 12 3_13_2 4_14_2 4_34_4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 89 910 10 8 9 10 8 9 10 850ns Time Stage 5.11 5 標(biāo) 量 處 理 機 解 ： （ 2） 瓶 頸 在 3、 4段措 施 3： 重 復(fù) 設(shè) 置 硬 件 )(ns851TnTP 1 pipeline 58.82%1710885010400E 5.12 5 標(biāo) 量 處 理 機 題 ：如 果 流 水 線 有 m段 ， 各 段 的 處 理 時 間 分 別 是 ti（i=1， 2， ， m） ， 現(xiàn) 在 有 n個 任 務(wù) 需 要 完 成 ， 且每 個