福建農(nóng)林大學(xué)系統(tǒng)結(jié)構(gòu)計算題

1、-. z.題型一：一五六題型二：二七題型三：三四題型四：八九十十一十二十三十四十五題型五：十六十七十八題型六：十九二二二三二五二六二七二八其他題型考選擇題：二十二一二四二九三十一【7-6】由霍納法則給定的表達(dá)式如下：E=a(b+c(d+e(f+gh)利用減少樹高的方法來加速運(yùn)算，要求：畫出樹形流程圖。確定TP、P、SP、EP的值。解：1假設(shè)用單處理機(jī)處理，T1=7，改成E=ace(f+gh)+a(b+cd)，其計算的樹形流程圖如附圖46所示。P=3；TP=4；SP=T1/TP=7/4；EP=SP/P=7/12二【6-2】設(shè)向量長度均為64，在CRAY-1機(jī)上所用浮點(diǎn)功能部件的執(zhí)行時間分別為：相

2、加6拍，相乘7拍，求倒數(shù)近似值14拍；在存儲器讀數(shù)6拍，打入存放器及啟動功能部件各1拍。問以下各指令組的哪些指令可以？哪些指令不可？不能的原因是什么？分別計算出各指令全部完成所需的拍數(shù)。V0存儲器2V2V0V1V1V2+V3 V3存儲器V4V5V6 V4V0+ V3V0存儲器4V0存儲器V2V0V1 V11/ V0V3V2+ V0 V3V1V2V5V3+ V4 V5V3+ V4解：1三條全并行，完成時間為72拍2一、二條并行，第三條，完成時間為80拍3第一條第二條，與第三條串行，與第四條串行，完成時間為222拍4全，完成時間為104拍三【例5-3】在一個4段的流水線處理機(jī)上需經(jīng)7拍才能完成一個

3、任務(wù)，其預(yù)約表如表5-2所示。表5-2 7拍才能完成一個任務(wù)的預(yù)約表段時間1234567 S1 S2 S3 S4分別寫出延遲制止表F、沖突向量C；畫出流水線狀態(tài)轉(zhuǎn)移圖；求出最小平均延遲及流水線的最大吞吐率及其調(diào)度時的最正確方案。按此調(diào)度方案，輸入6個任務(wù)，際的吞吐率。解：此例可得延遲制止表F=2,4,6。初始沖突向量C=101010。狀態(tài)轉(zhuǎn)移圖如圖5-29所示。各種調(diào)度方案及其相應(yīng)的平均延遲如表5-3所示。表5-3 調(diào)度方案及其相應(yīng)的平均延遲調(diào)度方案平均延遲/拍1,7 43,5 45,3 45 4由表5-3可知，最小平均延遲為4拍。此時流水線的最大吞吐率Tpma*=1/4任務(wù)/拍。最正確調(diào)度方

4、案宜選其中按1,7周期性調(diào)度的方案。按1,7調(diào)度方案輸入6個任務(wù)，全部完成的時間為1+7+1+7+1+7=24拍，實(shí)際吞吐率Tp=6/24任務(wù)/拍。假設(shè)按3,5調(diào)度方案輸入6個任務(wù)，全部完成的時間為3+5+3+5+3+7=26拍，實(shí)際吞吐率Tp=6/26任務(wù)/拍。假設(shè)按5,3調(diào)度方案輸入6個任務(wù)，全部完成的時間為5+3+5+3+5+7=28拍，實(shí)際吞吐率Tp=6/28任務(wù)/拍?？梢?，最正確的方案應(yīng)為1,7調(diào)度方案，輸入6個任務(wù)的實(shí)際吞吐率較之其他方案要更高些。四【5-11】在一個5段的流水線處理機(jī)上需經(jīng)9拍才能完成一個任務(wù)，其預(yù)約表如表5-4所示。分別寫出延遲制止表F、沖突向量C；畫出流水線狀

5、態(tài)轉(zhuǎn)移圖；求出最小平均延遲及流水線的最大吞吐率及其調(diào)度方案。按此流水線調(diào)度方案輸入6個任務(wù)，際吞吐率。表5-4 9拍才能完成一個任務(wù)的預(yù)約表段時間 T0T1T2T3T4T5T6T7T8S1S2S3S4S5解：根據(jù)預(yù)約表中各個行中打的拍數(shù)求出差值，并將這些差值聚集在一起，就可得到延遲制止表F=1,3,4,8。由延遲制止表F可轉(zhuǎn)換得初始沖突向量C=10001101。根據(jù)初始沖突向量可畫出狀態(tài)轉(zhuǎn)換圖如附圖31所示。各種周期性調(diào)度方案列于附表15。由附表15可知最小平均延遲為3.5拍。此時，Tpma*=1/3.5任務(wù)/拍。最正確調(diào)度方案為2,5。附表15 周期性調(diào)度方案調(diào)度方案平均延遲/拍調(diào)度方案平均

6、延遲/拍2,53.56,76.52,74.577555,23.56,55.566按2,5調(diào)度方案實(shí)際輸入6個任務(wù)的時空圖如附圖32所示。實(shí)際吞吐率Tp=6/25任務(wù)/拍。五【例7-4】計算E1=a+b*+c*+d*。利用減少樹高的方法來加速運(yùn)算，要求：畫出樹形流程圖。確定TP、P、SP、EP的值。解：1利用霍納法可得到E1=a+*(b+*(c+*(d)。假設(shè)用單處理機(jī)處理，T1=7，改成E1=a+*(b+*(c+*(d)。其計算的樹形流程圖如附圖7-17a所示。TP=4、P=3、SP=3/2、EP=1/2六【例7-6】表達(dá)式E2=a+b(c+def+g)+h。利用減少樹高的方法來加速運(yùn)算，要求

7、：畫出樹形流程圖。確定TP、P、SP、EP的值。解：P253-P254七【P201】設(shè)向量長度均為64，在CRAY-1機(jī)上所用浮點(diǎn)功能部件的執(zhí)行時間分別為：相加6拍，相乘7拍，求倒數(shù)近似值14拍；在存儲器讀數(shù)6拍，打入存放器及啟動功能部件各1拍。問以下指令組的哪些指令可以？哪些指令不可？不能的原因是什么？分別計算出各指令全部完成所需的拍數(shù)。V3存儲器V2V0+V1V4V2V3解：P201-P202八【5-3】有一個浮點(diǎn)乘流水線如圖5-36a所示，其乘積可直接返回輸入端或暫存于相應(yīng)緩沖存放器中，畫出實(shí)現(xiàn)ABCD的時空圖以及輸入端的變化，并求出流水線的吞吐率和效率；當(dāng)流水線改為圖5-36b所示的形

8、式實(shí)現(xiàn)同一計算時，求該流水線的效率及吞吐率。解：按圖5-36a組織，實(shí)現(xiàn)ABCD的時空關(guān)系如附圖16所示。吞吐率：Tp=3/13t ；效率：=35t/313t=5/13流水線按圖5-36b組織，實(shí)現(xiàn)ABCD的時空關(guān)系如附圖17所示。吞吐率：Tp=3/11t；效率：=35t/311t=5/11九【5-4】一個4段的雙輸入端規(guī)格化浮點(diǎn)加法流水線，每段經(jīng)過時間為10ns，輸出可直接返回輸入或?qū)⒔Y(jié)果暫存于相應(yīng)緩存器中，問最少需要經(jīng)多長時間才能求出10i=1Ai，并畫出時空圖。解：按A1+A2+A3+A4+A9+A10+A5+A6+A7+A8流水的時空圖如附圖18所示。十【5-5】為提高流水線效率可采用

9、哪兩種主要途徑來克制速度瓶頸？現(xiàn)有3段流水線各經(jīng)過時間依次為t、3t、t。1分別計算在連續(xù)輸入3條指令和30條指令時的吞吐率和效率。2按兩種途徑之一進(jìn)展改良，畫出流水線構(gòu)造示意圖，同時計算連續(xù)輸入3條指令和30條指令時的吞吐率和效率。3通過對1、2兩小題的計算比擬可得出什么結(jié)論？解：提高流水線效率，消除速度瓶頸主要有兩種途徑：將瓶頸段再細(xì)分；重復(fù)設(shè)置多個瓶頸段并聯(lián)工作，給其輪流分配任務(wù)。在3段流水線各段經(jīng)過時間依次為t、3t、t的情況下，連續(xù)流入3條指令時，將n=3，m=3，t1=t、t 2=3t、t3=t，tj=3t代入，可得吞吐率Tp和效率為假設(shè)采取將2段細(xì)分成3個子段，每個子段均為t，構(gòu)

10、成流水線構(gòu)造如附圖10所示。假設(shè)采取將3個2段并聯(lián)構(gòu)成的流水線，其構(gòu)成如附圖20所示。十一【5-6】有一個雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時間為t、2t、2t、t的1、2、3、4四個子過程構(gòu)成。加按124連接，乘按134連接，流水線輸出設(shè)有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入?，F(xiàn)要執(zhí)行AB+CD+EF+GH的運(yùn)算，請調(diào)整計算順序，畫出能獲得吞吐率盡量高的流水時空圖，標(biāo)出流水線入、出端數(shù)的變化情況，求出完成全部運(yùn)算的時間及此期間流水線的效率。如對流水線瓶頸子過程再細(xì)分，最少需多長時間可完成全部運(yùn)算？假設(shè)子過程3不能再細(xì)分，只能用并聯(lián)方法改良，則流水線的效率為多少？解：十二【5-7】有一個乘

11、-加雙功能靜態(tài)流水線，乘由1234完成，加由154完成，各段延時均為t，輸出可直接返回輸入或存入緩沖器緩沖?，F(xiàn)要求計算長度均為8的A、B兩個向量逐對元素求和的連乘積 S=8i=1Ai+Bi畫出流水線完成此運(yùn)算的時空圖。完成全部運(yùn)算所需多少t？此期間流水線的效率是多少？解：十三【5-8】帶雙輸入端的加-乘雙功能靜態(tài)流水線有1、2、3、4四個子部件，延時分別為t、t、2t、t，加按124連接，乘按134連接，輸出可直接返回輸入或鎖存，現(xiàn)欲執(zhí)行4i=1ai+bici。畫出此流水線時空圖，標(biāo)出流水線入端數(shù)據(jù)變化情況。計算運(yùn)算全部完成所需時間及在此期間流水線的效率。將瓶頸子部件再細(xì)分，畫出解此題的時空圖

12、。求出按3解此題所需時間及在此期間流水線的效率。解：1234十四【5-9】現(xiàn)有長度為8的向量A和B，請分別畫出以下4種構(gòu)造的處理器上求點(diǎn)積AB的時空圖，并求完成全部結(jié)果的最少時鐘拍數(shù)。設(shè)處理器中每個部件的輸出均可直接送到任何部件的輸入或存入緩沖器中，其間的傳送延時不計，指令和源操作數(shù)均能連續(xù)提供。處理器有個一乘法部件和一個加法部件，不能同時工作，部件也只能以順序方式工作，完成一次加法或乘法均需5拍。與1根本一樣，只是乘法部件和加法部件可并行。處理器有一個乘-加雙功能靜態(tài)流水線，乘、加均由5個流水線構(gòu)成，各段經(jīng)過時間要1拍。處理器有乘、加兩條流水線，可同時工作，各由5段構(gòu)成，每段經(jīng)過時間為1拍。

13、解：十五【5-2】流水線由4個功能部件組成，每個功能部件的延遲時間為t，當(dāng)輸入10個數(shù)據(jù)后間歇5t又輸入10個數(shù)據(jù)，如此周期性地工作，求此時流水線的吞吐率，并畫出其時空圖。十六【例3-3】P89P91十七【3-5】設(shè)中斷級屏蔽位1對應(yīng)于開放，0對應(yīng)于屏蔽，各級中斷處理程序的中斷級屏蔽設(shè)置如表3-6所示。表3-6 習(xí)題3-5中的中斷級屏蔽位設(shè)置中斷處理程序級別中斷級屏蔽位第1級第2級第3級第4級第1級0000第2級1011第3級1000第4級1010當(dāng)中斷相應(yīng)優(yōu)先次序?yàn)?234時，其中斷處理次序是什么？設(shè)所有的中斷處理都各需3個單位時間，中斷響應(yīng)和中斷返回時間相對中斷處理時間少得到多。當(dāng)機(jī)器正在

14、運(yùn)行用戶程序時，同時發(fā)生第2、3級中斷請求，過兩個單位時間后，又同時發(fā)生第1、4級中斷請求，試畫出程序運(yùn)行過程示意圖。解：1中斷處理完的次序?yàn)?342。CPU運(yùn)行程序的過程示意圖如附圖4所示。在該圖中，粗短線局部代表進(jìn)展交換程序狀態(tài)字的時間，t為1個單位時間。十八【3-6】假設(shè)機(jī)機(jī)器共有5級中斷請求，中斷響應(yīng)優(yōu)先次序?yàn)?2345，現(xiàn)要求其實(shí)際的中斷處理次序?yàn)?4523，答復(fù)下面問題：設(shè)計各級中斷處理程序的中斷級屏蔽位令1對應(yīng)于屏蔽，0對應(yīng)于開放；假設(shè)在運(yùn)行用戶程序時，同時出現(xiàn)第4、2級中斷請求，而在處理第2級中斷未完成時，又同時出現(xiàn)第1、3、5級中斷請求，請畫出此程序運(yùn)行過程示意圖。解：12十

15、九【例2-5】現(xiàn)假設(shè)*模型機(jī)共有nn=7條指令，使用頻度如表2-4所示。假設(shè)操作碼用定長表示，需要3位。而按信息論觀點(diǎn)，假設(shè)各種指令的出現(xiàn)是互相獨(dú)立的實(shí)際并不都是如此，操作碼的信息源熵信息源所含平均信息量H=-ni=1pi1bpi。由表2-4的數(shù)據(jù)可得H=-ni=1pi1bpi=2.17。說明表示這7種指令的操作碼平均只需2.17位即可?，F(xiàn)在用3位定長碼表示，信息冗余度為3-2.17/328%。冗余度相當(dāng)大。指令使用頻度pi指令使用頻度piI10.40I50.04I20.30I60.03I30.15I70.03I40.05-改用哈夫曼編碼以及擴(kuò)展的哈夫曼編碼；構(gòu)造哈夫曼數(shù)；解：1指令頻度pi操

16、作碼OP使用哈夫曼編碼OP長度li利用哈夫曼概念的擴(kuò)展操作碼OP長度liI10.4001002I20.30102012I30.151103102I40.0511100511004I50.0411101511014I60.0311110511104I70.03111115111142二十【例2-6】P59二一【例2-7】假設(shè)*機(jī)要求有：三地址指令4條，單地址指令255條，零地址指令16條。設(shè)指令字長為12位，每個地址碼長為3位。能否以擴(kuò)展操作碼為其編碼？如果單地址指令改為254條呢？解：P60二二【例2-8】*模型機(jī)9條指令的使用頻度如表2-7所示。要求有兩種指令字長，都按雙操作數(shù)指令格式編排，

17、采用擴(kuò)展操作碼，并限制只能有兩種操作碼碼長。設(shè)該機(jī)有假設(shè)干通用存放器，主存為16位寬，按字節(jié)編址，采用按整數(shù)邊界存儲，任何指令都在一個主存周期中取得，短指令為存放器-存放器型，長指令為存放器-主存型，主存地址應(yīng)能變址尋址。表2-7 模型機(jī)指令指令使用頻度指令使用頻度指令使用頻度ADD加STO存CIL循環(huán)左移30%7%3%SUB減JMP轉(zhuǎn)移CLA清加24%7%20%JOMSHR右移STP停機(jī)6%2%1%改用哈夫曼編碼以及擴(kuò)展的哈夫曼編碼；構(gòu)造哈夫曼數(shù)；計算平均碼長解：1哈夫曼編碼：ADD加30%01SUB減24%11CLA20%10JOM6%0001STO7%0011JMP7%0010SHR2%

18、000001CIL3%00001STP1%00000擴(kuò)展的操作碼編碼：ADD加30%00SUB減24%01CLA20%10JOM6%11000STO7%11001JMP7%11010SHR2%11011CIL3%11100STP1%11101哈夫曼樹：平均碼長：哈夫曼編碼：2.61位；擴(kuò)展碼：2.78位。二三【2-4】設(shè)*機(jī)器階值6位、尾數(shù)48位，階符和數(shù)符不在其，當(dāng)尾數(shù)分別2、8、16為基時，在非負(fù)階、正尾數(shù)、規(guī)格化情況下，求出其最小階、最大階、階的個數(shù)、最小尾數(shù)值、最大尾數(shù)值、可表示的最小值和最大值及可表示數(shù)的個數(shù)。解：p=6，m=48時，在非負(fù)階、規(guī)格化、正尾數(shù)的情況下，rm=2,8,1

19、6的各個參數(shù)的計算結(jié)果如附表1所示：二四【2-5】浮點(diǎn)數(shù)系統(tǒng)使用的階基rp=2，階值位數(shù)p=2，尾數(shù)基值rm=10，以rm為基的尾數(shù)m=1。試計算在非負(fù)階、正尾數(shù)、規(guī)格化情況下的最小尾數(shù)值、最大尾數(shù)值、最大階值、可表示的最小值和最大值及可表示數(shù)的個數(shù)；對于rp=2，p=2，rm=4，m=2，重復(fù)以上計算。解：1在非負(fù)階、正尾數(shù)、規(guī)格化情況下：2二五【2-6】由4位數(shù)其中最低位為下溢處理的附加位經(jīng)ROM查表舍入法，下溢處理成3位結(jié)果，設(shè)計使下溢處理平均誤差接近于0的ROM表，列出ROM編碼表的地址與容的對應(yīng)關(guān)系。解：ROM下溢處理表16個單元的地址碼為00001111，它與其容即下溢處理后的3位

20、結(jié)果值的對照關(guān)系如下表所示：地址00000001001000110100010101100111容000001001010010011011100地址10001001101010111100110111101111容100101101110110111111111二六【2-9】經(jīng)統(tǒng)計，*機(jī)器14條指令的使用頻度分別為0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14,0.11,0.03。分別求出用等長碼、哈夫曼碼、只有兩種碼長的擴(kuò)展操作碼等3種編碼方式的操作碼平均碼長。解：14條指令的等長操作碼的平均碼長是4位。哈夫曼編碼平均

21、碼長3.38位。只有兩種碼長的擴(kuò)展操作碼平均碼長3.4位。二七【2-10】電文由AJ及空格字符組成，其字符出現(xiàn)頻度依次為0.17,0.05,0.20,0.06,0.08,0.03,0.01,0.08,0.13,0.08，0.11。各字符用等長二進(jìn)碼編碼，傳送103個字符時，共需傳送多少個二進(jìn)制碼碼位？構(gòu)造哈夫曼數(shù)，寫出各字符的二進(jìn)碼碼位數(shù)，計算字符的二進(jìn)制位平均碼長。用哈夫曼碼傳送103個字符，比定長碼傳送減少傳送的二進(jìn)制碼碼位數(shù)是多少？解：1共需傳送4103位。哈夫曼樹如附圖2所示。字符碼的二進(jìn)制位平均碼長為3.23位?？蓽p少傳送的二進(jìn)制碼碼位數(shù)是4-3.23103=770位二八【2-11】用于文字處理的*專用機(jī)，每