并行計算試卷

《并行計算試卷》由會員分享，可在線閱讀，更多相關(guān)《并行計算試卷（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2003?2004學(xué)年 秋 季學(xué)期試卷 課程名:計算機系統(tǒng)結(jié)構(gòu)與并行處理（一）學(xué)分：_4_ ~成 學(xué)號： 姓名： 院：計算機學(xué)院績 一. 填充題：（每小題3分、共12分） 1 ?計算機系統(tǒng)結(jié)構(gòu)定義是程序設(shè)計者所看到的計算機屬性，即概念性，結(jié)構(gòu)，功能性。 2. 虛擬存儲系統(tǒng)，輔存容量為228Byte,主存容量為216Byte,頁面為1Kbyte,則MEM 系統(tǒng)提供的程序空間有 頁，對應(yīng)實存空間 26 頁，若 采用組相聯(lián)，則整個虛存應(yīng)分為 212 區(qū)。 3. 流水線結(jié)構(gòu)的并行性是采用 的技術(shù)途徑。 4?在系統(tǒng)結(jié)構(gòu)中，程序訪問局部化性質(zhì)應(yīng)用于 cache ， ， 虛擬

2、存儲器 等方面。 二. 簡答題：（每小題4分、共24分） 1.簡述系列機的概念。 先設(shè)計一種系統(tǒng)結(jié)構(gòu)；按其設(shè)計它的系統(tǒng)軟件；按照器件狀況和硬件技術(shù)，研究這種結(jié)構(gòu)的各種 實現(xiàn)方法；按速度，價格等不同要求分別提供不同速度，不同配置的各檔機器。 2?存儲器層次結(jié)構(gòu)是怎樣的？其容量、速度、價格是怎樣分布的。 速度越來越 快，價格越 來越高 寄存器組 cache 主存儲器 輔助存儲器 后援存儲器 3. 簡述虛擬計算機概念。 計算機只對觀察者而存在；功能體現(xiàn)在廣義語言上；對該語言提供解釋手段；作用在信息處理

3、或控 制對象上；簡言之，是由軟件實現(xiàn)的機器。 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)”？簡述之。 數(shù)據(jù)相關(guān)：當前一條指令的執(zhí)行結(jié)果可能在流水線中是后續(xù)指

4、令的操作數(shù)，它們可能發(fā)生了 “先讀 后寫”等相關(guān)。它是一種局部相關(guān)。 轉(zhuǎn)移相關(guān)：由轉(zhuǎn)移指令引起流水線“斷流”這是一種全局相關(guān) 6.先行控制結(jié)構(gòu)中有那些緩沖棧組成？分別敘述其功能。 先行指令棧：讀取后援指令，保證指令分析器能夠順序取指。 現(xiàn)行讀數(shù)棧：讀出的數(shù)據(jù)放在該棧，運算器直接從其讀取數(shù)據(jù)進行操作。 先行操作棧：指令分析器預(yù)處理萬一條指令，就將相應(yīng)操作命令送入該棧，而執(zhí)行部件從棧內(nèi)按順 序逐步取出操作命令執(zhí)行。 后行寫數(shù)據(jù)棧：每當接到運算器送來的要寫入主存的數(shù)據(jù)，由控制邏輯自動向主存發(fā)寫數(shù)請求，完 成存數(shù)的操作。 三.某機有10條指令，其使用頻度分別為0.14, 0.12, 0.1

5、2, 0.03, 0.05, 0.06, 0.04, 0.13, 0.30, 0.01。 要求：（a）畫出Hafuman編碼的二叉樹。（b）寫出等長二進制編碼，Hafuman編碼， 2-4擴展編碼。（c）計算三種編碼的平均碼長。（15分） I 二進制編碼 Haffman 碼 2-4擴展編碼 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

6、1101 1100 0.04 0111 1110 1101 0.03 1000 11110 1110 0.01 1001 11111 1111 平均碼長 4 2.93 3.12 四.主存有4個模塊，每塊大小為1K字節(jié)，若采用低位交叉編址方式 （1） 請畫出地址劃分示意圖。 （2） 設(shè)已知存儲單元地址A=OFFEH,請在地址劃分示意圖上標明A的位置。（10分） M1 M2 M4 0000 0001 0002 0003

7、 0004 0005 0006 0007 0FFC 0FFD 0FFE A 0FFF 五?有一個Cache—主存層次：主存分8塊（0?7）, Cache為4塊（0?3）,塊大小為 5, 4, 1, 2, 6, 5, 6, 0, 2。 畫出主存-Cache映象圖和地址對應(yīng)示意圖。標出地址各字段的位數(shù)。 試用LRU和OPT替換算法，分別畫出替換示意圖、求出命中率H。（14分） 1KB。采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊。已知頁面地址流為2, 7

8、, 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

9、 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ù)處理流水線，如圖所

10、示。Cache每送出4個數(shù)據(jù)后，間隔400ns再送出4 個數(shù)據(jù)，連續(xù)不斷。請畫出此條件下，包括Cache在內(nèi)的處理過程時一空圖，并求出 其效率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

11、 16 17 18 I 11t 1 12t 24 E= =43.64% 11*5 4 TP= =3.64MIPS P 11 第8頁（共8頁） 七.假設(shè)一個4段流水線（其時鐘周期T =20 ns）的預(yù)約表如下，要求： （1） 寫出禁止等待時間和初始沖突向量Co。 （2） 畫出調(diào)度該流水線的狀態(tài)變換圖。 （3） 確定與最佳迫切循環(huán)相關(guān)聯(lián)MAL。 （4） 確定與MAL和給定的T對應(yīng)的流水線吞吐率。（15分） X X X X X X X X （1） S1禁止時間 3. 5 2

12、S2禁止時間 2 S3禁止時間 2 禁止時間2，3，5允許時間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

13、 X3 X4 S4 X1 X2 X1 X2 X3 X4 X3 X4 Hp =2/(7*T )=14.2MIPS 上海大學(xué)2003?2004學(xué)年 冬 季學(xué)期試卷 課程名：計算機系統(tǒng)結(jié)構(gòu)與并行處理（二）_學(xué)分:_4 ~成 學(xué)號： 姓名： 院系： 績 題號 —一 二 三 四 五 六 七 八 得分 得 1 1 分1__ 一.填充題: （共15分，每空1分） 1. 網(wǎng)格（Grid）技術(shù)是20世紀90年代中期隨著 和 分布式計算技

14、術(shù) 的不斷發(fā)展而誕生的一種全新技術(shù)。 2?計算模型的四種驅(qū)動方式是控制驅(qū)動、數(shù)據(jù)驅(qū)動、需求驅(qū)動和模式匹配驅(qū)動。 3. RISC結(jié)構(gòu)中采用的三種流水線結(jié)構(gòu)是超標量結(jié)構(gòu)、 超流水線結(jié)構(gòu)和超長指令字（VLIW）結(jié)構(gòu)。 4. 單機系統(tǒng)實現(xiàn)并行處理的途徑是時間重疊、資源重復(fù)、資源共享。多機系統(tǒng)實現(xiàn)并 行處理的途徑是功能專用化、機間互聯(lián)、網(wǎng)絡(luò)化。 二、簡答題：（共20分） 1.請畫圖表示兩種并行處理機的結(jié)構(gòu)（6分） 見書上138圖5—2 5 — 3 2. 簡述集群系統(tǒng)的概念。（5分） 集群系統(tǒng)是利用高速通信網(wǎng)絡(luò)將一組高性能工作站或高檔PC機連接起來，在并行程序 設(shè)計和集成開發(fā)環(huán)境支

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

16、如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)計算二種方案的加速比。(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.

17、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、請用J.B.Dennis和J.E.Rumbaugh提出的數(shù)據(jù)流程序圖描述下列語句: if true then (a+b) 2 else (a*c)/d 3、已知16個節(jié)點的超立方體網(wǎng)絡(luò)，要求用E立方體尋徑算法，計算從源節(jié)點（1010） 到目的節(jié)點（0111）的路徑，寫出計算過程，畫出網(wǎng)絡(luò)拓撲圖，并在圖上用箭頭標出 路徑。（10分） s=1010 d=01

18、11 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ù)表達式E=a-[b（c-de+f-g）+h],現(xiàn)用3個處理機的并行系統(tǒng)處理。要求: 試壓縮樹高來開發(fā)該式并行性。求出P、Tp、Sp、Ep。 （10 分） d e d e T 串=7 Tp=4 P=3 Sp= T 串/Tp=7/4 Ep=

19、 Sp/p=7/12 5、參照如下圖算法，要求： (1) 寫出原始運算表達式 (2) 寫出S],S2???Sn的操作內(nèi)容 (3) 用FORK、JOIN語句編寫并行程序。(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

20、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 GOT

21、O S8 S9 R=N+O S10: Z=Q+R S3 K=e+f S6 N=a*K JOIN 2 6、現(xiàn)有8個處理機，編號分別為0~7,用多級互聯(lián)網(wǎng)絡(luò)連接。規(guī)定2級用PM2-2，1 級用 Shuffle(Shuffle), 0 級用 Cubel。要求： (a) 分別列出PM2-2，Shuffle(Shuffle)，Cubel時，處理機0?7互連編號。 (b) 畫出各級互聯(lián)網(wǎng)絡(luò)圖。 (c) 在圖中畫出編號5連通到編號3的路徑，并標出開關(guān)狀態(tài)。 （15 分） Cube1