計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與并行處理(共23頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第 1 頁 ( 共 8 頁 )大學(xué) 2003 2004 學(xué)年 秋 季學(xué)期試卷 課程名:計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與并行處理(一) 學(xué)分：_4_學(xué)號(hào)：_ 姓名：_ 院：計(jì)算機(jī)學(xué)院一 填充題：（每小題3分、共12分）1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)定義是程序設(shè)計(jì)者所看到的計(jì)算機(jī)屬性，即概念性，結(jié)構(gòu)，功能性。 2虛擬存儲(chǔ)系統(tǒng)，輔存容量為228Byte，主存容量為216Byte，頁面為1Kbyte，則MEM系統(tǒng)提供的程序空間有 218 頁，對(duì)應(yīng)實(shí)存空間 26 頁，若采用組相聯(lián)，則整個(gè)虛存應(yīng)分為 212 區(qū)。3流水線結(jié)構(gòu)的并行性是采用 時(shí)間重迭 的技術(shù)途徑。 4在系統(tǒng)結(jié)構(gòu)中，程序訪問局部化性質(zhì)應(yīng)用于 ca

2、che ， 流水線， 虛擬存儲(chǔ)器 等方面。二 簡(jiǎn)答題：（每小題4分、共24分）1 簡(jiǎn)述系列機(jī)的概念。先設(shè)計(jì)一種系統(tǒng)結(jié)構(gòu)；按其設(shè)計(jì)它的系統(tǒng)軟件； 按照器件狀況和硬件技術(shù)，研究這種結(jié)構(gòu)的各種實(shí)現(xiàn)方法； 按速度，價(jià)格等不同要求分別提供不同速度，不同配置的各檔機(jī)器。成績(jī)命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 2 頁 ( 共 8 頁 )2存儲(chǔ)器層次結(jié)構(gòu)是怎樣的？其容量、速度、價(jià)格是怎樣分布的。3簡(jiǎn)述虛擬計(jì)算機(jī)概念。計(jì)算機(jī)只對(duì)觀察者而存在；功能體現(xiàn)在廣義語言上；對(duì)該語言提供解釋手段；作用在信

3、息處理或控制對(duì)象上；簡(jiǎn)言之，是由軟件實(shí)現(xiàn)的機(jī)器。4What is the policy of “write back” when writing to the cache? (answer in English)The information is written only to the block in the cache.The modified cache block is written to main memory only when it is replaced. 第 3 頁 ( 共 8 頁 )5什么是“數(shù)據(jù)相關(guān)”、“轉(zhuǎn)移相關(guān)”？ 簡(jiǎn)述之。數(shù)據(jù)相關(guān)：當(dāng)前一條指令的執(zhí)行結(jié)果可能在流水

4、線中是后續(xù)指令的操作數(shù)，它們可能發(fā)生了“先讀后寫”等相關(guān)。它是一種局部相關(guān)。轉(zhuǎn)移相關(guān)：由轉(zhuǎn)移指令引起流水線“斷流”。 這是一種全局相關(guān)6先行控制結(jié)構(gòu)中有那些緩沖棧組成？分別敘述其功能。先行指令棧：讀取后援指令，保證指令分析器能夠順序取指?，F(xiàn)行讀數(shù)棧：讀出的數(shù)據(jù)放在該棧，運(yùn)算器直接從其讀取數(shù)據(jù)進(jìn)行操作。先行操作棧：指令分析器預(yù)處理萬一條指令，就將相應(yīng)操作命令送入該棧，而執(zhí)行部件從棧內(nèi)按順序逐步取出操作命令執(zhí)行。后行寫數(shù)據(jù)棧：每當(dāng)接到運(yùn)算器送來的要寫入主存的數(shù)據(jù)，由控制邏輯自動(dòng)向主存發(fā)寫數(shù)請(qǐng)求，完成存數(shù)的操作。命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證

5、“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 4 頁 ( 共 8 頁 )三 某機(jī)有10條指令，其使用頻度分別為0.14，0.12，0.12，0.03，0.05，0.06，0.04，0.13， 0.30， 0.01。要求：(a) 畫出Hafuman編碼的二叉樹。 (b) 寫出等長(zhǎng)二進(jìn)制編碼，Hafuman編碼，2-4擴(kuò)展編碼。 (c) 計(jì)算三種編碼的平均碼長(zhǎng)。（15分）I二進(jìn)制編碼Haffman碼2-4擴(kuò)展編碼0.30000000000.140001010010.13001001110000.12001110010010.12010010110100.06010111001

6、0110.050110110111000.040111111011010.0310001111011100.011001111111111平均碼長(zhǎng)42.933.12 第 5 頁 ( 共 8 頁 )四主存有4個(gè)模塊，每塊大小為1K字節(jié)，若采用低位交叉編址方式 （1） 請(qǐng)畫出地址劃分示意圖。（2） 設(shè)已知存儲(chǔ)單元地址A=0FFEH，請(qǐng)?jiān)诘刂穭澐质疽鈭D上標(biāo)明A的位置。（10分）命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 6 頁 ( 共 8 頁 )五有一個(gè)Cache主存層次：主存分8塊（07

7、），Cache為4塊（03），塊大小為1KB。采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊。已知頁面地址流為2，7，4，2，0，1，5，4，1，2，6，5，6，0，2。（1） 畫出主存-Cache映象圖和地址對(duì)應(yīng)示意圖。標(biāo)出地址各字段的位數(shù)。（2） 試用LRU和OPT替換算法，分別畫出替換示意圖、求出命中率H。（14分）LRU：A2742015412656020組444*11*44*4*4*555*5*00*55*1111*1*001組22*2*2H2222222H2*2*2*2H777*7*7*7*7*7*7*666H66*H=OPT：A2742015412656020組444444*H1*1*1*1*1

8、*000*1*5*55555H55*5*1組2222H222222H2*2*222H7*7*7*7*7*7*7*7*7*666H*6*6*H= 第 7 頁 ( 共 8 頁 )六設(shè)有數(shù)據(jù)處理流水線，如圖所示。Cache 每送出4個(gè)數(shù)據(jù)后，間隔400ns再送出4個(gè)數(shù)據(jù)，連續(xù)不斷。請(qǐng)畫出此條件下，包括Cache在內(nèi)的處理過程時(shí)空?qǐng)D，并求出其效率E和吞吐率TP。（10分）3123412F2422E1341211234123cache1234123123456789101112131415161718 |11t| | 12t| E=43.64%TP=3.64MIPS命題紙使用說明：1、字跡必須端正，以黑

9、色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 8 頁 ( 共 8 頁 )七 假設(shè)一個(gè)4段流水線（其時(shí)鐘周期=20 ns）的預(yù)約表如下，要求：（1） 寫出禁止等待時(shí)間和初始沖突向量C0。（2） 畫出調(diào)度該流水線的狀態(tài)變換圖。（3） 確定與最佳迫切循環(huán)相關(guān)聯(lián)MAL。（4） 確定與MAL和給定的對(duì)應(yīng)的流水線吞吐率。（15分）（1）S1 禁止時(shí)間 3. 5 2S2禁止時(shí)間 2 S3禁止時(shí)間 2 禁止時(shí)間2，3，5 允許時(shí)間 1， 4初始沖突向量C0=10110（2）（3）MAL=(1,6)=3.512345678910111213

10、141516S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X3X4S4X1X2X1X2X3X4X3X4HP =2/(7*)=14.2MIPS 第 8 頁 ( 共 1 頁 )上海大學(xué) 2003 2004學(xué)年 冬 季學(xué)期試卷課程名：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與并行處理(二)_學(xué)分： 4_學(xué)號(hào)：_ 姓名：_ 院系：_題號(hào)一二三四五六七八得分一填充題：（共15分, 每空1分）1 網(wǎng)格（Grid）技術(shù)是20世紀(jì)90年代中期隨著 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù) 和 分布式計(jì)算技術(shù) 的不斷發(fā)展而誕生的一種全新技術(shù)。2計(jì)算模型的四種驅(qū)動(dòng)方式是控制驅(qū)動(dòng)、數(shù)據(jù)驅(qū)動(dòng)、需求驅(qū)動(dòng)和模式匹配驅(qū)動(dòng)

11、。 3 RISC結(jié)構(gòu)中采用的三種流水線結(jié)構(gòu)是超標(biāo)量結(jié)構(gòu)、超流水線結(jié)構(gòu)和超長(zhǎng)指令字（VLIW）結(jié)構(gòu)。4單機(jī)系統(tǒng)實(shí)現(xiàn)并行處理的途徑是時(shí)間重疊、資源重復(fù)、資源共享。多機(jī)系統(tǒng)實(shí)現(xiàn)并行處理的途徑是功能專用化、機(jī)間互聯(lián)、網(wǎng)絡(luò)化。成績(jī)命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 8 頁 ( 共 2 頁 )得分二、簡(jiǎn)答題：（共20分）1請(qǐng)畫圖表示兩種并行處理機(jī)的結(jié)構(gòu)（6分）見書上138 圖52 532簡(jiǎn)述集群系統(tǒng)的概念。（5分）集群系統(tǒng)是利用高速通信網(wǎng)絡(luò)將一組高性能工作站或高檔PC機(jī)連接起來，在并行程

12、序設(shè)計(jì)和集成開發(fā)環(huán)境支撐下統(tǒng)一調(diào)度、協(xié)調(diào)處理以實(shí)現(xiàn)高效并行處理的系統(tǒng)。集群系統(tǒng)中的主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的，主要利用消息傳遞方式實(shí)現(xiàn)機(jī)間的通信，由建立在一般的操作系統(tǒng)上的并行編程環(huán)境完成系統(tǒng)的資源管理及相互協(xié)作。第 8 頁 ( 共 3 頁 )3 簡(jiǎn)述計(jì)算機(jī)性能評(píng)價(jià)和計(jì)算機(jī)性能測(cè)量的定義（4分）計(jì)算機(jī)性能評(píng)價(jià)是指計(jì)算機(jī)系統(tǒng)對(duì)原始數(shù)據(jù)進(jìn)行邏輯推算。計(jì)算機(jī)性能測(cè)量是指采用基準(zhǔn)測(cè)試程序包來度量計(jì)算機(jī)系統(tǒng)的性能。4簡(jiǎn)述數(shù)據(jù)流計(jì)算機(jī)工作原理。（5分）數(shù)據(jù)流計(jì)算機(jī)沒有程序計(jì)數(shù)器，沒有中央控制器，指令的執(zhí)行由數(shù)據(jù)來驅(qū)動(dòng)，把控制流變?yōu)閿?shù)據(jù)流。當(dāng)指令所需數(shù)據(jù)可用時(shí)，指令就可以執(zhí)行。命題紙使用說明：1

13、、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 8 頁 ( 共 4 頁 )得分三綜合題（65分）1如FP操作比例為35%，F(xiàn)P的CPI=4.5，其它指令CPI=1.6。FPSQR操作比例為5%，F(xiàn)PSQR的CPI=20。有二種方案： 方案1：把所有FP的CPI減為2；方案2：把FPSQR的CPI減為6。要求： (a) 試比較二種方案的CPI。(b) 計(jì)算二種方案的加速比。（10分） CPI=4.5*35%+1.6*65%=2.615方案1CPI1=CPI-(CPI原FP-CPI新FP)×352.

14、615-(4.5-2)*35%=1.74(另外方法：2×351。6×650。71。041。74)S1=CPI/CPI1=2.615/1.776=1.5方案2CPI2=CPI-(CPI原FPSQR-CPI新FPSQR)×52.615-(20-6)*5%=1.915S2=CPI/CPI2=2.615/1.915=1.366方案1好2、請(qǐng)用J.B.Dennis和J.E.Rumbaugh提出的數(shù)據(jù)流程序圖描述下列語句：if true then （ab）2 else (a*c)/d（10分）b+/起始控制令牌dcaFTXXT F第 8 頁 ( 共 5 頁 )3、已知16個(gè)節(jié)

15、點(diǎn)的超立方體網(wǎng)絡(luò)，要求用E立方體尋徑算法，計(jì)算從源節(jié)點(diǎn)（1010）到目的節(jié)點(diǎn)（0111）的路徑，寫出計(jì)算過程，畫出網(wǎng)絡(luò)拓?fù)鋱D，并在圖上用箭頭標(biāo)出路徑。（10分）s=1010 d=0111 sd=1101s0d0=01=1 Vs1=1011s1d1=11=0 跳過s2d2=01=1 VV100=10111001111s3d3=10=1 VV1000=1111100001111011000000100011000101000101011001111000100110101100111011011111命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)

16、量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 8 頁 ( 共 6 頁 )4、已知算術(shù)表達(dá)式E=a-b(c-de+f-g)+h，現(xiàn)用3個(gè)處理機(jī)的并行系統(tǒng)處理。要求： 試壓縮樹高來開發(fā)該式并行性。求出P、Tp、Sp、Ep。（10分）T串7 Tp4 P3Sp= T串/ Tp=7/4Ep= Sp/p=7/12第 8 頁 ( 共 7 頁 )5、參照如下圖算法，要求：（1）寫出原始運(yùn)算表達(dá)式（2）寫出S1,S2Sn的操作內(nèi)容（3）用FORK、JOIN語句編寫并行程序。（10分） h-(a*b+c/d) +a*(e+f)+b/(g-h)s1:I=a*bFORK s2 JOIN 4JOIN 3S1

17、0 Z=Q+Rs2:J=c/dFORK s3 GOTO S5GOTO S8s3:K=e+fFORK s4S4 L=g-hS7 O=b/LS4:L=g-hS1 I=a*bJOIN 4JOIN 3S5:M=I+J JOIN 4S5 FORK s6S8 FORK s9S6:N=a*K GOTO S5 FORK s7 Q=h-MS7:O=b/Ls2 J=c/d M=I+JJOIN 2S8:Q=h-M JOIN 4JOIN 3GOTO S10S9:R=N+O GOTO S5GOTO S8S9 R=N+OS10:Z=Q+RS3 K=e+fS6 N=a*KJOIN 2命題紙使用說明：1、字跡必須端正，以黑色碳素墨水書寫在框線內(nèi)，文字與圖均不得剪貼，以保證“掃描”質(zhì)量；2、命題紙只作考試（測(cè)驗(yàn)）命題所用，不得移作他用。第 8 頁 ( 共 8 頁 )6、現(xiàn)