計算機科學(xué)與技術(shù)試卷

1、XXXX年同等學(xué)力人員申請碩士學(xué)位學(xué)科綜合水平全國統(tǒng)一考試 計算機科學(xué)與技術(shù)試卷第二部分專業(yè)知識課程課程I計算機系統(tǒng)結(jié)構(gòu)1999年試卷（5分）解釋下列名詞Amdahl 定律并行處理局部性原理虛擬共享存儲器非均勻存儲器（簡稱NUMA）型共亨存儲多處理機（10分）某臺計算機只有Load/Store指令能對存儲器進行讀/寫操作，其它指令只對寄存器進 行操作。根據(jù)程序跟蹤實驗結(jié)果，己知每種指令所占的比例及CPI數(shù)如下：指令系統(tǒng)指令所占比例CPI算邏指令43%1Load指令21%2Store指令12%2轉(zhuǎn)移指令2 1%2（4分）求上述情況下的平均CPI；（6分）假設(shè)程序由M條指令組成，算邏運算中25%的

2、指令的兩個操作數(shù)中的一個己在寄存器 中，另一個必須在算邏指令執(zhí)行前用Load指令從存儲器取到寄存器。因此有人建議增加另一種算 邏指令，其特點是一個操作數(shù)取自寄存器，另一個操作數(shù)取自存儲器，即寄存器-存儲器類型。假 設(shè)這種指令的CPI等于2,同時，轉(zhuǎn)移指令CPI變?yōu)?,求新的指令系統(tǒng)的平均CPI。（10分）一動態(tài)多功能流水線由6個功能段組成，如下圖其中：SI、S4、S5、S6組成乘法流水線，SI、S2、S3、S6組成加法流水線。各個功能段時間均為 50ns,假設(shè)該流水線的輸出結(jié)果可以直接返回流水線輸入端，而且設(shè)置有足夠的緩沖寄存器，若 按照最快的方式用該流水線計算F = X1XY1XZ1 + .

3、 + X5XY5XZ5。（4分）請畫出其處理過程的時空圖；（6分）計算其實際吞吐率、加速比和效率；（10分）有一個由高速緩沖存儲器與主存儲器組成的二級存儲系統(tǒng)，己知其主存容量為32KB,采用組相聯(lián)方式進行地址映象與變換，主存與緩存的一塊為64字節(jié)，緩存共分8組，每組 16塊。（4分）畫出主存與緩存的地址格式（地址總長度及各字段名稱與位數(shù)）（6分）假定Cache之存儲周期為20ns,命中率為0. 95,希望采用Cache后的加速比大于10, 那么要求主存儲器的存取速度應(yīng)大于多少？一、（共5分，每題1分）解釋下列名詞MFLOPS基準測試程序分布存儲多處理機互連網(wǎng)絡(luò)數(shù)據(jù)驅(qū)動方式 二、（共12分，每題

4、4分）簡答題請問在指令集結(jié)構(gòu)設(shè)計中，應(yīng)該考慮哪些主要問題，針對這些問題有哪些主要的設(shè)計選擇？請問向量處理機的工作方式可以分為哪兒大類？它們對向量處理支持主要有哪些技術(shù)特點？Cache的寫操作有哪兩種方式？從可靠性和通信量（指Cache與主存間）兩方面比較兩種方 式的優(yōu)劣。三、（6分）設(shè)有100個處理器，要求應(yīng)用程序的加速比達到80,求：應(yīng)用程序所需的并行化比率（應(yīng)用程序中可并行化成分占應(yīng)用程序的百分比）：在使用50個處理器的方式下，請求出該應(yīng)用程序的加速比；請分別求出使用100個和50個處理器時的加速效率。四、（6分）假設(shè)一臺主頻為200MHZ的向量處理機中功能部件的啟動開銷為：取向量X標量和

5、向量相乘取數(shù)和存數(shù)為12個時鐘周期、乘法部件為7個時鐘周期、加法部件為6個時鐘周期；向量寄 存器的長度為64,允許向量鏈接處理；執(zhí)行標量代碼開銷（分段開采開銷）是一個常數(shù)，大小為 15?，F(xiàn)在該向量處理機上運行下列DAXPY代碼（Y=a*X+Y,其中X和Y是長度為n的向量，初 始時己存放在內(nèi)存；a是一個標量）： LV 取向量X標量和向量相乘取向量Y 相加 存結(jié)果取向量Y 相加 存結(jié)果LVV3, RY；ADDV V4, V2, V3；SVRY, V4求DAXPY在該向量處理機上運行所需要的時鐘周期數(shù)。最大性能是多少MFLOPS?半性能向 量長度是多少？五、（6分）在頁式虛擬存儲器中，一個程序由P1

6、P5共5個頁面組成，在程序的執(zhí)行過程中， 依次訪問到的頁面順序如下:P2, P3, P2, Pl, P5, P2, P4, P5, P3, P2, P5, P2,假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，采用LFU替換算法，試求出其頁命中率。如果在程序執(zhí)行過程中每訪問一個頁面，平均要對該頁面內(nèi)的存儲單元訪問32次，求訪問主 存單元的命中率？一、名詞解釋（5X1=5分）MIPS互連網(wǎng)絡(luò)直徑機群系統(tǒng)預(yù)約表窗口重疊技術(shù) 二、填空（17分）在虛擬存儲器中有三種地址空間。應(yīng)用程序員用來編寫應(yīng)用程序的空間叫;第二種是空間，第三種是輔存地址空間，也就是磁盤存儲器的地址空間。與這三種地址空間相對 應(yīng)的三種地址為

7、, 和磁盤存儲器地址。 在CISC中，指令使用頻度比較高，占據(jù) 處理機時間。向量流水線存儲器結(jié)構(gòu)有 和 兩種。在多功能流水線中，按照在同一時間內(nèi)是否能夠連接成多種方式、同時執(zhí)行多種功能，可以把多功能流水線分為 和 兩種。 計算機體系結(jié)構(gòu)分為SISD、o?三、三、（4分）假設(shè)某處理機時鐘頻率為 15MHz,程序主要由輸入輸出等四種指令組 成，指令混合比及每種指令時鐘周期數(shù)如下：（1）（2分）求此處理機有效CPI。（2）（2分）若將處理機時鐘提高到50MHz,求 相應(yīng)的運行速率。指令類型時鐘周期數(shù)指令混合比A類310%B類140%C類240%D類（輸入輸出類）110%四、（4分）矩陣乘法OAXB,

8、 A和B為6X6的矩陣，加法、乘法部件的延遲時間均為3個時鐘 周期（每個時鐘周期20ns）,加法、乘法指令都有“取指令”、“分析指令”（各占一個時鐘周 期）。計算在下面不同情況下所需最短時間。（1）（2分）處理機只有一個通用部件，采用順序方式執(zhí)行。（2）（2分）有一條兩功能靜態(tài)流水線，加法、乘法都經(jīng)過3個功能段，每個功能段延遲時間為一 個時鐘周期。五、（4分）在Cache-主存存儲系統(tǒng)中，Cache命中率為0. 96,主存命中率為？。（1）（2分）求系統(tǒng)的等效命中率；（2）（2分）在Cache命中指令中，指令分指令體和數(shù)據(jù)體兩部分，其中20%為指令體。若將整個 系統(tǒng)等效命中率減少10%,求數(shù)據(jù)

9、體命中率為多少？2002年試卷（2002/6/9）一、名詞解釋（5X1=5分）CPI高速緩沖存儲器（Cache）流水線控制相關(guān)靜態(tài)互連網(wǎng)絡(luò)SIMD計算機二、填空題（6X2=12分）計算機系統(tǒng)結(jié)構(gòu)是計算機系統(tǒng)的軟、硬件的分界面，計算機組成計算機系統(tǒng)結(jié)構(gòu)的;計算機實現(xiàn)是計算機組成的 o它們各自包含不同的內(nèi)容，但又有緊密關(guān)系。假設(shè)高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90%,則采用 Cache后，能使整個系統(tǒng)獲得的加速比為。根據(jù)多臺外圍設(shè)備共享通道的不同情況，可將通道分為三種類型，字節(jié)多路通道、和 O在指令流水線中，數(shù)據(jù)相關(guān)有、和先寫后寫三種。一個5段流水線，各段執(zhí)行

10、時間分別為Ins, 2ns, 2ns, Ins, 2ns,在該流水線上完成10個連續(xù)任務(wù)所需要的時間為 nso設(shè)有16個處理器（編號分別為0, 1, 2.15）,采用單級互連網(wǎng)絡(luò)，當(dāng)互連函數(shù)為Shuffle （shuffle）時，第8號處理器與 號處理機相連。三、（6分）假定你是一個計算機設(shè)計者，己設(shè)想了一個優(yōu)化的設(shè)計方案，它能減少過程調(diào)用和返回所需 的取/存指令次數(shù)。為了進行驗證，對未加優(yōu)化和己優(yōu)化的方案進行實驗測試，其中假定所使用的 是相同的優(yōu)化編譯器。實驗測得的結(jié)果如下：優(yōu)化方案的時鐘周期比未優(yōu)化的快15%；未優(yōu)化方案的取/存指令數(shù)占總指令數(shù)的30%；優(yōu)化方案的取/存指令數(shù)比未優(yōu)化方案的

11、少1/3：對于其他指令，兩種方案的動態(tài)執(zhí)行數(shù)沒有變化；未優(yōu)化方案的所有指令執(zhí)行均只需一個時鐘周期，而優(yōu)化方案只有取/存指令需二個時鐘 周期，其它需一個時鐘周期。試計算：（1）優(yōu)化方案的平均CPI （2分）；（2）優(yōu)化方案的加速比（4分）。四、（6分）設(shè)有一個15000條指令的程序在一臺時鐘速率為25MHz的線性流水線處理機上執(zhí)行。假設(shè)該 指令流水線為5段，并且每個時鐘周期發(fā)射一條指令，忽略由于轉(zhuǎn)移指令和無序執(zhí)行造成的損（1）用該流水線執(zhí)行這一程序，并用流過延遲與其相等的一個等效非流水線處理機執(zhí)行同一程序，將兩者加以比較并計算其加速比。（2分）（2）該流水線處理機的效率是多少？ （2分）（3）該

12、流水線處理機的吞吐率是多少？ （2分）五、（6分）一臺模擬機共有7條指令，各指令的使用頻度分別為35強，25%, 20%, 10%, 5%, 3%, 2%。該 模擬機有8位和16位兩種指令長，采用2-4擴展操作碼，8位字長指令為寄存器-寄存器（R-R） 二地址類型，16位字長指令為寄存器-存貯器（R-M）二地址變址尋址（-128W變址范圍W127 ） 類型。（1）計算操作碼的平均碼長（2分）；（2）該機允許使用多少個可編址的通用寄存器，多少個變址寄存器？ （2分）設(shè)計該機的兩種指令格式，標出各字段位數(shù)并給出操作碼編碼。（2分）參考解答1999年試卷解答名詞解釋P9.加快經(jīng)常性事件原理（李學(xué)干教

13、材第1章）在同一時刻或同一時間間隔內(nèi)進行一種以上的操作P13.時間局部性/空間局部性P554.將分布存儲MIMD系統(tǒng)虛擬成共享MIMD系統(tǒng)P528.由許多局部存儲器組成全局地址空間計算CPI=1. 57設(shè)原指令總數(shù)為M,則新指令總數(shù)為M - 0.43MX0.25=0.8925M,各種指令的新比例如下指令系統(tǒng)指令所占比例CPI舊算邏指令(0. 43M-0. 43MX0. 25)/0.8925M0. 36131新算邏指令(0. 43MX0. 25)/0.8925M0. 12042Load指令(0. 21M-0. 43MX0. 25)/0.8925M0. 11482Store指令0. 12M/0.8

14、925M0. 13482轉(zhuǎn)移指令0. 24M/0.8925M0. 26893CPI* e 1. 9076計算任務(wù)劃分如下:時空圖如下:空間S6 s5 S4 s3 s2 Si1234567891011叵1314間12345678910123456789101112131411121314時123456789101112131422 AtTk = 22At, TP = 7/11 At, S = 28/lb E = 14/33四.計算1.如下圖所示主存（虛）地址四.計算1.如下圖所示主存（虛）地址15位:虛組號5位組內(nèi)塊號4位塊內(nèi)偏移量6位緩存（實）地址13位:實組號3位 組內(nèi)塊號4位 塊內(nèi)偏移量6

15、位己知 Tl = 20ns, H = 0.95, Sp = T2 / T 10,求 T2。將公式T = HXT1 + (1-H)X T2代入上式， 得 T2 / 10 H X T1+ (1 - H) X T2, 整理得 T2 H X Tl/(0. 1 - (1 - H) = 380ns2000年試卷解答名詞解釋 TOC o 1-5 h z P16P16P500P394P607計算P102P348P195計算(用Amdahl定律)由 80 = 1/(1-F) + F/100),得 F = 790/792 e 99. 7%Sn = 1/( (1-F) + F/50) = 7920/178 R 44

16、. 49加速效率參見李學(xué)干教材第7章Eioo = Sioo/100 = 80/100 = 80% Eso = 7920/178/50 e 89%計算(向量流水線)照抄教材P388-P389的例題計算按“最久沒有使用算法”作圖t =123456789101112命中次數(shù)p =232152453252LFU22222*222*333*3*5333*555*555*55111*444*222入入中入換中換中換換中中頁命中率H1 = 5/12 R 42%單元命中率 H2 = (12X32 - 7)/12X32 e 98%2001年試卷解答名詞解釋 TOC o 1-5 h z P15P399P541P2

17、95P121填空P147虛存空間，實存空間，虛地址，主存實地址P112 20%, 80%P350存儲器-存儲器，寄存器-寄存器P283靜態(tài)流水線，動態(tài)流水線P6 SIMD, MISD, MIMD?計算（用Amdahl定律）CPI = 1.6MIPS = 31. 25計算（就是將教材P346第18題1、2小問中8X8改成6X6,其它相同）6分析：計算每個結(jié)果元素都需要計算勺=Z（。注，燈），共計6次乘法和5次加法。Jt=i外層循環(huán)i = 16, j = 16順序方式：T 乘=T 加=5At, To = （6XT 乘 + 5XT 力口）X36 = 1980 At = 39600ns指令級流水線分3

18、段（取指、分析、執(zhí)行），操作級流水線也分3段。注意在操作級乘法與加 法不能重疊。先做6X36次乘法，再做5X36次加法，彼此之間均無相關(guān)存在。5X36次加法6X365X36次加法3 2 1行行行析指執(zhí)執(zhí)執(zhí)分取取指3 2 1行行行析指執(zhí)執(zhí)執(zhí)分取取指6X36+3-15X36+3-1Tk = 402 A t = 8040ns計算（題目沒有抄正確，含義不清）1.等效命中率H_指令命中次數(shù)+數(shù)據(jù)命中次數(shù)一總訪問次麴V=指令比例x指令命中率+數(shù)據(jù)比例x數(shù)據(jù)命中率2.名詞解釋phP131, P172 TOC o 1-5 h z P269P402P451填空P5第4段 邏輯實現(xiàn)，物理實現(xiàn)6ns I10 X 2

19、nsP193 23.57 (己知 Tm/Tc = 5, H = 0. 9)6ns I10 X 2nsP238第2段選擇通道，數(shù)組多路通道P304第4段(P307-P308也有)先寫后讀，先讀后 寫26ns (見右圖)2 (shuffle(shuffle(1000B) = 0010B)計算設(shè)原指令總數(shù)為M,其中取/存指令為第1類，其它指令為第2類。1.優(yōu)化前，IC=M =03M + 0.7M, C/7 = JWxl +業(yè)竺xl = l ,時鐘周期為 CYCLE：M M優(yōu)化后，/C=ZxO.3M+O.7M = O.9M,x2 + xl =旦 1.22 ,時鐘周30.9M0.9M0.9期為 0.85XCYCLEe T ICxCPIxCYCLE MxlxCYCLE12. S ,)=a 1.07p T： ICxCPIxCY