并行計(jì)算試卷

2003?2004學(xué)年 秋 季學(xué)期試卷 課程名:計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與并行處理（一）學(xué)分：_4_ ~成 學(xué)號(hào)： 姓名： 院：計(jì)算機(jī)學(xué)院績(jī) 一. 填充題：（每小題3分、共12分） 1 ?計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)定義是程序設(shè)計(jì)者所看到的計(jì)算機(jī)屬性，即概念性，結(jié)構(gòu)，功能性。 2. 虛擬存儲(chǔ)系統(tǒng)，輔存容量為228Byte,主存容量為216Byte,頁(yè)面為1Kbyte,則MEM 系統(tǒng)提供的程序空間有 頁(yè)，對(duì)應(yīng)實(shí)存空間 26 頁(yè)，若 采用組相聯(lián)，則整個(gè)虛存應(yīng)分為 212 區(qū)。 3. 流水線結(jié)構(gòu)的并行性是采用 的技術(shù)途徑。 4?在系統(tǒng)結(jié)構(gòu)中，程序訪問局部化性質(zhì)應(yīng)用于 cache ， ， 虛擬存儲(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ī)器。 2?存儲(chǔ)器層次結(jié)構(gòu)是怎樣的？其容量、速度、價(jià)格是怎樣分布的。 速度越來越 快，價(jià)格越 來越高 寄存器組 cache 主存儲(chǔ)器 輔助存儲(chǔ)器 后援存儲(chǔ)器 3. 簡(jiǎn)述虛擬計(jì)算機(jī)概念。 計(jì)算機(jī)只對(duì)觀察者而存在；功能體現(xiàn)在廣義語(yǔ)言上；對(duì)該語(yǔ)言提供解釋手段；作用在信息處理或控 制對(duì)象上；簡(jiǎn)言之，是由軟件實(shí)現(xiàn)的機(jī)器。 4. What 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. 5.什么是“數(shù)據(jù)相關(guān)” “轉(zhuǎn)移相關(guān)”？簡(jiǎn)述之。 數(shù)據(jù)相關(guān)：當(dāng)前一條指令的執(zhí)行結(jié)果可能在流水線中是后續(xù)指令的操作數(shù)，它們可能發(fā)生了 “先讀 后寫”等相關(guān)。它是一種局部相關(guān)。 轉(zhuǎn)移相關(guān)：由轉(zhuǎn)移指令引起流水線“斷流”這是一種全局相關(guān) 6.先行控制結(jié)構(gòu)中有那些緩沖棧組成？分別敘述其功能。 先行指令棧：讀取后援指令，保證指令分析器能夠順序取指。 現(xiàn)行讀數(shù)棧：讀出的數(shù)據(jù)放在該棧，運(yùn)算器直接從其讀取數(shù)據(jù)進(jìn)行操作。 先行操作棧：指令分析器預(yù)處理萬(wàn)一條指令，就將相應(yīng)操作命令送入該棧，而執(zhí)行部件從棧內(nèi)按順 序逐步取出操作命令執(zhí)行。 后行寫數(shù)據(jù)棧：每當(dāng)接到運(yùn)算器送來的要寫入主存的數(shù)據(jù)，由控制邏輯自動(dòng)向主存發(fā)寫數(shù)請(qǐng)求，完 成存數(shù)的操作。 三.某機(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.30 0000 00 00 0.14 0001 010 01 0.13 0010 011 1000 0.12 0011 100 1001 0.12 0100 101 1010 0.06 0101 1100 1011 0.05 0110 1101 1100 0.04 0111 1110 1101 0.03 1000 11110 1110 0.01 1001 11111 1111 平均碼長(zhǎng) 4 2.93 3.12 四.主存有4個(gè)模塊，每塊大小為1K字節(jié)，若采用低位交叉編址方式 （1） 請(qǐng)畫出地址劃分示意圖。 （2） 設(shè)已知存儲(chǔ)單元地址A=OFFEH,請(qǐng)?jiān)诘刂穭澐质疽鈭D上標(biāo)明A的位置。（10分） M1 M2 M4 0000 0001 0002 0003 0004 0005 0006 0007 0FFC 0FFD 0FFE A 0FFF 五?有一個(gè)Cache—主存層次：主存分8塊（0?7）, Cache為4塊（0?3）,塊大小為 5, 4, 1, 2, 6, 5, 6, 0, 2。 畫出主存-Cache映象圖和地址對(duì)應(yīng)示意圖。標(biāo)出地址各字段的位數(shù)。 試用LRU和OPT替換算法，分別畫出替換示意圖、求出命中率H。（14分） 1KB。采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊。已知頁(yè)面地址流為2, 7, 4, 2, 0, 1, A 2 7 4 2 0 1 5 4 1 2 6 5 6 0 2 0 組 4 4 4* 1 1* 4 4* 4* 4* 5 5 5* 5* 0 0* 5 5* 1 1 1 1* 1* 0 0 1 組 2 2* 2* 2H 2 2 2 2 2 2 2H 2** 2* 2* 2H 7 7 7* 7* 7* 7* 7* 7* 7* 6 6 6H 6 6* (1) (2) LRU： 4 H=15 OPT： A 2 7 4 2 0 1 5 4 1 2 6 5 6 0 2 0 組 4 4 4 4 4 4*H 1* 1* 1* 1* 1* 0 0 0* 1* 5* 5 5 5 5 5H 5 5* 5* 1 組 2 2 2 2H 2 2 2 2 2 2H 2* 2* 2 2 2H 7* 7* 7* 7* 7* 7* 7* 7* 7* 6 6 6H* 6* 6* 6 H=15 六.設(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分） 3 1 2 3 4 1 2F 2 4 2 2E 1 3 4 1 2 1 1 2 3 4 1 2 3 cache 1 2 3 4 1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 I 11t 1 12t 24 E= =43.64% 11*5 4 TP= =3.64MIPS P 11 第8頁(yè)（共8頁(yè)） 七.假設(shè)一個(gè)4段流水線（其時(shí)鐘周期T =20 ns）的預(yù)約表如下，要求： （1） 寫出禁止等待時(shí)間和初始沖突向量Co。 （2） 畫出調(diào)度該流水線的狀態(tài)變換圖。 （3） 確定與最佳迫切循環(huán)相關(guān)聯(lián)MAL。 （4） 確定與MAL和給定的T對(duì)應(yīng)的流水線吞吐率。（15分） X X X X X X X X （1） S1禁止時(shí)間 3. 5 2 S2禁止時(shí)間 2 S3禁止時(shí)間 2 禁止時(shí)間2，3，5允許時(shí)間1， 4 初始沖突向量C0={10110} （2） 10110 10111 11111 (3) MAL=(1,6)=3.5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 S1 X1 X2 X1 X2 X1 X2 X3 X4 X3 X4 X3 X4 S2 X1 X2 X1 X2 X3 X4 X3 X4 S3 X1 X2 X3 X4 S4 X1 X2 X1 X2 X3 X4 X3 X4 Hp =2/(7*T )=14.2MIPS 上海大學(xué)2003?2004學(xué)年 冬 季學(xué)期試卷 課程名：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與并行處理（二）_學(xué)分:_4 ~成 學(xué)號(hào)： 姓名： 院系： 績(jī) 題號(hào) —一 二 三 四 五 六 七 八 得分 得 1 1 分1__ 一.填充題: （共15分，每空1分） 1. 網(wǎng)格（Grid）技術(shù)是20世紀(jì)90年代中期隨著 和 分布式計(jì)算技術(shù) 的不斷發(fā)展而誕生的一種全新技術(shù)。 2?計(jì)算模型的四種驅(qū)動(dòng)方式是控制驅(qū)動(dòng)、數(shù)據(jù)驅(qū)動(dòng)、需求驅(qū)動(dòng)和模式匹配驅(qū)動(dòng)。 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ò)化。 二、簡(jiǎn)答題：（共20分） 1.請(qǐng)畫圖表示兩種并行處理機(jī)的結(jié)構(gòu)（6分） 見書上138圖5—2 5 — 3 2. 簡(jiǎn)述集群系統(tǒng)的概念。（5分） 集群系統(tǒng)是利用高速通信網(wǎng)絡(luò)將一組高性能工作站或高檔PC機(jī)連接起來，在并行程序 設(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é)作。 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í)行。 得 三.綜合題(65分) 分 1.如FP操作比例為35%, FP的CPI=4.5，其它指令CPI=1.6。FPSQR操作 比例為5%, FPSQR的CPI=20。有二種方案：方案1：把所有FP的CPI 減為2；方案2：把FPSQR的CPI減為6。要求：(a)試比較二種方案的 CPI。(b)計(jì)算二種方案的加速比。(10分) CPI=4.5*35%+1.6*65%=2.615 方案1 CPI1=CPI-(CPI 原 FP-CPI 新 FP)X35%=2.615-(4.5-2)*35%=1.74 (另外方法：2X35% = 1。6X65%=0。7+1。04 = 1。74) S1=CPI/CPI1=2.615/1.776=1.5 方案2 CPI2=CPI-(CPI 原 FPSQR-CPI 新 FPSQR) X 5%=2.615-(20-6)*5%=1.915 S2=CPI/CPI2=2.615/1.915=1.366 方案1好 （10 分） 2、請(qǐng)用J.B.Dennis和J.E.Rumbaugh提出的數(shù)據(jù)流程序圖描述下列語(yǔ)句: if true then (a+b) 2 else (a*c)/d 3、已知16個(gè)節(jié)點(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 s 十 d=1101 s0 十 d0=0 十 1=1 s1 十 d1=1 十 1=0 s2 十 d2=0 十 1=1 V = s 十 1=1011 跳過 V=V 十 100=1011 十 100=1111 V=V 十 1000=1111 十 1000 = 0111 s3 十 d3=1 十 0=1 4、已知算術(shù)表達(dá)式E=a-[b（c-de+f-g）+h],現(xiàn)用3個(gè)處理機(jī)的并行系統(tǒng)處理。要求: 試壓縮樹高來開發(fā)該式并行性。求出P、Tp、Sp、Ep。 （10 分） d e d e T 串=7 Tp=4 P=3 Sp= T 串/Tp=7/4 Ep= Sp/p=7/12 5、參照如下圖算法，要求： (1) 寫出原始運(yùn)算表達(dá)式 (2) 寫出S],S2???Sn的操作內(nèi)容 (3) 用FORK、JOIN語(yǔ)句編寫并行程序。(10分) h— z rT' < / a / \ b \ / c Q /、 d \ / e / A / f g h h-(a*b+c/d) +a*(e+f)+b/(g-h) s1: I=a*b FORK s2 JOIN 4 JOIN 3 S10 Z=Q+R s2: J=c/d FORK s3 GOTO S5 GOTO S8 s3: K=e+f FORK s4 S4 L=g-h S7 O=b/L S4: L=g-h S1 I=a*b JOIN 4 JOIN 3 S5: M=I+J JOIN 4 S5 FORK s6 S8 FORK s9 S6: N=a*K GOTO S5 FORK s7 Q=h-M S7: O=b/L s2 J=c/d M=I+J JOIN 2 S8: Q=h-M JOIN 4 JOIN 3 GOTO S10 S9: R=N+O GOTO S5 GOTO S8 S9 R=N+O S10: Z=Q+R S3 K=e+f S6 N=a*K JOIN 2 6、現(xiàn)有8個(gè)處理機(jī)，編號(hào)分別為0~7,用多級(jí)互聯(lián)網(wǎng)絡(luò)連接。規(guī)定2級(jí)用PM2-2，1 級(jí)用 Shuffle(Shuffle), 0 級(jí)用 Cubel。要求： (a) 分別列出PM2-2，Shuffle(Shuffle)，Cubel時(shí)，處理機(jī)0?7互連編號(hào)。 (b) 畫出各級(jí)互聯(lián)網(wǎng)絡(luò)圖。 (c) 在圖中畫出編號(hào)5連通到編號(hào)3的路徑，并標(biāo)出開關(guān)狀態(tài)。 （15 分） Cube1