系統(tǒng)結(jié)構(gòu)答案

第第 一一 章章 1 261 26 假設(shè)高速緩存假設(shè)高速緩存 CacheCache 工作速度為主存的工作速度為主存的 5 5 倍 且倍 且 CacheCache 被訪問命中的概率為被訪問命中的概率為 9090 那么 采 那么 采 用用 CacheCache 后能使整個(gè)存儲系統(tǒng)獲得多高的加速比后能使整個(gè)存儲系統(tǒng)獲得多高的加速比 T0 1 解 根據(jù) Amdahl 定理有 Sn 結(jié)合題意 Cache 工作速度 為 Tn 1 Fe Fe Se 主存的 5 倍 相當(dāng)于改進(jìn)存儲器后獲得的加速比為 5 即 Se 5 Cache 被訪問命中的概率為 90 相當(dāng) 于訪問存儲器的時(shí)間有 90 化在 Cache 上 即 Fe 0 9 所以 Sn 1 1 0 9 0 9 5 3 57 1 271 27 設(shè)計(jì)指令存儲器有兩種不同方案 一種是采用價(jià)格較貴的高速存儲器芯片 另一種是采用價(jià)設(shè)計(jì)指令存儲器有兩種不同方案 一種是采用價(jià)格較貴的高速存儲器芯片 另一種是采用價(jià) 格便宜的低速存儲器芯片 采用后一方案時(shí) 用同樣的經(jīng)費(fèi)可使存儲器總線帶寬加倍 從而每隔格便宜的低速存儲器芯片 采用后一方案時(shí) 用同樣的經(jīng)費(fèi)可使存儲器總線帶寬加倍 從而每隔 2 2 個(gè)時(shí)個(gè)時(shí) 鐘周期可取出鐘周期可取出 2 2 條指令條指令 每條指令為單字長每條指令為單字長 3232 位位 而采用前一方案時(shí) 每一個(gè)時(shí)鐘周期取出一條單字長 而采用前一方案時(shí) 每一個(gè)時(shí)鐘周期取出一條單字長 指令 由于訪存局部性原理 當(dāng)取出指令 由于訪存局部性原理 當(dāng)取出 2 2 個(gè)指令字時(shí) 通常這個(gè)指令字時(shí) 通常這 2 2 個(gè)指令字都要使用 但仍有個(gè)指令字都要使用 但仍有 2525 的時(shí)鐘周 的時(shí)鐘周 期中 取出的期中 取出的 2 2 個(gè)指令字中僅有個(gè)指令字中僅有 1 1 個(gè)指令字是有用的 試問采用這兩種實(shí)現(xiàn)方案所構(gòu)成的存儲器帶寬是個(gè)指令字是有用的 試問采用這兩種實(shí)現(xiàn)方案所構(gòu)成的存儲器帶寬是 多少 多少 解 帶寬是指單位時(shí)間內(nèi)處理的二進(jìn)制位數(shù) 相當(dāng)于頻率 用 f 表示 采用方案 A 時(shí) 存取指令的 CPIa 1 時(shí)鐘周期 指令字 即 fa 1 CPIa 指令字長 1 32 32 位 時(shí)鐘周期 采用方案 B 時(shí) 存取指令的 CPIb 0 75 2 2 0 25 2 1 1 25 時(shí)鐘周期 指令字 即 fa 1 CPIa 指令字長 0 8 32 25 6 位 時(shí)鐘周期 1 281 28 某工作站采用時(shí)鐘頻率為某工作站采用時(shí)鐘頻率為 15MHz15MHz 處理速率為 處理速率為 10MIPS10MIPS 的處理機(jī)來執(zhí)行一個(gè)測試程序 假定每的處理機(jī)來執(zhí)行一個(gè)測試程序 假定每 次存儲器存取為次存儲器存取為 1 1 個(gè)時(shí)鐘周期 試問 個(gè)時(shí)鐘周期 試問 1 1 此計(jì)算機(jī)的有效此計(jì)算機(jī)的有效 CPICPI 是多少是多少 2 2 假定將處理機(jī)的時(shí)鐘頻率提高到假定將處理機(jī)的時(shí)鐘頻率提高到 30MHz30MHz 但存儲器的工作速率不變 這樣 每次存儲器存取需要 但存儲器的工作速率不變 這樣 每次存儲器存取需要 2 2 個(gè)時(shí)鐘周期 如果個(gè)時(shí)鐘周期 如果 3030 指令每條只需要一次存儲器存取操作 另外 指令每條只需要一次存儲器存取操作 另外 5 5 指令每條需要二次存儲器存取操 指令每條需要二次存儲器存取操 作 假定測試程序的指令數(shù)不變 并與原工作站兼容 試求改進(jìn)后的處理機(jī)作 假定測試程序的指令數(shù)不變 并與原工作站兼容 試求改進(jìn)后的處理機(jī) CPICPI 和和 MIPSMIPS 解 1 由 MIPS 時(shí)鐘頻率 CPI 106 則有 CPIA 時(shí)鐘頻率 MIPS 106 1 5 2 當(dāng)時(shí)鐘頻率為 15MHZ 時(shí) 假設(shè)不進(jìn)行存儲操作指令的 CPI 為 x 則要進(jìn)行一次存儲操作指令的 CPI 為 1 x 要進(jìn)行二次存儲操作指令的 CPI 為 2 x 因此有 1 5 x 65 1 x 30 2 x 5 解得 x 1 1 當(dāng)時(shí)鐘頻率為 30MHZ 時(shí) 不進(jìn)行存儲操作指令的 CPI 不變?yōu)?1 1 要進(jìn)行一次存儲操作指令的 CPI 為 2 x 3 1 要進(jìn)行二次存儲操作指令的 CPI 為 4 x 5 1 因此平均 CPI 為 CPIB 1 1 65 3 1 30 5 1 5 1 9 所以 MIPSB 時(shí)鐘頻率 CPIB 106 30 106 1 9 106 15 8MIPS 1 291 29 某計(jì)算機(jī)某計(jì)算機(jī) CacheCache 能存放能存放 20002000 條指令 假設(shè)條指令 假設(shè) 10 10 的指令承擔(dān)了的指令承擔(dān)了 90 90 時(shí)間的指令訪問 而且這時(shí)間的指令訪問 而且這 10 10 指令中每條指令的執(zhí)行時(shí)間相同 如果要執(zhí)行的某程序共指令中每條指令的執(zhí)行時(shí)間相同 如果要執(zhí)行的某程序共 5000050000 條指令 當(dāng)計(jì)算機(jī)執(zhí)行該程序時(shí) 在條指令 當(dāng)計(jì)算機(jī)執(zhí)行該程序時(shí) 在 CacheCache 中能訪問到的指令的概率是多少 中能訪問到的指令的概率是多少 解 由題意可知 45000 條指令承擔(dān) 10 時(shí)間的指令訪問 5000 條指令承擔(dān) 90 時(shí)間的指令訪問 顯 然 5000 條指令被頻繁使用 設(shè)平均使用次數(shù)為 X 另外 45000 條指令僅使用一次 則有 45000 0 1 5000X 0 9 解得 X 81 所以該程序執(zhí)行指令的條數(shù)為 Y 45000 5000 81 假設(shè)頻繁使用的 5000 條指令均勻分布于程序之中 即每次調(diào)入 Cache 的 2000 條指令有 200 條是頻 繁使用的 另假設(shè)每次調(diào)入 Cache 的 2000 條指令中的 1800 條均被使用了一次 所以執(zhí)行該程序時(shí) Cache 中能訪問到的指令的概率為 50000 2000 100 1 301 30 有一臺計(jì)算機(jī) 不同類型指令在理想有一臺計(jì)算機(jī) 不同類型指令在理想 CacheCache 無訪問失敗 與實(shí)際 無訪問失敗 與實(shí)際 CacheCache 有訪問失敗 兩種 有訪問失敗 兩種 情況下的性能如下表 求理想情況下的性能如下表 求理想 CacheCache 相對于實(shí)際相對于實(shí)際 CacheCache 的加速比 的加速比 指令類型指令類型 出現(xiàn)頻率出現(xiàn)頻率 理想理想 CacheCPICacheCPI 實(shí)際實(shí)際 CacheCPICacheCPI 運(yùn)算指令運(yùn)算指令 40 40 1 1 3 3 取數(shù)指令取數(shù)指令 20 20 2 2 8 8 存數(shù)指令存數(shù)指令 15 15 2 2 8 8 控制指令控制指令 25 25 2 2 4 4 解 理想 Cache 情況下指令的平均時(shí)鐘周期數(shù) CPI 為 CPI理想 1 40 2 20 2 15 2 25 1 6 n i IcIiCPIi 1 實(shí)際 Cache 情況下指令的平均時(shí)鐘周期數(shù) CPI 為 CPI實(shí)際 3 40 8 20 8 15 4 25 5 0 n i IcIiCPIi 1 S 實(shí)際 CacheCPU 執(zhí)行時(shí)間 理想 CacheCPU 執(zhí)行時(shí)間 IC 時(shí)鐘周期 CPI實(shí)際 IC 時(shí)鐘周期 CPI理想 CPI CPIA 5 0 1 6 3 12 1 311 31 假設(shè)在一臺假設(shè)在一臺 40MHz40MHz 處理機(jī)上運(yùn)行測試程序共有條指令 由處理機(jī)上運(yùn)行測試程序共有條指令 由 4 4 類指令組成 已知指令的類指令組成 已知指令的 CPICPI 和和 所各占比例如下表 所各占比例如下表 指令類型指令類型 指令比例指令比例 CPICPI 算邏運(yùn)算算邏運(yùn)算 60 60 1 1 CacheCache 命中存取命中存取 18 18 2 2 控制指令控制指令 12 12 4 4 CacheCache 末命中訪主存末命中訪主存 10 10 8 8 1 1 計(jì)算處理機(jī)運(yùn)行該程序的平均計(jì)算處理機(jī)運(yùn)行該程序的平均 CPICPI 2 2 根據(jù)根據(jù) 1 1 所得所得 CPICPI 計(jì)算相應(yīng)的 計(jì)算相應(yīng)的 MIPSMIPS 速率 速率 解 1 CPI 1 60 2 18 4 12 8 10 2 2 n i IcIiCPIi 1 2 MIPS 時(shí)鐘頻率 CPI 106 40 106 2 2 106 18 19 1 321 32 已知已知 4 4 個(gè)程序在個(gè)程序在 A A B B C C 三臺計(jì)算機(jī)上的執(zhí)行時(shí)間三臺計(jì)算機(jī)上的執(zhí)行時(shí)間 秒秒 分別如下表 假設(shè)每個(gè)程序都有分別如下表 假設(shè)每個(gè)程序都有 100 10100 106 6條指令要執(zhí)行 計(jì)算這條指令要執(zhí)行 計(jì)算這 3 3 臺計(jì)算機(jī)對每個(gè)程序的臺計(jì)算機(jī)對每個(gè)程序的 MIPSMIPS 速率 根據(jù)這些速率值 你能否得出這速率 根據(jù)這些速率值 你能否得出這 3 3 臺計(jì)算機(jī)相對性能的明確結(jié)論 你能否找到一種將它們排序的方法 試說明理由 臺計(jì)算機(jī)相對性能的明確結(jié)論 你能否找到一種將它們排序的方法 試說明理由 程序程序 計(jì)算機(jī)計(jì)算機(jī) A A 計(jì)算機(jī)計(jì)算機(jī) B B 計(jì)算機(jī)計(jì)算機(jī) C C 程序程序 1 1 1 1 1010 2020 程序程序 2 2 10001000 100100 2020 程序程序 3 3 500500 10001000 5050 程序程序 4 4 100100 800800 100100 解 1 由 MIPS 的定義有 MIPS Ic Tcpu 106 100 106 Tcpu 106 100 Tcpu 根據(jù)上表中列出的 Tcpu則可計(jì)算出相應(yīng)的 MIPS 如下表所示 程序 計(jì)算機(jī) A 計(jì)算機(jī) B 計(jì)算機(jī) C 程序 1 100 10 5 程序 2 0 1 1 5 程序 3 0 2 0 1 2 程序 4 1 0 125 1 2 由于 MIPS 與指令值 指令使用的頻率等有關(guān) 在同一臺機(jī)器上運(yùn)行不同的程序 得出不同的 速率 MIPS 因此不能僅用 MIPS 來評價(jià)計(jì)算機(jī)性能的優(yōu)劣 而應(yīng)用執(zhí)行程序的算術(shù)平均 Tcpu來評價(jià)比較好 TcpuA 1 1000 500 100 4 400 25 TcpuB 10 100 1000 800 4 477 5 TcpuC 20 20 50 100 4 47 5 所以性能排序?yàn)?C A B 第第 二二 章章 2 252 25 浮點(diǎn)數(shù)系統(tǒng)使用的階碼基值浮點(diǎn)數(shù)系統(tǒng)使用的階碼基值 r re e 2 2 階值位數(shù) 階值位數(shù) q 2q 2 尾數(shù)基值 尾數(shù)基值 r rm m 10 10 尾數(shù)位數(shù) 尾數(shù)位數(shù) p p 1 1 即按照使 即按照使 用的二進(jìn)制位數(shù)來說 等價(jià)于用的二進(jìn)制位數(shù)來說 等價(jià)于 p 4p 4 計(jì)算在非負(fù)階 正尾數(shù) 規(guī)格化情況下的最小尾數(shù)值 最大尾數(shù)值 計(jì)算在非負(fù)階 正尾數(shù) 規(guī)格化情況下的最小尾數(shù)值 最大尾數(shù)值 最大階值 可表示的最小值和最大值及可表示數(shù)的個(gè)數(shù) 最大階值 可表示的最小值和最大值及可表示數(shù)的個(gè)數(shù) 解 最小尾數(shù)值 rm 1 10 1 0 1 最大尾數(shù)值 1 rm p 1 10 1 0 9 最大階值 2q 1 3 可表示數(shù)的最小值 1 rm 1 10 1 0 1 可表示數(shù)的最大值 rm2q 1 1 rm p 103 1 10 1 900 可表示數(shù)的個(gè)數(shù) 2q rmp rm 1 rm 22 101 10 1 10 36 2 262 26 一個(gè)處理機(jī)有一個(gè)處理機(jī)有 I1I1 I10I10 共共 1010 條指令 經(jīng)統(tǒng)計(jì) 各指令在程序中出現(xiàn)的概率如下 條指令 經(jīng)統(tǒng)計(jì) 各指令在程序中出現(xiàn)的概率如下 I1I1 0 250 25 I2I2 0 200 20 I3I3 0 150 15 I4I4 0 100 10 I5I5 0 080 08 I6I6 0 080 08 I7I7 0 050 05 I8I8 0 040 04 I9I9 0 030 03 I10I10 0 020 02 1 1 計(jì)算這 計(jì)算這 1010 條指令的操作碼最短平均長度 條指令的操作碼最短平均長度 2 2 寫出這 寫出這 1010 條指令的條指令的 HuffmanHuffman 編碼 并計(jì)算操作碼編碼的平均長度和信息冗余量 編碼 并計(jì)算操作碼編碼的平均長度和信息冗余量 3 3 采用 采用 3 73 7 擴(kuò)展編碼法和擴(kuò)展編碼法和 2 82 8 擴(kuò)展編碼法編寫這擴(kuò)展編碼法編寫這 1010 條指令的操作碼 并分別計(jì)算編碼的平均長條指令的操作碼 并分別計(jì)算編碼的平均長 度和信息冗余量 說明哪一種擴(kuò)展編碼較好的理由 度和信息冗余量 說明哪一種擴(kuò)展編碼較好的理由 解 1 操作碼編碼的最短平均長度為 H log2pi n i i p 1 H 0 25log20 25 0 20log20 20 0 15log20 15 0 10log20 10 0 08log20 08 0 08log20 08 0 05log20 05 0 04log20 04 0 03log20 03 0 02log20 02 2 96 位 2 根據(jù)給出的使用頻度 在構(gòu)造 Huffman 樹的過程中 有兩個(gè)結(jié)點(diǎn)可供合并 因此可生成不 同的 Huffman 樹 其中給出一棵如圖所示 相應(yīng)的 Huffman 編碼如表所示 1 0 1 0 1 0 I2 I1 1 0 1 0 1 0 I4 1 0 I3 1 0 I6 1 0 I5 I10 I9 I8 I7 IiPi Huffman 編碼 Li 2 5 編碼 3 7 Li 2 4 編碼 2 8 Li I1 0 25 002002002 I2 0 20 102012012 I3 0 15 010310210004 I4 0 10 110311000510014 I5 0 08 0110411001510104 I6 0 08 1110411010510114 I7 0 05 01110511011511004 I8 0 04 01111511100510014 I9 0 03 11110511101511104 I10 0 02 11111511110511114 Huffman 編碼的平均長度為 l li n i i p 1 l 0 25 2 0 20 2 0 15 3 0 10 3 0 08 4 0 08 4 0 05 5 0 04 5 0 03 5 0 02 5 2 99 位 Huffman 編碼的信息冗余量為 R 1 H l 1 2 96 2 99 100 1 0 3 3 7 擴(kuò)展編碼和 2 8 擴(kuò)展編碼如表所示 3 7 擴(kuò)展編碼要求短碼碼點(diǎn)數(shù)為 3 長碼碼點(diǎn)數(shù)為 7 所以短碼長取 2 位 有碼點(diǎn) 22 4 個(gè) 用一個(gè)作 1 00 0 02 0 05 0 13 0 23 0 43 0 03 0 08 0 10 0 20 0 04 0 09 0 17 0 32 0 57 0 05 0 08 0 15 0 25 擴(kuò)展標(biāo)志 長碼長取 3 位 有碼點(diǎn) 23 8 個(gè) 有一個(gè)未被利用 即有一個(gè) 余碼點(diǎn) 編碼的平均長度為 l 0 25 0 20 0 15 2 0 10 0 08 0 08 0 05 0 04 0 03 0 02 5 3 2 位 3 7 擴(kuò)展編碼的信息冗余量為 R 1 H l 1 2 96 3 2 100 7 5 2 8 擴(kuò)展編碼要求短碼碼點(diǎn)數(shù)為 2 長碼碼點(diǎn)數(shù)為 8 所以短碼長取 2 位 有碼點(diǎn) 22 4 個(gè) 用二個(gè)作 擴(kuò)展標(biāo)志 長碼長取 2 位 有碼點(diǎn) 22 2 8 個(gè) 碼點(diǎn)全部被利用 即沒有多余碼點(diǎn) l 0 25 0 20 2 0 15 0 10 0 08 0 08 0 05 0 04 0 03 0 02 4 3 1 位 2 8 擴(kuò)展編碼的信息冗余量為 R 1 H l 1 2 96 3 1 100 4 5 可見 2 8 擴(kuò)展編碼優(yōu)于 3 7 擴(kuò)展編碼 2 272 27 經(jīng)統(tǒng)計(jì) 某種處理機(jī)經(jīng)統(tǒng)計(jì) 某種處理機(jī) 1414 條指令的使用頻度分別為 條指令的使用頻度分別為 0 010 01 0 150 15 0 120 12 0 03 0 02 0 04 0 02 0 04 0 01 0 13 0 15 0 140 03 0 02 0 04 0 02 0 04 0 01 0 13 0 15 0 14 0 11 0 030 11 0 03 分別給出它們的定 分別給出它們的定 長碼 長碼 HuffmanHuffman 編碼 只能有兩種碼長且平均長度盡可能短的擴(kuò)展編碼 并分別計(jì)算三種編碼的平均長度 編碼 只能有兩種碼長且平均長度盡可能短的擴(kuò)展編碼 并分別計(jì)算三種編碼的平均長度 0 15 0 15 0 14 0 13 0 12 0 11 0 04 0 04 0 03 0 03 0 02 0 02 0 01 0 01 2 282 28 用于文字處理的某專用機(jī) 每個(gè)文字符用用于文字處理的某專用機(jī) 每個(gè)文字符用 4 4 位十進(jìn)制數(shù)字 位十進(jìn)制數(shù)字 0 0 9 9 編碼表示 空格用 編碼表示 空格用 表示 表示 在對傳送的文字符和空格進(jìn)行統(tǒng)計(jì)后 得出它們的使用頻度如下 在對傳送的文字符和空格進(jìn)行統(tǒng)計(jì)后 得出它們的使用頻度如下 0 200 20 0 0 170 0 17 1 0 061 0 06 2 0 082 0 08 3 0 113 0 11 4 0 084 0 08 5 5 0 050 05 6 0 086 0 08 7 0 137 0 13 8 0 038 0 03 9 0 019 0 01 1 1 若對數(shù)字 若對數(shù)字 0 0 9 9 和空格采用二進(jìn)制編碼 試設(shè)計(jì)編碼平均長度最短的編碼 和空格采用二進(jìn)制編碼 試設(shè)計(jì)編碼平均長度最短的編碼 2 2 若傳送 若傳送 10106 6個(gè)文字符號 且每個(gè)文字符號后均自動跟一個(gè)空格 按最短的編碼 共需傳送多少個(gè)文字符號 且每個(gè)文字符號后均自動跟一個(gè)空格 按最短的編碼 共需傳送多少 個(gè)二進(jìn)制位 若傳送波特率為個(gè)二進(jìn)制位 若傳送波特率為 9600bPS9600bPS 共需傳送多少時(shí)間 共需傳送多少時(shí)間 3 3 若對數(shù)字 若對數(shù)字 0 0 9 9 和空格采用和空格采用 4 4 位定長碼編碼 重新計(jì)算問題 位定長碼編碼 重新計(jì)算問題 2 2 解 1 操作碼編碼的平均長度最短為 Huffman 編碼 生成的 Huffman 樹 如圖所示 相應(yīng)的 Huffman 編碼如表所示 l li 3 23 位 n i i p 1 2 根據(jù)題意 每個(gè)字符的二進(jìn)制碼的平均長度為 3 23 4 1 16 15 位 若要傳輸 106 個(gè)字符 則要傳輸二進(jìn)制位數(shù)為 106 16 15 1 615 107 位 若波特率為 56Kb s 則傳輸時(shí)間為 1 615 107 56 103 288 s 3 當(dāng)采用四位定長編碼時(shí) 則需要傳輸二進(jìn)制位數(shù)為 106 4 4 1 2 107 位 傳輸時(shí) 間為 2 107 56 103 357 s 1 0 1 0 1 0 1 00 0 01 0 04 0 09 0 20 0 40 0 03 0 05 0 11 0 20 0 080 06 0 14 0 27 0 60 0 16 0 08 0 13 0 33 0 17 0 08 1 0 1 0 1 0 3 3 7 7 0 0 5 5 1 1 6 6 4 4 2 2 9 9 8 8 2 292 29 一臺模型機(jī)共有一臺模型機(jī)共有 7 7 條指令 各指令的使用頻度分別為 條指令 各指令的使用頻度分別為 35 35 25 25 20 20 10 10 5 5 3 3 2 2 有 有 8 8 個(gè)通用數(shù)據(jù)寄存器 個(gè)通用數(shù)據(jù)寄存器 2 2 個(gè)變址寄存器 個(gè)變址寄存器 1 1 要求操作碼的平均長度最短 請?jiān)O(shè)計(jì)操作碼的編碼 并計(jì)算操作碼編碼的平均長度 要求操作碼的平均長度最短 請?jiān)O(shè)計(jì)操作碼的編碼 并計(jì)算操作碼編碼的平均長度 2 2 設(shè)計(jì) 設(shè)計(jì) 8 8 位字長的寄存器位字長的寄存器 寄存器型指令寄存器型指令 3 3 條 條 1616 位字長的寄存器一存儲器型變址尋址方式指位字長的寄存器一存儲器型變址尋址方式指 令令 4 4 條 變址范圍不小于正 負(fù)條 變址范圍不小于正 負(fù) 127127 請?jiān)O(shè)計(jì)指令格式 并給出指令各字段的長度和操作碼的編碼 請?jiān)O(shè)計(jì)指令格式 并給出指令各字段的長度和操作碼的編碼 2 302 30 一臺模型機(jī)共有一臺模型機(jī)共有 7 7 條指令 各指令的使用頻度分別為 條指令 各指令的使用頻度分別為 35 35 25 25 20 20 10 10 5 5 3 3 2 2 有 有 8 8 個(gè)通用數(shù)據(jù)寄存器 個(gè)通用數(shù)據(jù)寄存器 2 2 個(gè)變址寄存器 個(gè)變址寄存器 1 1 要求操作碼的平均長度最短 請?jiān)O(shè)計(jì)操作碼的編碼 并計(jì)算操作碼編碼的平均長度 要求操作碼的平均長度最短 請?jiān)O(shè)計(jì)操作碼的編碼 并計(jì)算操作碼編碼的平均長度 2 2 設(shè)計(jì) 設(shè)計(jì) 8 8 位字長的寄存器位字長的寄存器 寄存器型指令寄存器型指令 3 3 條 條 1616 位字長的寄存器一存儲器型變址尋址方式指令位字長的寄存器一存儲器型變址尋址方式指令 4 4 條 變址范圍不小于正 負(fù)條 變址范圍不小于正 負(fù) 127127 請?jiān)O(shè)計(jì)指令格式 并給出指令各字段的長度和操作碼的編碼 請?jiān)O(shè)計(jì)指令格式 并給出指令各字段的長度和操作碼的編碼 解 1 操作碼編碼的平均長度最短為 Huffman 編碼 生成的 Huffman 樹如圖所示 相應(yīng)的 Huffman 編碼如表所示 l li 2 35 位 n i i p 1 IiPi Huffman 編碼 Li 0 20 102 0 0 17 0003 7 0 13 0103 3 0 11 1103 2 0 08 00104 4 0 08 00114 6 0 08 01104 1 0 06 01114 5 0 05 11104 8 0 03 111105 9 0 01 111115 1 00 0 02 0 05 0 10 0 20 0 40 0 03 0 05 0 10 0 20 0 25 0 60 0 35 2 由于通用寄存器有 8 個(gè) 則指令中通用寄存器字段應(yīng)為 3 位 操作碼字段 2 位可有 4 個(gè)碼點(diǎn) 用三個(gè)碼點(diǎn)表示三條指令 另一個(gè)碼點(diǎn)則作為擴(kuò)展標(biāo)志 所以 3 條 8 位長的寄存器 寄存器型指令格式 如下 由于變址寄存器有 2 個(gè) 則指令中變址寄存器字段應(yīng)為 1 位 變址范圍 127 127 則指令中相對 位移字段應(yīng)為 8 位 操作碼字段前 2 位可有 4 個(gè)碼點(diǎn) 用三個(gè)碼點(diǎn)表示三條指令 另一個(gè)碼點(diǎn)則作為擴(kuò) 展標(biāo)志 擴(kuò)展 2 位正好可表示四條指令 操作碼字段則為 4 位 所以 4 條 16 位長的寄存器 存儲器型指 令格式如下 特別地 當(dāng)采用 3 4 擴(kuò)展編碼時(shí) 使用頻度高的用短碼表示 使用頻度低的用長碼表示 其相應(yīng)的 編碼如表所示 2 312 31 某處理機(jī)的指令字長為某處理機(jī)的指令字長為 1616 位 有二地址指令 一地址指令和零地址指令位 有二地址指令 一地址指令和零地址指令 3 3 類 每個(gè)地址字段類 每個(gè)地址字段 的長度均為的長度均為 6 6 位 位 1 1 如果二地址指令有 如果二地址指令有 1515 條 一地址指令和零地址指令的條數(shù)基本相等 問一地址指令和零地址條 一地址指令和零地址指令的條數(shù)基本相等 問一地址指令和零地址 指令各有多少條 并為這指令各有多少條 并為這 3 3 類指令分配操作碼 類指令分配操作碼 2 2 如果指令系統(tǒng)要求這 如果指令系統(tǒng)要求這 3 3 類指令條數(shù)的比例大致為類指令條數(shù)的比例大致為 1 1 9 9 9 9 問這 問這 3 3 類指令各有多少條 并為這類指令各有多少條 并為這 3 3 類指令分配操作碼 類指令分配操作碼 解 1 操作碼字段取 4 位可有 24 16 個(gè)碼點(diǎn) 用 15 個(gè)碼點(diǎn) 0000 1110 表示 15 條二地址指令 另一個(gè)碼點(diǎn) 1111 則作為擴(kuò)展標(biāo)志 所以 15 條二地址指令格式如下 由于要求一地址指令和零地址指令的條數(shù)基本相等 所以地址碼 1 字段 6 位擴(kuò)展有 26 64 個(gè)碼點(diǎn) 用 63 個(gè)碼點(diǎn) 表示 63 條一地址指令 另一個(gè)碼點(diǎn) 則作為擴(kuò)展標(biāo)志 而用地址碼 2 字段 6 位擴(kuò)展有 26 64 個(gè)碼點(diǎn) 64 個(gè)碼點(diǎn)都用來表示零地址指令 共有 64 條 IiPi Huffman 編碼 Li 2 4 編碼 3 4 Li I1 0 35 002002 I2 0 25 012012 I3 0 20 102102 I4 0 10 110311004 I5 0 05 1110411014 I6 0 03 11110511104 I7 0 02 11111511114 操作碼 2 位 寄存器 1 3 位 寄存器 2 3 位 操作碼 4 位 寄存器 3 位 變址寄存器 1 位 相對位移 8 位 操作碼 4 位 地址碼 1 6 位 地址碼 2 6 位 2 在一中指令條數(shù)的比例大約 1 4 2 4 2 因此若使一地址指令和零地址指令加大一倍 則三 類指令條數(shù)的比例大約 1 9 9 操作碼字段取 4 位時(shí)的 16 個(gè)碼點(diǎn) 用 14 個(gè)碼點(diǎn) 0000 1101 表示 14 條二地址指令 另二個(gè)碼點(diǎn) 1110 與 1111 則作為擴(kuò)展標(biāo)志 擴(kuò)展標(biāo)志 1110 擴(kuò)展地址碼 1 字段 6 位的 64 個(gè)碼點(diǎn) 全部用來表示一地址指令 有 64 條 擴(kuò)展標(biāo)志 1111 擴(kuò)展地址碼 1 字段 6 位的 64 個(gè)碼點(diǎn) 用 62 個(gè)碼點(diǎn) 表示 62 條一地址指令 另二 個(gè)碼點(diǎn) 與 則作為擴(kuò)展標(biāo)志 這樣一地址指令 共有 126 條 擴(kuò)展標(biāo)志 與 擴(kuò)展地址碼 2 字段 6 位 各有 64 個(gè)碼點(diǎn)全部用來表示零地址指令 則有 128 條零地 址指令 2 322 32 某模型機(jī)某模型機(jī) 9 9 條指令使用頻度為 條指令使用頻度為 ADDADD 加 加 30 30 SUBSUB 減 減 24 24 JOMJOM 按負(fù)轉(zhuǎn)移 按負(fù)轉(zhuǎn)移 6 6 STOSTO 存 存 7 7 JMPJMP 轉(zhuǎn)移 轉(zhuǎn)移 7 7 SHRSHR 右移 右移 2 2 CILCIL 循環(huán)左移 循環(huán)左移 3 3 CLACLA 清除 清除 20 20 STPSTP 停機(jī) 停機(jī) 1 1 要求有兩種指令字長 都按雙操作數(shù)指令格式編排 采用擴(kuò)展操作碼 并限制只能有兩種操作碼碼長 要求有兩種指令字長 都按雙操作數(shù)指令格式編排 采用擴(kuò)展操作碼 并限制只能有兩種操作碼碼長 設(shè)該機(jī)有若干通用寄存器 主存為設(shè)該機(jī)有若干通用寄存器 主存為 1616 位寬 按字節(jié)編址 采用按整數(shù)邊界存儲 任何指令都在一個(gè)主存位寬 按字節(jié)編址 采用按整數(shù)邊界存儲 任何指令都在一個(gè)主存 周期中取得 短指令為寄存器周期中取得 短指令為寄存器 寄存器型 長指令為寄存器寄存器型 長指令為寄存器 主存型 主存地址應(yīng)能變址尋址 主存型 主存地址應(yīng)能變址尋址 1 1 僅根據(jù)使用頻度 不考慮其它要求 設(shè)計(jì)出全 僅根據(jù)使用頻度 不考慮其它要求 設(shè)計(jì)出全 HuffmanHuffman 操作碼 計(jì)算其平均碼長 操作碼 計(jì)算其平均碼長 2 2 考慮題目全部要求 設(shè)計(jì)優(yōu)化實(shí)用的操作碼形式 并計(jì)算其操作碼的平均碼長 考慮題目全部要求 設(shè)計(jì)優(yōu)化實(shí)用的操作碼形式 并計(jì)算其操作碼的平均碼長 3 3 該機(jī)允許使用多少可編址的通用寄存器 該機(jī)允許使用多少可編址的通用寄存器 4 4 畫出該機(jī)兩種指令字格式 標(biāo)出各字段之位數(shù) 畫出該機(jī)兩種指令字格式 標(biāo)出各字段之位數(shù) 5 5 指出訪存操作數(shù)地址尋址的最大相對位移量為多少個(gè)字節(jié) 指出訪存操作數(shù)地址尋址的最大相對位移量為多少個(gè)字節(jié) 解 1 根據(jù)給出的使用頻度 在構(gòu)造 Huffman 樹的過程中 有兩個(gè)結(jié)點(diǎn)可供合并 因此可生成不 同的 Huffman 樹 其中給出一棵如圖所示 相應(yīng)的 Huffman 編碼如表所示 Huffman 編碼的平均長度為 l li n i i p 1 l 0 3 2 0 24 2 0 2 2 0 07 4 0 07 4 0 06 4 0 03 5 0 02 6 0 01 6 2 61 位 ADDADD CLACLA SUBSUB J0MJ0M JMPJMP STOSTO CILCIL 0 56 0 01 0 03 0 06 0 12 0 26 0 02 0 03 0 060 07 0 14 1 00 0 20 0 07 0 44 0 240 30 STPSTP SHRSHR 2 任何指令都在一個(gè)主存 周期中取得 那么短指令字長為 8 位 長指令字長為 16 位 又指令都是二地址指令 所以短指令寄存器 寄存器型的格式為 長指令為寄存器 主存型的格式為 由題意可知 指令操作碼采用擴(kuò)展編碼 且只能有兩種碼長 從指令使用頻度來看 ADD SUB 和 CLA 三條指令的使用頻度與其它指令的使用頻度相差較大 所以用兩位操作碼的三個(gè)碼點(diǎn)來表示三條指令 一個(gè)碼點(diǎn)作為擴(kuò)展碼點(diǎn) 且擴(kuò)展三位來表示六條指令 即采用 2 4 擴(kuò)展編碼構(gòu)成 3 6 編碼 2 4 擴(kuò)展編 碼如表所示 2 4 擴(kuò)展編碼 3 6 的平均長度為 l li 2 78 n i i p 1 3 4 由短指令寄存器 寄存器型的格式可知 寄存器號字段長度為 3 位 寄存器個(gè)數(shù)為 8 個(gè) 則各字段長度如圖格式所標(biāo)識 而對于長指令寄存器 主存型 一般變址寄存器是某通用寄存器 則變址寄存器號的字段長度為 3 位 則各字段長度如圖格式所標(biāo)識 5 由于相對位移字段長度為 5 位 因此訪存地址尋址的最大相對位移量為 25 32 字節(jié) 第第 三三 章章 習(xí)習(xí) 題題 3 83 8 在一臺單流水線多操作部件的處理機(jī)上執(zhí)行下面的程序 每條指令的取指令 指令譯碼需要一在一臺單流水線多操作部件的處理機(jī)上執(zhí)行下面的程序 每條指令的取指令 指令譯碼需要一 個(gè)時(shí)鐘周期 個(gè)時(shí)鐘周期 MOVEMOVE ADDADD 和和 MULMUL 操作分別需要操作分別需要 2 2 個(gè) 個(gè) 3 3 個(gè)和個(gè)和 4 4 個(gè)時(shí)鐘周期 每個(gè)操作都在第一個(gè)時(shí)鐘周期個(gè)時(shí)鐘周期 每個(gè)操作都在第一個(gè)時(shí)鐘周期 從通用寄存器中讀操作數(shù) 在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫到通用寄存器中 從通用寄存器中讀操作數(shù) 在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫到通用寄存器中 k k MOVEMOVE R1R1 R0R0 R1 R1 R0 R0 k 1k 1 MULMUL R0R0 R2R2 R1R1 R0 R0 R2 R1 R2 R1 k 2k 2 ADDADD R0R0 R2R2 R3R3 R0 R0 R2 R3 R2 R3 1 1 就程序本身而言 可能有哪幾種數(shù)據(jù)相關(guān)就程序本身而言 可能有哪幾種數(shù)據(jù)相關(guān) 指令 IiPi Huffman 編碼 Li 2 5 編碼 3 6 Li ADDI1 0 30 012002 SUBI2 0 24 112012 CLAI3 0 20 102102 STOI4 0 07 00114110015 JMPI5 0 07 00104110105 JOMI6 0 06 00014110115 CILI7 0 03 000015111005 SHRI8 0 02 6111015 STPI9 0 01 6111105 操作碼 2 位 寄存器 1 3 位 寄存器 2 3 位 操作碼 5 位 寄存器 3 位 變址寄存器 3 位 相對位移 5 位 2 2 在程序?qū)嶋H執(zhí)行過程中 哪幾種數(shù)據(jù)相關(guān)會引起流水線停頓在程序?qū)嶋H執(zhí)行過程中 哪幾種數(shù)據(jù)相關(guān)會引起流水線停頓 3 3 畫出指令執(zhí)行過程的流水線時(shí)空圖 并計(jì)算完成這畫出指令執(zhí)行過程的流水線時(shí)空圖 并計(jì)算完成這 3 3 條指令共需要多少個(gè)時(shí)鐘周期 條指令共需要多少個(gè)時(shí)鐘周期 解 1 就程序本身而言 可能有三種數(shù)據(jù)相關(guān) 若 3 條指令順序流動 則 k 指令對 R1 寄存器的 寫與 k 1 指令對 R1 寄存器的讀形成的 先寫后讀 相關(guān) 若 3 條指令異步流動 則 k 指令對 R0 寄存器 的讀與 k 1 指令對 R0 寄存器的寫形成的 先讀后寫 相關(guān) k 2 指令對 R0 寄存器的寫與 k 1 指令對 R0 寄存器的寫形成的 寫 寫 相關(guān) 2 在程序?qū)嶋H執(zhí)行過程中 二種數(shù)據(jù)相關(guān)會引起流水線停頓 一是 先寫后讀 相關(guān) k 指令對 R1 的寫在程序執(zhí)行開始后的第四個(gè)時(shí)鐘 k 1 指令對 R1 的讀對指令本身是第三個(gè)時(shí)鐘 但 k 1 指令比 k 指令晚一個(gè)時(shí)鐘進(jìn)入流水線 則在程序執(zhí)行開始后的第四個(gè)時(shí)鐘要讀 R1 不能在同一時(shí)鐘周期內(nèi)讀寫同 一寄存器 因此 k 1 指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水線 產(chǎn)生了流水線停頓 二是 寫 寫 相關(guān) k 1 指 令對 R0 的寫對指令本身是第六個(gè)時(shí)鐘 而要求該指令進(jìn)入流水線應(yīng)在程序執(zhí)行開始后的第三個(gè)時(shí)鐘 所 以對 R0 的寫是在程序執(zhí)行開始后的第八個(gè)時(shí)鐘 k 2 指令對 R0 的寫對指令本身是第五個(gè)時(shí)鐘 而 k 2 指 令比 k 1 指令晚一個(gè)時(shí)鐘進(jìn)入流水線 則在程序執(zhí)行開始后的第四個(gè)時(shí)鐘 所以對 R0 的寫是在程序執(zhí)行 開始后的第八個(gè)時(shí)鐘 不能在同一時(shí)鐘周期內(nèi)寫寫同一寄存器 因此 k 2 指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水 線 產(chǎn)生了流水線停頓 另外 可分析 先讀后寫 相關(guān)不會產(chǎn)生流水線的停頓 3 由題意可認(rèn)位該指令流水線由六個(gè)功能段取指 譯碼 取數(shù) 運(yùn)一 運(yùn)二和存數(shù)等組成 則程 序指令執(zhí)行過程的流水線時(shí)空圖如下圖所示 若 3 條指令順序流動 共需要 9 個(gè)時(shí)鐘周期 空間 存數(shù) K 存數(shù) K 1 存數(shù) K 2 存數(shù) 運(yùn)二 K 1 運(yùn)二 運(yùn)一 K 1 運(yùn)一 K 2 運(yùn)一 取數(shù) K 取數(shù) K 1 取數(shù) K 2 取數(shù) 譯碼 K 譯碼 K 1 譯碼 K 2 譯碼 取指 K 取指 K 1 取指 K 2 取指 時(shí)間 0 1 2 3 4 5 6 7 8 9 3 93 9 某流水線由某流水線由 4 4 個(gè)功能部件組成 每個(gè)功能部件的執(zhí)行時(shí)間都為個(gè)功能部件組成 每個(gè)功能部件的執(zhí)行時(shí)間都為 t t 當(dāng)輸入 當(dāng)輸入 1010 個(gè)數(shù)據(jù)后 停頓個(gè)數(shù)據(jù)后 停頓 5t5t 又輸入 又輸入 1010 個(gè)數(shù)據(jù) 如此重復(fù) 計(jì)算流水線的實(shí)際吞吐率 加速比和效率 并畫出時(shí)空圖 個(gè)數(shù)據(jù) 如此重復(fù) 計(jì)算流水線的實(shí)際吞吐率 加速比和效率 并畫出時(shí)空圖 解 該題中的流水線的任務(wù)是非連續(xù)流入的 因此不能直接應(yīng)用公式直接計(jì)算 要利用時(shí)空圖 題 意的流水線時(shí)空圖如下圖所示 空間 S4 1 2 3 4 5 6 7 8 9 10 1 2 S3 1 2 3 4 5 6 7 8 9 10 1 2 S2 1 2 3 4 5 6 7 8 9 10 1 2 S1 1 2 3 4 5 6 7 8 9 10 1 2 時(shí)間 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 TP 10 15 t 0 67 t S T0 TK 10 4 t 15 t 2 67 E 4 10 t 4 15 t 0 67 3 11 有一個(gè)四段指令流水線為取指 IF 譯碼 ID 執(zhí)行 EX 寫回 WB 分支指令在第二個(gè)時(shí) 鐘周期未決定是不是條件失敗分支 在第三個(gè)時(shí)鐘周期未決定是不是成功分支 還假定第一個(gè)時(shí) 鐘周期的操作和條件分支無關(guān) 并略去其它流水線停頓 要求 1 分別畫出無條件分支 發(fā)生的條件分支 不發(fā)生的條件分支時(shí)指令執(zhí)行的時(shí)空圖 2 假設(shè)條件分支指令占所有指令的 20 且其中 60 指令可能執(zhí)行 無條件分支占 5 問實(shí)際的 流水線加速比是多少 解 1 根據(jù)題意 分支指令采用的是流水線停頓的方法來處理 而判斷條件分支指令讓流水線停 頓 應(yīng)在取指功能段后設(shè)計(jì)一個(gè) 指令分析器 來判斷流水線是否停頓 顯然 無條件分支指令與條件 成功 發(fā)生條件 分支是一樣的 需要在第三個(gè)時(shí)鐘周期未決定下一條指令的地址 因此流水線要停頓 二個(gè)時(shí)鐘周期 對于條件失敗 條件不成功 分支 需要在第二個(gè)時(shí)鐘周期未決定下一條指令的地址 因此流水線要停頓一個(gè)時(shí)鐘周期 2 串行執(zhí)行 N 條指令的時(shí)間為 T1 N k t 流水線方式執(zhí)行 N 條指令的時(shí)間為 Tn k 1 t N N 5 2 N 20 60 1 5 t Sn T1 Tn k 1 28 3 13 用一條 5 個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算 F 每個(gè)功能段的延遲時(shí)間 每個(gè)功能段的延 10 1 i Ai 遲時(shí)間均相等 流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路 而且設(shè)置有足夠的緩沖寄存器 要求用盡可能短的時(shí)間完成計(jì)算 畫出流水線時(shí)空圖 計(jì)算流水線的實(shí)際吞吐率 加速比和效率 解 為使計(jì)算過程充分利用流水線的性能 避免 先寫后讀 相關(guān) 需要將計(jì)算的算法改為 A1 A2 A3 A4 A9 A10 A5 A6 A7 A9 且按括號的優(yōu)先次序計(jì)算九次加法 相應(yīng)的流水線時(shí)空圖如下圖所示 空間 S5 1 2 3 4 5 6 7 8 9 S4 1 2 3 4 5 6 7 8 9 S3 1 2 3 4 5 6 7 8 9 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 時(shí)間 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 TP 9 21 t 0 429 t S T0 TK 9 5 t 21 t 2 143 E 5 9 t 5 21 t 0 429 3 15 有一條 3 個(gè)功能段的流水線如下圖所示 每個(gè)功能段的延遲時(shí)間均為 t 但是 功能段 S2的輸出 要返回到它自己的輸入端循環(huán)執(zhí)行一次 輸入 輸出 t t t 1 如果每隔一個(gè) t 向流水線連續(xù)輸入任務(wù) 這條流水線會發(fā)生什么問題 2 求這條流水線能夠正常工作的實(shí)際吞吐率 加速比和效率 3 可用什么辦法來提高流水線的吞吐率 畫出改進(jìn)后的流水線結(jié)構(gòu) S1S2S3 解 1 每個(gè)任務(wù)在段 S2要反饋循環(huán)一次 執(zhí)行時(shí)間為 2 t 其它各段的執(zhí)行時(shí)間為 t 因此應(yīng) 按瓶頸段的執(zhí)行時(shí)間 2 t 流入任務(wù) 才不會發(fā)生沖突現(xiàn)象 否則會發(fā)生流水線的阻塞 2 若連續(xù)輸入 n 個(gè)任務(wù) 則流水線的實(shí)際吞吐率 加速比和效率分別為 TP n 4 t 2 n 1 t n 2 n 1 t S 4n t 4 t 2 n 1 t 2n n 1 E 4n t 3 4 t 2 n 1 t 2n 3 n 1 3 為提高流水線的吞吐率 可重復(fù)設(shè)置段 S2 并使兩個(gè)段 S2串連在一起 從而消除瓶頸段 S2 而且各段執(zhí)行時(shí)間相等為 t 流水線的段數(shù)為 4 流水線的結(jié)構(gòu)如下圖所示 輸入 輸出 t t t t 3 16 在一個(gè) 5 段的流水線處理機(jī)上需經(jīng) 9 t 才能完成一個(gè)任務(wù) 其預(yù)約表為 1 寫出流水線的初始沖突向量 2 畫出流水線任務(wù)調(diào)度的狀態(tài)有向圖 3 求出流水線的最優(yōu)調(diào)度策略及最小平均延遲時(shí)間和流水線的最大吞吐率 4 按最優(yōu)調(diào)度策略連續(xù)輸入 8 個(gè)任務(wù)時(shí) 流水線的實(shí)際吞吐率是多少 解 1 根據(jù)初始沖突向量的構(gòu)成方法 對預(yù)約表各行中打 的拍數(shù)求出差值 除去重復(fù)的后匯集 在一起 即得到延遲禁止表為 F 1 5 6 8 由 F 可得到初始沖突向量為 C 2 根據(jù)后繼沖突向量的遞推規(guī)則 Cj SHR k Ci C0則可得出所有的后繼狀態(tài) 具體有 C0四個(gè)后繼狀態(tài) C1 SHR 2 C0 C0 7 C2 SHR 3 C0 C0 C3 SHR 4 C0 C0 3 2 C4 SHR 7 C0 C0 C0 7 4 7 C1二個(gè)后繼狀態(tài) C5 SHR 2 C1 C0 C6 SHR 7 C1 C0 C0 7 C2二個(gè)后繼狀態(tài) C7 SHR 4 C2 C0 C3 3 4 7 2 C8 SHR 7 C2 C0 C0 C3二個(gè)后繼狀態(tài) C9 SHR 3 C3 C0 C2 時(shí)間 1 2 3 4 5 6 7 8 9 流水段 S1 S2 S3 S4 S5 延遲 D2 S1S2 S3S2 C0 C2 C1 C3 C5 C10 SHR 7 C3 C0 C0 C5一個(gè)后繼狀態(tài) C11 SHR 7 C5 C0 C0 由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示 3 由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間 如下表所示 調(diào)度策略 平均延遲時(shí)間 特別地 從 C0出發(fā)的 3 4 3 也是一個(gè) 2 2 7 2 2 7 t 3 3 67 t 任務(wù)調(diào)度策略 除第一條有向弧外 第二 三條 2 7 2 7 t 2 4 5 t 有向組成一個(gè)環(huán)路 該調(diào)度策略為 4 3 從 表 3 4 7 3 4 7 t 3 4 67 t 中可以得到平均延遲時(shí)間最小的調(diào)度策略為 4 3 7 3 7 t 2 5 t 3 該調(diào)度策略則為最優(yōu)調(diào)度策略 相應(yīng)的最小 4 3 7 4 3 7 t 3 4 67 t 平均延遲時(shí)間為 3 5 t 所以流水線的最大吞吐 4 7 4 7 t 2 5 5 t 率為 7 7 t TPmax 1 3 5 t 0 286 t 3 4 3 4 3 t 2 3 5 t 4 按最優(yōu)調(diào)度策略 3 4 3 連續(xù)輸入 8 個(gè)任務(wù)時(shí) 流水線的實(shí)際吞吐率為 TP 8 3 4 3 4 3 4 3 9 t 0 24 t 3 17 有一個(gè) 5 段流水線的預(yù)約表如下 1 畫出流水線調(diào)度狀態(tài)有向圖 2 分別求出允許不等間隔調(diào)度和等間隔調(diào)度的最優(yōu)調(diào)度策略以及這兩種調(diào)度策略的最大吞吐率 3 若連續(xù)輸入 10 個(gè)任務(wù) 求這兩種調(diào)度策略的實(shí)際吞吐率 解 1 根據(jù)初始沖突向量的構(gòu)成方法 對預(yù)約表各行中打 的拍數(shù)求出差值 除去重復(fù)的后匯集 在一起 即得到延遲禁止表為 F 1 3 6 由 F 可得到初始沖突向量為 C0 根據(jù)后繼沖突向量的遞推規(guī)則 Cj SHR k Ci C0則可得出所有的后繼狀態(tài) 具體有 C0三個(gè)后繼狀態(tài) C1 SHR 2 C0 C0 5 C2 SHR 4 C0 C0 C3 SHR 5 C0 C0 C0 4 2 5 5 C1二個(gè)后繼狀態(tài) C4 SHR 2 C1 C0 C5 SHR 5 C1 C0 C0 5 C2二個(gè)后繼狀態(tài) C6 SHR 4 C2 C0 C2 4 2 時(shí)間 1 2 3 4 5 6 7 流水段 S1 S2 S3 S4 S5 C0 C2 C1 C7 SHR 5 C2 C0 C0 C4一個(gè)后繼狀態(tài) C8 SHR 5 C4 C0 C0 由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示 2 由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間 如下表所示 調(diào)度策略 平均延遲時(shí)間 特別地 從 C0出發(fā)的 4 4 也是一個(gè)任 務(wù) 2 5 2 5 t 2 3 5 t 調(diào)度策略 除第一條有向弧外 第二條有向弧是 一 4 5 4 5 t 2 4 5 t 個(gè)環(huán)路 該調(diào)度策略為 4 從表中可以得到平 均 5 5 t 延遲時(shí)間最小的等間隔和不等間隔的調(diào)度策略為 2 2 5 2 2 5 t 3 3 t 4 4 和 2 2 5 相應(yīng)的最小平均延遲時(shí) 4 4 4 t 間為 4 t 和 3 t 所以流水線的最大吞吐率為 TPAmax 1 4 t 0 25 t TPBmax 1 3 t 0 33 t 3 按等間隔最優(yōu)調(diào)度策略 4 4 連續(xù)輸入 10 個(gè)任務(wù)時(shí) 流水線的實(shí)際吞吐率為 TP 10 4 4 4 4 4 4 4 4 4 7 t 10 43 t 按不等間隔最優(yōu)調(diào)度策略 2 2 5 連續(xù)輸入 10 個(gè)任務(wù)時(shí) 流水線的實(shí)際吞吐率為 TP 10 2 2 5 2 2 5 2 2 5 7 t 5 17 t 第第 四四 章章 習(xí)習(xí) 題題 4 13 由 3 個(gè)訪問速度 存儲容量和每位價(jià)格都不相同的存儲器構(gòu)成一個(gè)存儲系統(tǒng) 3 個(gè)存儲器 M1 M2 和 M3 的訪問周期分別為 R1 R2 和 R3 存儲容量分別為 Sl S2 和 S3 每位價(jià)格分別為 C1 C2 和 C3 Ml 靠近 CPU 1 寫出這個(gè)三級存儲系統(tǒng)的等效訪問時(shí)間 等效存儲容量 S 和等效每位價(jià)格 C 的表達(dá)式 2 在什么條件下 整個(gè)存儲系統(tǒng)的每位平均價(jià)格接近于 C3 解 1 設(shè) Hi為 CPU 訪存在 Mi中的概率 則存儲系統(tǒng)的等效訪問時(shí)間 存儲容量和每位價(jià)格分別 為 T S