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

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