《計算機系統結構》總復習-習題[稻香書屋]

《《計算機系統結構》總復習-習題[稻香書屋]》由會員分享，可在線閱讀，更多相關《《計算機系統結構》總復習-習題[稻香書屋]（103頁珍藏版）》請在裝配圖網上搜索。

1、總復習1學習幻燈第一章第一章 基本概念（基本概念（P1P1）本章介紹計算機系統結構的一些基本知識。包括定性知識和定量知識兩大組內容。為了便于學習，本章各節重新編號，與教材編號不同。定量知識：對計算機性能進行定量評價的幾個重要公式。2學習幻燈本章重點本章重點 本章從定性知識和定量知識兩個方面介紹計算機系統結構的基本概念。有關重點如下：(1)Amdahl定律；(2)平均周期數CPI公式，程序執行時間Te公式；(3)每秒百萬指令數MIPS公式，每秒百萬浮點數MFLOPS公式。3學習幻燈1.定量知識3個性能公式1.1 AmdahlAmdahl定律定律（加快經常性事件原理，P9）其中：Sn 全局加速比；

2、To 原執行時間（old）；Tn 新執行時間（new）；Se 被改進部分的局部加速比；Fe 被改進部分原執行時間占原來總時間的百分比。4學習幻燈Amdahl定律的推導5學習幻燈Amdahl定律的圖形 從圖1.2可以看出，增大Se和Fe對Sn都有提升作用；但當Fe固定時，一味增大Se對Sn的作用會越來越不顯著。6學習幻燈作作1.12 假定利用增加向量模塊來提高計算機的運假定利用增加向量模塊來提高計算機的運算速度。計算機處理向量的速度比其通常的運算速度。計算機處理向量的速度比其通常的運算要快算要快20倍，將可用向量處理部分所花費的時倍，將可用向量處理部分所花費的時間占總時間的百分比稱為可向量化百分

3、比。間占總時間的百分比稱為可向量化百分比。（1）求出加速比）求出加速比S和向量化百分比之間的關系式和向量化百分比之間的關系式作作1.13（2）當要得到加速比為當要得到加速比為2時的可向量化百時的可向量化百分比分比F為多少？為多少？作作1.14 （3）為了獲得在向量模式所得到的最大加為了獲得在向量模式所得到的最大加速比的一半，可向量化百分比速比的一半，可向量化百分比F為多少？為多少？7學習幻燈(2)由（1）式有解（1）：由Amdahl定律知FFFS*192020)20/()1(153.01910)20/()1(12FFF(1)8學習幻燈(3)由題意可知95.01918)20/()1(110FFF

4、9學習幻燈作作1.17 假設高速緩存假設高速緩存Cache工作速度為主存的工作速度為主存的5倍，倍，且且Cache被訪問命中的概率為被訪問命中的概率為90，則采用，則采用Cache后后，能使整個存儲系統獲得多高的加速比？，能使整個存儲系統獲得多高的加速比？57.328.015/9.0)9.01(1oePTTS解：解：fe=0.9，re=510學習幻燈1.2 CPI與程序執行時間Te（P11）CPI是衡量CPU執行指令效率的重要指標。讓我們先考慮一個標準測速程序的全部執行時間Te和其中所有第i種指令的累計時間Ti，易知11學習幻燈1.3 每秒百萬指令數MIPS與每秒百萬浮點數MFLOPS（P11

5、）例題：P10，例1.1例1.5。P33，題12，題13，題14。12學習幻燈 例例1.191.19 用一臺用一臺4OMHz4OMHz處理機執行標準測試程序，處理機執行標準測試程序，它含的混合指令數和相應所需的時鐘周期數如它含的混合指令數和相應所需的時鐘周期數如下：下：指令類型指令類型 指令條數 時鐘周期數時鐘周期數 整數運算整數運算 4500045000 1 數據傳送數據傳送 32000 232000 2 浮點運算浮點運算 15000 215000 2 控制傳送控制傳送 8000 28000 2 求有效求有效CPICPI、MIPSMIPS速率和程序的執行時間。速率和程序的執行時間。13學習幻

6、燈 解：依題意可知 IN=105條，n=455.1)08.0215.0232.0245.01()(411iniNiiIICPICPI8.251055.1104010666CPIfMIPSC)(875.31040/155.11065msTCPIITCNCPU14學習幻燈作作1.201.20 某工作站采用時鐘頻率為某工作站采用時鐘頻率為15MHz15MHz、處理速率為、處理速率為10MIPS10MIPS的處理機來執行一個巳知混合程序。假定每次的處理機來執行一個巳知混合程序。假定每次存儲器存取為存儲器存取為1 1周期延遲、試問：周期延遲、試問：(1)(1)此計算機的有效此計算機的有效CPICPI是多

7、少是多少?(2)(2)假定將處理機的時鐘提高到假定將處理機的時鐘提高到30MHz30MHz，但存儲器子，但存儲器子 系統速率不變。這樣，每次存儲器存取需要兩個時鐘系統速率不變。這樣，每次存儲器存取需要兩個時鐘 周期。如果周期。如果3030指令每條只需要一次存儲存取，而另指令每條只需要一次存儲存取，而另 外外5 5每條需要兩次存儲存取，還假定已知混合程序每條需要兩次存儲存取，還假定已知混合程序 的指令數不變，并與原工作站兼容，試求改進后的處的指令數不變，并與原工作站兼容，試求改進后的處 理機性能。理機性能。解解 (1)5.11010101510666MIPSfCPIoldold15學習幻燈(2)

8、依題意可知：依題意可知：30%的指令需要一次存儲存取，則的指令需要一次存儲存取，則這些指令在處理器提高時鐘頻率之后需要增加這些指令在處理器提高時鐘頻率之后需要增加1個時個時鐘周期；另外鐘周期；另外5%的指令需要增加的指令需要增加2個時鐘周期。個時鐘周期。改進后性能提高情況可用改進后性能提高情況可用CPU時間之比表示：時間之比表示：9.12%51%30oldnewCPICPI79.15109.1103010666newnewnewCPIfMIPS58.1/)()(newNnewoldNoldnewCPUoldCPUfICPIfICPITT16學習幻燈作作1.21 1.21 假設在一臺假設在一臺4

9、0MHz40MHz處理機上運行處理機上運行200 000200 000條條指令的目標代碼，程序主要由四種指令組成。根據指令的目標代碼，程序主要由四種指令組成。根據程序跟蹤實驗結果，已知指令混合比和每種指令所程序跟蹤實驗結果，已知指令混合比和每種指令所需的指令數如下：需的指令數如下：指令類型指令類型CPI指令混合百分比算術和邏輯運算算術和邏輯運算160%CacheCache命中的加載命中的加載/存儲存儲 218%轉移轉移 412%CacheCache失效時訪問主存失效時訪問主存810%(1)(1)計算在單處理機上用上述蹤數據運行程序的平均計算在單處理機上用上述蹤數據運行程序的平均CPICPI(2

10、)(2)根據根據(1)(1)所得所得CPICPI，計算相應的，計算相應的MIPS MIPS 速率和程序的執行時間速率和程序的執行時間17學習幻燈 解：依題意可知 IN=2105條，n=4，24.2)1.0812.0418.026.01()(411iniNiiIICPICPI86.17102.2104010666CPIfMIPSC)(2.111024.210264015msTCPIITCNCPU18學習幻燈第二章第二章 指令系統（指令系統（P36P36）本章介紹指令系統設計中2個最基本的內容：數據表示、操作碼優化。本章重點本章重點 (1)Huffman編碼方法；(2)等長擴展編碼方法（15/15

11、/15法，8/64/512法）；(3)編碼方法性能指標（平均碼長L，信息冗余量R）。19學習幻燈2.1 Huffman壓縮編碼（P91）(1)Huffman壓縮概念（最佳編碼定理）：當用n個長度不等的代碼分別代表n種發生概率不等的事件時，按照短代碼給高概率事件、把長代碼給低概率事件的原則分配，可使平均碼長達到最低。(2)Huffman編碼方法 這種編碼方法由兩個過程組成。頻度合并：將全部n個事件（在此即為n條指令）的頻度值排序，選取其中最小的2個頻度合并，然后將剩下的n-1個頻度再次排序，再合并最小的2個頻度，如此重復，直至剩下1個頻度為止。記錄所有的合并關系，形成一棵二叉樹 Huffman樹

12、，所有原始頻度值充當樹葉，而最后剩下的總頻度1為樹根；碼元分配：從樹根開始，對每個中間結點的左右2個分支邊各賦予一位代碼“0”和“1”（“0”在哪一側不限）。讀出從根結點到任一片樹葉的路徑上依次出現的代碼位就排成了這個事件（即指令）的完整編碼。由于頻度高的事件較晚被合并，它的編碼位數也就較少，符合Huffman壓縮原則。上面所說的頻度值就是各事件實際出現次數的百分比，它是理論出現概率的近似值。20學習幻燈 平均碼長平均碼長：各事件編碼長度的數學期望。信息冗余量信息冗余量：它表明消息編碼中“無用成分”所占的百分比。21學習幻燈2.2 擴展編碼方法（擴展編碼方法（等長擴展法，P94-95）用碼長表

13、示：例如4-8-12法。這并不能說明具體編碼方法，例如下面兩種編碼方法都是4-8-12法。用碼點數表示：例如15/15/15法，8/64/512法15/15/15法，每一種碼長都有4位可編碼位（前頭可以有相同的擴展標識前綴），可產生16個碼點（即編碼組合），但是至多只能使用其中15個來表示事件，留下1個或多個碼點組合作為更長代碼的擴展標識前綴。已經用來表示事件的碼點組合不能再作為其它更長代碼的前導部分，否則接收者會混淆。這就是“非前綴原則”。8/64/512法，每一種碼長按4位分段，每一段中至少要留下1位或多位作為擴展標識。各段剩下的可編碼位一起編碼，所產生的碼點用來對應被編碼事件。每一段中的

14、標識位指出后面還有沒有后續段。22學習幻燈10000001110.090.300.601.000.1510.0610.030.030.040.050.150.300.4023學習幻燈由此可得到哈夫曼編碼如下：由此可得到哈夫曼編碼如下：I1:0 I2:10 I3:110 I4:11100 I1:0 I2:10 I3:110 I4:11100 I5:11101 I6:11110 I7:11111 I5:11101 I6:11110 I7:11111 平均碼長平均碼長L L=0.4=0.4*1+0.31+0.3*2+0.152+0.15*3+0.053+0.05*5+0.045+0.04*5 5+0

15、.03+0.03*5+0.035+0.03*5=2.205=2.20位位 信息冗余量信息冗余量R=(2.20-2.17)/2.20=1.36%R=(2.20-2.17)/2.20=1.36%指令長度個數指令長度個數=4=424學習幻燈2.2.擴展哈夫曼編碼擴展哈夫曼編碼 I1,I2,I3 I1,I2,I3 用兩位用兩位:00,01,10:00,01,10 I4,I5,I6,I7 I4,I5,I6,I7 用四位用四位:1100,1101,1110,:1100,1101,1110,11111111L L=(0.4+0.3+0.15)=(0.4+0.3+0.15)*2+(0.05+0.04+0.03

16、+0.03)2+(0.05+0.04+0.03+0.03)*4 4=2.30=2.30位位信息冗余量信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%=(2.30-2.20)/2.30=0.0565=5.65%25學習幻燈41 1 1 151 1 1 1 10.03I741 1 1 051 1 1 1 00.03I641 1 0 151 1 1 0 10.04I541 1 0 051 1 1 0 00.05I421 031 1 00.15I320 1 2 1 00.30I220 0100.40I1OP長度長度lihuffman擴展編擴展編碼碼OP長長度度li操作碼操作碼OP

17、使用哈夫曼使用哈夫曼編碼編碼 頻頻 度度（Pi）指指 令令操作碼的擴展（等長擴展）操作碼的擴展（等長擴展）平均碼長：2.2 2.326學習幻燈作 2.13 采用最優Huffman編碼法（信息熵）的操作碼最短平均長度為：27學習幻燈28學習幻燈例例2.22.2 指令系統共有指令系統共有4242種指令，前種指令，前1515種使用頻率平均種使用頻率平均為為0.050.05，中間，中間1313種使用頻率平均為種使用頻率平均為0.0150.015，最后，最后1414種種使用頻率平均為使用頻率平均為0.0040.004。如何編碼？。如何編碼？00000000 ：1515種種111011101111 000

18、01111 0000 ：1515種種1111 11101111 11101111 1111 00001111 1111 0000 ：1515種種1111 1111 11101111 1111 1110解：解：因頻率分布有三種，故因頻率分布有三種，故碼長可有三種；碼長可有三種；因每段指令數基本相同，因每段指令數基本相同，故可采用故可采用等長擴展等長擴展(4-8-12(4-8-12位位)，保留特征碼的每段指令保留特征碼的每段指令數相同數相同(15-15-15)(15-15-15)方法。結方法。結果如圖所示；果如圖所示；結果：采用結果：采用15-15-1515-15-15擴展方法，最后一種編碼用于擴

19、展方法，最后一種編碼用于擴展，每段擴展，每段0000000011101110用于編碼，用于編碼，11111111用于擴展。用于擴展。29學習幻燈例例2.32.3 某模型機有某模型機有9 9條指令，其使用頻率為：條指令，其使用頻率為：ADDADD（加）（加）30%30%SUBSUB（減）（減）24%24%JOMJOM（按負轉移）（按負轉移）6%6%STOSTO（存）（存）7%7%JMPJMP（轉移）（轉移）7%7%SHRSHR（右移）（右移）2%2%CILCIL（循環左移）（循環左移）3%3%CLACLA（清加）（清加）20%20%STPSTP（停機）（停機）1%1%要求有兩種指令字長，都按雙操

20、作數指令格式編要求有兩種指令字長，都按雙操作數指令格式編,采用擴展操作碼，并限制只能有兩種操作碼碼長。設采用擴展操作碼，并限制只能有兩種操作碼碼長。設該機有若干個通用寄存器，主存為該機有若干個通用寄存器，主存為1616位寬，按字節編位寬，按字節編址，采用整數邊界存貯，任何指令都在一個主存周期址，采用整數邊界存貯，任何指令都在一個主存周期中取得，短指令為寄存器寄存器型，長指令為寄存中取得，短指令為寄存器寄存器型，長指令為寄存器主存型，主存地址應能變址尋址。器主存型，主存地址應能變址尋址。30學習幻燈 解：解：(1)Huffman樹的形式如圖所示。樹的形式如圖所示。0.010.020.03010.

21、030.06010.060.12010.070.070.14010.260100.300.200.240.44010.561001131學習幻燈 由上圖可得到的由上圖可得到的Huffman編碼為：編碼為：ADD(ADD(加加)30%01)30%01 SUB(SUB(減減)24%11)24%11 CLA(CLA(清加清加)20%10)20%10 JOM(JOM(按負轉移按負轉移)6%0001)6%0001 STO(STO(存存)7%0011)7%0011 JMP(JMP(轉移轉移)7%0010)7%0010 CIL(CIL(循環左移循環左移)3%00001)3%00001 SHR(SHR(右移右

22、移)2%000001 )2%000001 STP(STP(停機停機)1%000000)1%000000因此，操作碼的平均碼長為：因此，操作碼的平均碼長為：位61.291iiilpl32學習幻燈(2)采用采用2-5擴展的操作碼編碼為：擴展的操作碼編碼為：ADD(ADD(加加)30%00)30%00 SUB(SUB(減減)24%01)24%01 CLA(CLA(清加清加)20%10)20%10 JOM(JOM(按負轉移按負轉移)6%11000)6%11000 STO(STO(存存)7%11001)7%11001 JMP(JMP(轉移轉移)7%11010)7%11010 SHR(SHR(右移右移)2

23、%11011 )2%11011 CIL(CIL(循環左移循環左移)3%11100)3%11100 STP(STP(停機停機)1%11101)1%11101因此，操作碼的平均碼長為：因此，操作碼的平均碼長為：位78.2526.02)20.024.030.0(91iiilp33學習幻燈(3)該機允許使用的可編址的通用寄存器個數為該機允許使用的可編址的通用寄存器個數為23=8個個(4)短指令為寄存器短指令為寄存器-寄存器型，格式如下：寄存器型，格式如下：OP(2位位)R1(3位位)R2(3位位)OP(5位位)R1(3位位)X(2位位)相對位移相對位移d(6位位)(5)訪主存操作數地址尋址的最大相對位

24、移量為訪主存操作數地址尋址的最大相對位移量為64個字節個字節(-32+31個字節個字節)長指令為寄存器長指令為寄存器-主存型，格式如下：主存型，格式如下：34學習幻燈 作2.14 一臺模型機共有7條指令，各指令的使用頻度分別是35、25、20、10、5、3、2，有8個通用數據寄存器，2個變址寄存器。(1)要求操作碼的平均長度最短，請設計操作碼的編碼，并計算所設計操作碼的平均長度。(2)設計8位字長的寄存器寄存器型指令3條，16位字長的寄存器存儲器型變址尋址方式指令4條，變址范圍不小于正、負127。請設計指令格式，并給出各字段的長度和操作碼的編碼。35學習幻燈答:(1)要使得到的操作碼長度最短，

25、應采用Huffman編碼，Huffman樹構造如下36學習幻燈由此可以得到7條指令的編碼分別如下：這樣，Huffman編碼法得到的操作碼的平均長度為：l =2(0.35+0.25+0.20)+30.10+4 0.05+5(0.03+0.02)=1.6+0.3+0.2+0.25=2.35指令號 出現的頻率編碼135%00225%01320%10410%11055%111063%1111072%1111137學習幻燈38學習幻燈作2.14(改）一臺模擬機共有7條指令，各指令的使用頻度分別為35%，25%，20%，10%，5%，3%，2%。該模擬機有8位和16位兩種指令長，采用2-4擴展操作碼，8位

26、字長指令為寄存器-寄存器（R-R）二地址類型，16位字長指令為寄存器-存貯器（R-M）二地址變址尋址（-128變址范圍127）類型。(1)計算操作碼的平均碼長 (2)該機允許使用多少個可編址的通用寄存器，多少個變址寄存器？設計該機的兩種指令格式，標出各字段位數并給出操作碼編碼。39學習幻燈 擴展碼有2種方案（下圖）00 00013條 01 2條10 10001100 10011101 4條 10105條1110 10111111 1100(3-7型）（2-8 型）簡版40學習幻燈 2-4擴展碼有2種方案（上圖）前一種方案里短指令占的比例較大，應該選用它。平均碼長/L=(0.35+0.25+0.

27、20)2+(0.1+0.05+0.03+0.02)4=2.4 用R代表寄存器編號，A代表變址偏移量。題目未指明R-R型R-M型誰是短碼，所以先列出2種方案：41學習幻燈8 位:操作碼 2,寄存器（8-2)/2=3 （右邊為 操作碼4 位）16位：操作碼 2,寄存器 3，變址尋址（-128變址范圍127）：27=128，符號1位，共 8位，變址器：16-4-3-8=142學習幻燈 2.2.2 操作數優化尋址方式比較（P95）指令中操作數占用的位數由操作數的個數與尋址方式決定。按操作數的個數劃分，有零操作數指令、一操作數指令、二操作數指令、三操作數指令共四種形式。應該按機器用途來選擇（P99，表2

28、.20）?？s短操作數長度的常用方法是間址和變址（P99頁末）。43學習幻燈作作2.152.15 某處理機的指令字長為某處理機的指令字長為1616位，有雙地址位，有雙地址指令、單地址指令和零地址指令三類，并假設每指令、單地址指令和零地址指令三類，并假設每個地址字段的長度個地址字段的長度為為6 6位。位。（1 1）如果雙地址指令有）如果雙地址指令有1515條，單地址和零地址條，單地址和零地址指令的條數基本相同，問單地址指令和零地址指指令的條數基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。令各有多少條？并且為這三類指令分配操作碼。（2 2）如果三類指令的比例為）如果三類指

29、令的比例為1 1：9 9：9 9，問雙地址，問雙地址指令、單地址指令和零地址指令各有多少條？并指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。且為這三類指令分配操作碼。44學習幻燈45學習幻燈解解：（1 1）雙地址指令）雙地址指令1515條，條，地址碼：地址碼：0000000011101110 單地址指令單地址指令2 26 61 16363條，地址碼：條，地址碼：1111 0000001111 000000 1111 111110 1111 111110零地址指令零地址指令6464條，地址碼：條，地址碼：1111 111111 0000001111 111111 00000

30、0 1111 111111 111111 1111 111111 11111146學習幻燈47學習幻燈第三章第三章 存儲系統（存儲系統（P130P130）長期存在的問題：在合理的總價格限制下，單純性主存設備的速度跟不上CPU的發展，容量不能滿足軟件尺寸擴大。本章學習兩種提高主存系統性能/價格比的結構化方法：并行存儲器與存儲層次技術。后者為主。48學習幻燈 例例3.1 假設高速緩存假設高速緩存Cache工作速度為主存工作速度為主存的的5倍，且倍，且Cache被訪問命中的概率為被訪問命中的概率為90，則采用則采用Cache后，能使整個存儲系統獲得多后，能使整個存儲系統獲得多高的加速比？高的加速比？

31、解：解：57.351.09.05)1(52112AAAAApTHHTTTTS49學習幻燈l例例3.2 假設高速緩存假設高速緩存Cache的訪問周期為的訪問周期為50ns，主存的訪問周期為，主存的訪問周期為400ns，且，且Cache被訪問命中的概率為被訪問命中的概率為95，則采用，則采用Cache后后，能使整個存儲系統等效的訪問周期為多，能使整個存儲系統等效的訪問周期為多少？獲得多高的加速比？少？獲得多高的加速比？解：解：9.55.674002AApTTSnsTHHTTAAA5.6740005.05095.0)1(2150學習幻燈第四章第四章 輸入輸出系統（輸入輸出系統（P208）輸入輸出系統

32、輸入輸出系統是計算機系統中實現各種輸入輸出任務的資源總稱。它包括各種輸入輸出設備、相關的管理軟件等等。由于輸入輸出設備的特殊工作性質使其數據吞吐率通常遠低于主機，設計輸入輸出系統就是要建立數據交換的最佳方案，使雙方都能高效率地工作。本章重點是中斷優先級管理、通道流量設計。51學習幻燈4.1 基本輸入輸出方式(P212)4.1.1 程序控制I/O方式4.1.2 中斷I/O方式4.1.3 DMA方式4.1.4 通道方式4.1.5 I/O處理機方式52學習幻燈4.2 中斷優先級管理(P219)中斷是為實時任務優先獲得處理機資源而采用的一種調度技術，當系統中存在多個中斷源時必須根據實時性強弱設定優先順

33、序，這也被稱為中斷的分級。為了兼顧中斷響應的時效與配置的靈活，通常采用兩套機制結合組成中斷優先序管理體系。(1)硬件響應優先序：未被屏蔽的幾個中斷源同時提出申請時，CPU選擇服務對象的順序。它由硬件電路實現，用戶不能修改。如P226圖4.11所示。(2)軟件服務優先序：在各中斷服務程序開頭，用軟件設置自己的中斷屏蔽字（在主程序中也設置）。以此改變實際服務順序(P230)。例如某個硬件響應優先級高的中斷源，其中斷服務程序執行中屏蔽了自身，而開放了某個硬件響應優先級比它低的中斷源，后者就可以在前者剛開放中斷時就打斷它，從而在實際上先得到服務。中斷服務過程示意圖如P231圖4.14所示。由于常規用戶

34、主程序對處理機的需求緊迫性最低，所以它的中斷屏蔽字是“全部開放”。(3)實例分析：屏蔽字表、中斷服務過程圖。例4.1（P230倒數第8行開始）53學習幻燈作業4.5 已知中斷服務請求次序為 1-2-3-4，現改為3-2-4-1，（1）設計中斷屏蔽碼（2）處理機運行主程序時，同時D1和D2q請求中斷，而在運行中斷源D2時，D3和D4又同時請求，請畫出程序運行過程示意圖解：(1)中斷屏蔽字表如下圖；(令1對應屏蔽，0對應開放)54學習幻燈(2)中斷過程示意圖如下圖。55學習幻燈例例 4.1 4.1 設中斷級屏蔽位為設中斷級屏蔽位為“0”0”對應于開放，對應于開放，1 1對應于屏蔽，各級中斷處理程對

35、應于屏蔽，各級中斷處理程序的中斷級屏蔽位設置如下：序的中斷級屏蔽位設置如下：(1)(1)當中斷響應的優先次序為當中斷響應的優先次序為1 1、2 2、3 3、4 4，其中斷處理次序是什么？，其中斷處理次序是什么？(2)(2)所有的中斷處理各需要所有的中斷處理各需要3 3個單位時間，當正在運行用戶程序時，同時出個單位時間，當正在運行用戶程序時，同時出現第現第2 2、3 3級中斷請求，過級中斷請求，過2 2個單位時間，又同時出現第個單位時間，又同時出現第1 1、4 4級中斷請求，請畫級中斷請求，請畫出程序運行過程示意圖。出程序運行過程示意圖。中斷處理中斷處理程序級別程序級別中斷級屏蔽位中斷級屏蔽位第

36、第1 1級級第第2 2級級第第3 3級級第第4 4級級1 1級級2 2級級3 3級級4 4級級1 11 11 11 11 10 00 01 11 11 10 00 00 01 11 10 056學習幻燈【解答解答】(1)(1)當中斷響應的優先次序為當中斷響應的優先次序為1 1、2 2、3 3、4 4，其中斷處理次序是，其中斷處理次序是1 1、3 3、4 4、2 2。(2)(2)運行過程示意圖如下：運行過程示意圖如下：用戶程序用戶程序中中 斷斷 處處 理理 程程 序序中斷中斷請求請求t4112343257學習幻燈4.3 通道處理機(P233)(1)定義：通道處理機（簡稱通道）是隸屬于主處理機的輸

37、入輸出專用協處理機。(2)特點：有一套輸入輸出功能很強的專用指令系統；與主處理機共享主存，存放相應的程序和數據；一個通道可以連接多臺外部設備；主處理機可用啟動I/O指令來啟動一個通道；當通道訪存與主處理機沖突時，存控部件賦予通道較高的優先權；通道程序執行完畢自動轉入休眠狀態，同時向主處理機發出一個特定的中斷申請，通知該事件。(3)地位：從屬于主處理機。58學習幻燈 字節多路通道：以字節為單位交叉為多臺設備傳輸。子通道的概念。選擇通道：完成一臺設備的全部傳輸再去為另一臺設備服務。數組多路通道：以數組為單位交叉為多臺設備傳輸。(5)通道傳輸過程的時間分配(P241，其中P是設備臺數)：字節多路通道

38、：，其中n是單臺設備的數據傳輸量；選擇通道：數組多路通道：，其中k是塊尺寸，。(4)分類(P238)：59學習幻燈(6)通道流量分析(P243)：通道最大能力流量：60學習幻燈 通道實際最大負荷流量：通道正常工作條件：61學習幻燈 實例分析：通道時間關系圖P243 例 4.1 倒數第2行開始62學習幻燈(1)(1)在上表中填出設備相應二次請求傳送字節的間隔在上表中填出設備相應二次請求傳送字節的間隔時間。時間。(2)(2)當所有設備同時要傳送數據時，求其對通道要求當所有設備同時要傳送數據時，求其對通道要求的總流量的總流量f fbytebyte設備號設備號1 12 23 34 45 56 6傳送速

39、率傳送速率(B/ms)(B/ms)505050504040252525251010二次請求的二次請求的間隔時間間隔時間(S)(S)例例4.1 4.1 某字節交叉多路通道連接某字節交叉多路通道連接6 6臺設備，其數據臺設備，其數據傳送速率如下表所示。傳送速率如下表所示。63學習幻燈(3)(3)讓通道以極限流量讓通道以極限流量f fmax.bytemax.byte=f=fbytebyte的工作周期工的工作周期工作，通道的工作周期作，通道的工作周期(即即TS+TDTS+TD的時間間隔的時間間隔)是是多少？多少？(4)(4)讓通道中所掛設備速率越高的數據傳送請求被讓通道中所掛設備速率越高的數據傳送請求

40、被響應的優先級越高。畫出響應的優先級越高。畫出6 6臺設備同時發送請臺設備同時發送請求到下次同時發送請求期間里，通道響應和求到下次同時發送請求期間里，通道響應和處理完各設備請求時刻的示意圖。哪個設備處理完各設備請求時刻的示意圖。哪個設備丟失了信息？提出一種不丟失信息的解決辦丟失了信息？提出一種不丟失信息的解決辦法法。64學習幻燈設備號設備號1 12 23 34 45 56 6傳送速率傳送速率(B/ms)(B/ms)505050504040252525251010二次請求的間隔二次請求的間隔時間時間(S)(S)20 202020252540404040101000解解：(1)(1)(2)(2)總

41、容量總容量(3)(3)傳送周期傳送周期 T TS S+T+TD D=1ms/200B=5S=1ms/200B=5SmsBffiibyte/200611234566號設備丟失了一次數據號設備丟失了一次數據20us65學習幻燈 方法方法1：增加通道的最大流量增加通道的最大流量，保證連接在通道，保證連接在通道上的所有設備的數據傳送請求能夠及時得到通道上的所有設備的數據傳送請求能夠及時得到通道的響應的響應 方法方法2：動態改變設備的優先級動態改變設備的優先級 方法方法3：增加一定數量的數據緩沖器增加一定數量的數據緩沖器，特別是對，特別是對優先級比較低的設備優先級比較低的設備66學習幻燈例例4.2 印字

42、機各占一個子通道，印字機各占一個子通道，0號打印機、號打印機、1號打印號打印機和機和0號光電輸入機合用一個子通道。假定數據傳送號光電輸入機合用一個子通道。假定數據傳送期內高速印字機每隔期內高速印字機每隔25us發一個請求，低速打印機每發一個請求，低速打印機每隔隔150us發一個字節請求，光電輸入機每隔發一個字節請求，光電輸入機每隔800us發一發一個字節請求，則這個字節請求，則這5臺設備要求通道的實際流量為多臺設備要求通道的實際流量為多少？少？字節多路通道字節多路通道0子通道子通道2子通道子通道1子通道子通道0號高速號高速印字機印字機1號高速號高速印字機印字機0號打號打印機印機1號打號打印機印

43、機0號光電號光電輸入機輸入機67學習幻燈解：解：5臺設備要求通道的數據流量為：臺設備要求通道的數據流量為：可將該通道設計成可將該通道設計成0.1MB/s，即所設計的工作周期為，即所設計的工作周期為：這樣各設備的請求就能及時得到響應和處理，不這樣各設備的請求就能及時得到響應和處理，不會丟失信息。會丟失信息。sMBffbyte/095.0)800115011501(251251usTTftDSbyte101168學習幻燈0號印字機號印字機通道工作周期通道工作周期0us 50us 100us 150us1號印字機號印字機0號打印機號打印機1號打印機號打印機0號光電機號光電機表示設備提出申請的時刻表示

44、設備提出申請的時刻 表示通道處理完設備申請的時刻表示通道處理完設備申請的時刻優先級次序：優先級次序：0號印字機、號印字機、1號印字機、號印字機、0號打印機、號打印機、1號打印機、號打印機、0號光電機號光電機69學習幻燈例例4.3 4.3 設通道在數據傳送期中，選擇設備需設通道在數據傳送期中，選擇設備需4.9S4.9S，傳送一個字節數據需，傳送一個字節數據需0.lS0.lS。（1 1）其低速設備每隔）其低速設備每隔250S250S發出一個字節數據發出一個字節數據傳送請求，問最多可接多少臺這種設備？傳送請求，問最多可接多少臺這種設備？（2 2）若有）若有A AE E共共5 5種高速設備，要求字節傳

45、送種高速設備，要求字節傳送的間隔時間如下表所示，其時間單位為的間隔時間如下表所示，其時間單位為SS。若。若一次通信傳送的字節數不少于一次通信傳送的字節數不少于10241024個字節，問哪個字節，問哪些設備可掛在此通道上？哪些則不能？些設備可掛在此通道上？哪些則不能？設備設備A AB BC CD DE E時間間隔時間間隔(S)(S)0.130.130.10.10.110.110.20.20.30.370學習幻燈其中，其中，n1024，應使，應使 select i max select由此可得出通道工作周期為：由此可得出通道工作周期為：T0.1048(us)所以，只有所以，只有A、C、D、E可掛在

46、此通道上，可掛在此通道上，B則不行。則不行。n 2501.09.4111maxnfTTfniibyteDSbytennTTfSDselect9.41.011max71學習幻燈本章小結(1)5種I/O方式；(2)中斷優先級管理（屏蔽字表、中斷服務過程圖）；(3)3種通道處理機的特點；(4)3種通道最大能力流量；(5)3種通道實際最大負荷流量；(6)通道正常工作條件；(7)通道時間關系圖（字節多路通道）；習題：P250，題5，題8。72學習幻燈第五章第五章 標量流水線技術標量流水線技術(P253)P253)本章學習標量計算機上使用的流水加速技術。主要內容有流水技術的分類、流水線性能指標計算、非線性

47、流水線的調度算法。標量計算機指只能直接進行標量運算的計算機，與能夠直接進行向量運算的向量計算機相對應。流水處理方式的特征，是讓多個依次啟動的任務，盡量同時使用系統的不同部件，通過時間重疊來提高處理速率。這種技術理論上不增加成本。標量計算機上使用的流水加速技術屬于指令級并行技術。每條指令的處理過程，可以劃分為取指、譯碼、取數、運算、送結果5個子過程，也可以分得更細或更粗一些。劃分的原則是各部分時間長度大致相等、并使用CPU中不同的部件，這樣才有利于多任務重疊處理。73學習幻燈5.2 流水處理與邏輯相關的概念流水處理與邏輯相關的概念CPU中的各個部件按流水處理順序連接起來，就稱為一條流水線。5.2

48、.1 流水線工作原理 處理機解釋程序的方式有順序方式順序方式、重疊方式重疊方式、流水方式流水方式等。順序方式順序方式是解釋完一條指令再開始解釋下一條(P254)；流水方式流水方式是把一個重復的過程分解為若干個子過程，每個子過程可以與其它子過程同時進行，以此提高單位時間內解釋指令的數目(P277)；重疊方式重疊方式是一種簡單的流水方式，它把指令分成2個子過程，每條指令只與下一條指令相重疊(P255)。74學習幻燈 流水線結構圖(P278)流水線工作時空圖(P278P279)75學習幻燈76學習幻燈 5.2.2 邏輯相關邏輯相關(P263-276)相關的定義：(P263倒數第4段)一條指令必須等待

49、前一條指令解釋完成才能開始解釋。相關的分類及其對策1.全局性相關/局部性相關(P312、P269/P263、P303)；2.指令相關/數相關(P264/P263)；3.主存數相關/寄存器數相關(P265/P266)；4.數值相關/變址值相關(P266/P268)。77學習幻燈5.3 5.3 流水技術的分類流水技術的分類(P280)P280)線性/非線性(P280)：部件級/處理機級/處理機間級（宏流水線）(P281)：單功能/多功能(P282)：靜態/動態(P283)：標量/向量(P285)：同步/異步(P285)：順序/亂序(P285、P304)：78學習幻燈 5.4.1 吞吐率TP(P28

50、5)吞吐率（TP ThroughPut）指流水線在單位時間內執行的任務數，可以用輸入任務數或輸出任務數表示。，其中k表示流水線劃分的段數。當滿足 條件時，有 。5.4 5.4 線性流水線性能分析線性流水線性能分析(P285)P285)79學習幻燈其中5.4.2 5.4.2 加速比加速比(P288)P288)80學習幻燈段效率：，各段平均效率：其中 表示第i段設備量占整條流水線全部設備量的百分比。當滿足 條件時，有：5.4.3 5.4.3 效率（設備利用率，效率（設備利用率，P289P289）81學習幻燈1234 t t 3 t t 例例5.1 帶有瓶頸部件的帶有瓶頸部件的4功能段流水線功能段流

51、水線,t t1 1=t t2 2=t t4 4=t,t,t t3 3=3=3t,4t,4個任務、個任務、1010個任務時個任務時TPTP，E E、S SP P 。（1）分析法）分析法:各段時間不等各段時間不等tn1544t9)(64TP時，TP=TP=nt ti i+(n-1)+(n-1)tmaxtmaxi=1m82學習幻燈STS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151 234t111 23412341234輸出輸出=Sp=n*t ti imi=1t ti i+(n-1)(n-1)*t tj jmI=14*6 t t 15 t t=242415=1.6

52、E=E=n n個任務實際占用的時個任務實際占用的時-空區空區M M各段總的時各段總的時-空區空區%404.015615464tt（2）時空圖法）時空圖法83學習幻燈例例5.2 以浮點加法運算為例（四段流水線）各段時間相等，以浮點加法運算為例（四段流水線）各段時間相等，求吞吐率、效率。求吞吐率、效率。求求Z=A+B+C+D+E+F+G+H，TP、E、Sp (注意有相關注意有相關)Z=A+B+C+D+E+F+G+H1234567TP=7/15t tE E=7*4/(15*4)=7/1546%Sp=4*7/15=28/15=1.87解解:流水線的效率不高，原因在于存在著數據相關流水線的效率不高，原因

53、在于存在著數據相關,有空閑功能段。有空閑功能段。時間時間空間空間1111222233334444555566667777 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1584學習幻燈例例5.3 ASC計算機多功能算術運算流水線各段時間相等，計算機多功能算術運算流水線各段時間相等，6次浮點次浮點加、加、5次定點乘的吞吐率，效率，加速比次定點乘的吞吐率，效率，加速比 m=8，n=11分析：分析：T加加=6+(6-1)*1=11(t)T乘乘=4+(5-1)*1=8(t)則則 TP=（6+5）/(11+8)t=11/19t E=(6*6+5*4)t/(19*8t)=36.8%Sp

54、=(6*6+5*4)t/19t=56/19=2.94 123456123456123456123456123458671234561 23456時間時間浮加浮加定點乘定點乘一一二二三三 四四 五五一一二二三三 四四 五五一一二二三三 四四五五一一二二三三 四四五五 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1985學習幻燈作業作業5.7 p343 5.7 p343 一條線性流水線有一條線性流水線有4 4個功能段組成，每個功個功能段組成，每個功能段的延遲時間都相等，都為能段的延遲時間都相等，都為tt。開始。開始5 5個個tt，每間隔一，每間隔一個個

55、tt向流水線輸入一個任務，然后停頓向流水線輸入一個任務，然后停頓2 2個個tt，如此重復，如此重復。求流水線的實際吞吐率、加速比和效率。求流水線的實際吞吐率、加速比和效率。解答解答流水線的時空圖如下：流水線的時空圖如下：功能段 1 功能段 2 功能段 3 功能段 4 t 2t 3t 4t 5t 6t 7t 8t 10t 9t 1 2 1 1 1 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 1111t 12t 13t 14t 15t 86學習幻燈我們可以看出，在（我們可以看出，在（11n+111n+1）tt的時間內，可以輸出的時間內，可以輸出5n5

56、n個個結果，如果指令的序列足夠長（結果，如果指令的序列足夠長（nn），并且指令間不存），并且指令間不存在相關，那么，吞吐率可以認為滿足：在相關，那么，吞吐率可以認為滿足：加速比為：加速比為：從上面的時空圖很容易看出，效率為：從上面的時空圖很容易看出，效率為：)(115)/111(5)111(5nttntnnTp)(1120/1112011120)111(45nnnntntnS)(115/1115)111(420nntntnE87學習幻燈作業作業 5.85.8 用一條用一條5 5個功能段的浮點加法器流水線計算個功能段的浮點加法器流水線計算 每個功能段的延遲時間均相等，流水線的輸出端和輸入端之間每

57、個功能段的延遲時間均相等，流水線的輸出端和輸入端之間有直接數據通路，而且設置有足夠的緩沖寄存器。要求用盡可有直接數據通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，并計算流水線的實能短的時間完成計算，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。際吞吐率、加速比和效率。解答解答 首先需要考慮的是，首先需要考慮的是，1010個數的的和最少需要做幾次加法個數的的和最少需要做幾次加法。我們可以發現，加法的次數是不能減少的：。我們可以發現，加法的次數是不能減少的：9 9次；于是我們次；于是我們要盡可能快的完成任務，就只有考慮如何讓流水線盡可能要盡可能快的完

58、成任務，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關。由于加法滿足交換率和結這需要消除前后指令之間的相關。由于加法滿足交換率和結合率，我們可以調整運算次序如以下的指令序列，我們把中間合率，我們可以調整運算次序如以下的指令序列，我們把中間結果寄存器稱為結果寄存器稱為R R，源操作數寄存器稱為，源操作數寄存器稱為A A，最后結果寄存器稱，最后結果寄存器稱為為F F，并假設源操作數已經在寄存器中，則指令如下：，并假設源操作數已經在寄存器中，則指令如下：101iiAF88學習幻燈 I1：R1A1+A2 I2：R2A3+A4 I3：R3A5+A6 I4：R4A7+A8 I5：R5A9+

59、A10 I6：R6R1+R2 I7：R7R3+R4 I8：R8R5+R6 I9：FR7+R8 這并不是唯一可能的計算方法。假設功能段的延遲這并不是唯一可能的計算方法。假設功能段的延遲為為tt。時空圖如下，圖中的數字是指令號。時空圖如下，圖中的數字是指令號。89學習幻燈 32 1 4 1 1 1 1 2 2 2 2 3 3 3 34 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 921t部件m15432R1=A1+A2R2=A3+A4R3=A5+A6R4=A7+A8R5=A9+A10R6=R1+R2R7=R3+R4R8=R5+R6F=

60、R7+R8R1R3R5R6R7R8FR2R490學習幻燈整個計算過程需要整個計算過程需要21t21t，所以吞吐率為：，所以吞吐率為：加速比為：加速比為：效率為：效率為：tTp21914.221452159ttS%86.4221559ttE91學習幻燈 作業作業 5.95.9(類似題類似題5.8)5.8)一條線性靜態多功能流水線由一條線性靜態多功能流水線由6 6個個功能段組成，加法操作使用其中的功能段組成，加法操作使用其中的1 1、2 2、3 3、6 6功能段，乘法功能段，乘法操作使用其中的操作使用其中的1 1、4 4、5 5、6 6功能段，每個功能段的延遲時間功能段，每個功能段的延遲時間均相等

61、。流水線的輸入端與輸出端之間有直接數據通路，而均相等。流水線的輸入端與輸出端之間有直接數據通路，而且設置有足夠的緩沖寄存器?，F在用這條流水線計算：且設置有足夠的緩沖寄存器?，F在用這條流水線計算：畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。效率。61)(iiiBAF92學習幻燈解：解：為了取得較高的速度，我們需要一次將乘法作完，設源操為了取得較高的速度，我們需要一次將乘法作完，設源操作數存放在寄存器作數存放在寄存器A A、B B中，中間結果存放在寄存器中，中間結果存放在寄存器R R中，最后結中，最后結果存放在寄存器果存放在寄存器F

62、 F中，則執行的指令序列如下所示：中，則執行的指令序列如下所示：I1I1：R1A1R1A1*B1B1I2I2：R2A2R2A2*B2B2I3I3：R3A3R3A3*B3B3I4I4：R4A4R4A4*B4B4I5I5：R5A5R5A5*B5B5I6I6：R6A6R6A6*B6B6I7I7：R7R1+R2R7R1+R2I8I8：R8R3+R4R8R3+R4I9I9：R9R5+R6R9R5+R6I10I10：R10R7+R8R10R7+R8I11I11：FR9+R10FR9+R10這并不是唯一可能的計算方這并不是唯一可能的計算方法。假設功能段的延遲為法。假設功能段的延遲為tt。時空圖（不完全）如。

63、時空圖（不完全）如下，圖中的數字是指令號。下，圖中的數字是指令號。93學習幻燈1 222t部件m15432R1=A1*B1R2=A2*B2R3=A3*B3R4=A4*B4R5=A5*B5R6=A6*B6R7=R1+R2R8=R3+R4F=R9+R10R1R10R6R7R8F6111332223 434445 6555 6667 87778889R9=R5+R6R10=R7+R89991010111010111111乘法加法94學習幻燈整個計算過程需要整個計算過程需要22t22t，所以吞吐率為：，所以吞吐率為：加速比為：加速比為：效率為：效率為：tTp22922244224)56(ttS%3.3

64、32264)56(ttE95學習幻燈 例例5.45.4 有一個浮點乘流水線如下圖有一個浮點乘流水線如下圖(a)(a)所示，其乘積可所示，其乘積可直接返回輸入端或暫存于相應緩沖寄存器中，畫出實直接返回輸入端或暫存于相應緩沖寄存器中，畫出實現現A A*B B*C C*D D的時空圖以及輸入端的變化，并求出該流水的時空圖以及輸入端的變化，并求出該流水線的吞吐率和效率；當流水線改為下圖線的吞吐率和效率；當流水線改為下圖(b)(b)形式實現同形式實現同一計算時，求該流水線的效率及吞吐率。一計算時，求該流水線的效率及吞吐率。階加尾乘規格化t3tt積操作數圖(a)階加尾乘1尾乘2尾乘3規格化積t3tt3t3

65、t圖(b)96學習幻燈 分析分析 為了減少運算過程中的操作數相關，為了減少運算過程中的操作數相關，A A*B B*C C*D D應改為采應改為采用用(A(A*B)B)*(C(C*D)D)的算法步驟進行運算。的算法步驟進行運算。解解 按圖按圖(a)(a)組織，實現組織，實現A A*B B*C C*D D的時空關系如下圖的時空關系如下圖(A)(A)所示。所示。時間部件輸入輸出ABCDA*BC*DA*BC*DA*B*C*D13規格化尾乘階加圖(A)吞吐率吞吐率TP=3/(13t)TP=3/(13t)效率效率E=(3E=(35t)/(35t)/(313t)=5/13=38.5%13t)=5/13=38

66、.5%97學習幻燈時間部件輸入輸出ABCDA*BC*DA*BC*DA*B*C*D規格化尾乘3尾乘2尾乘1階加圖(B)11流水線按圖流水線按圖(b)(b)組織時，實現組織時，實現A A*B B*C C*D D的時空關系如圖的時空關系如圖(B)(B)吞吐率吞吐率TP=3/(11t)TP=3/(11t)效率效率E=(3E=(35t)/(55t)/(511t)=3/11=27.3%11t)=3/11=27.3%98學習幻燈本章小結本章小結(1)流水處理與相關的概念；(2)時空圖畫法及其應用；(3)7種流水線分類方法；(4)3個流水線性能指標；(5)2種“瓶頸”解決方法；99學習幻燈第七章 互連網絡1.設16個處理機的編號分別為0、1、15，采用單級互連網絡?；ミB函數分別為：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第12號處理機分別與哪一個處理機相連？100學習幻燈解：(12)10下=(1100)2下1100最高位取反得0100，4號處理機(12+8)MOD 16=4，4號處理機12 1=11，11號處理機1100循環左移