并行计算试卷

《并行计算试卷》由会员分享，可在线阅读，更多相关《并行计算试卷（18页珍藏版）》请在装配图网上搜索。

1、2003〜2004学年 秋 季学期试卷 课程名:计算机系统结构与并行处理（一）学分：_4_ ~成 学号： 姓名： 院：计算机学院绩 一. 填充题：（每小题3分、共12分） 1 •计算机系统结构定义是程序设计者所看到的计算机属性，即概念性，结构，功能性。 2. 虚拟存储系统，辅存容量为228Byte,主存容量为216Byte,页面为1Kbyte,则MEM 系统提供的程序空间有 页，对应实存空间 26 页，若 采用组相联，则整个虚存应分为 212 区。 3. 流水线结构的并行性是采用 的技术途径。 4•在系统结构中，程序访问局部化性质应用于 cache ， ， 虚拟

2、存储器 等方面。 二. 简答题：（每小题4分、共24分） 1.简述系列机的概念。 先设计一种系统结构；按其设计它的系统软件；按照器件状况和硬件技术，研究这种结构的各种 实现方法；按速度，价格等不同要求分别提供不同速度，不同配置的各档机器。 2•存储器层次结构是怎样的？其容量、速度、价格是怎样分布的。 速度越来越 快，价格越 来越高 寄存器组 cache 主存储器 辅助存储器 后援存储器 3. 简述虚拟计算机概念。 计算机只对观察者而存在；功能体现在广义语言上；对该语言提供解释手段；作用在信息处理

3、或控 制对象上；简言之，是由软件实现的机器。 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.什么是“数据相关” “转移相关”？简述之。 数据相关：当前一条指令的执行结果可能在流水线中是后续指

4、令的操作数，它们可能发生了 “先读 后写”等相关。它是一种局部相关。 转移相关：由转移指令引起流水线“断流”这是一种全局相关 6.先行控制结构中有那些缓冲栈组成？分别叙述其功能。 先行指令栈：读取后援指令，保证指令分析器能够顺序取指。 现行读数栈：读出的数据放在该栈，运算器直接从其读取数据进行操作。 先行操作栈：指令分析器预处理万一条指令，就将相应操作命令送入该栈，而执行部件从栈内按顺 序逐步取出操作命令执行。 后行写数据栈：每当接到运算器送来的要写入主存的数据，由控制逻辑自动向主存发写数请求，完 成存数的操作。 三.某机有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字节，若采用低位交叉编址方式 （1） 请画出地址划分示意图。 （2） 设已知存储单元地址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映象图和地址对应示意图。标出地址各字段的位数。 试用LRU和OPT替换算法，分别画出替换示意图、求出命中率H。（14分） 1KB。采用组相联映象，组内块数为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 六.设有数据处理流水线，如图所

10、示。Cache每送出4个数据后，间隔400ns再送出4 个数据，连续不断。请画出此条件下，包括Cache在内的处理过程时一空图，并求出 其效率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页） 七.假设一个4段流水线（其时钟周期T =20 ns）的预约表如下，要求： （1） 写出禁止等待时间和初始冲突向量Co。 （2） 画出调度该流水线的状态变换图。 （3） 确定与最佳迫切循环相关联MAL。 （4） 确定与MAL和给定的T对应的流水线吞吐率。（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 上海大学2003〜2004学年 冬 季学期试卷 课程名：计算机系统结构与并行处理（二）_学分:_4 ~成 学号： 姓名： 院系： 绩 题号 —一 二 三 四 五 六 七 八 得分 得 1 1 分1__ 一.填充题: （共15分，每空1分） 1. 网格（Grid）技术是20世纪90年代中期随着 和 分布式计算技

14、术 的不断发展而诞生的一种全新技术。 2•计算模型的四种驱动方式是控制驱动、数据驱动、需求驱动和模式匹配驱动。 3. RISC结构中采用的三种流水线结构是超标量结构、 超流水线结构和超长指令字（VLIW）结构。 4. 单机系统实现并行处理的途径是时间重叠、资源重复、资源共享。多机系统实现并 行处理的途径是功能专用化、机间互联、网络化。 二、简答题：（共20分） 1.请画图表示两种并行处理机的结构（6分） 见书上138图5—2 5 — 3 2. 简述集群系统的概念。（5分） 集群系统是利用高速通信网络将一组高性能工作站或高档PC机连接起来，在并行程序 设计和集成开发环境支

15、撑下统一调度、协调处理以实现高效并行处理的系统。集群系 统中的主机和网络可以是同构的，也可以是异构的，主要利用消息传递方式实现机间 的通信，由建立在一般的操作系统上的并行编程环境完成系统的资源管理及相互协作。 3. 简述计算机性能评价和计算机性能测量的定义（4分） 计算机性能评价是指计算机系统对原始数据进行逻辑推算。 计算机性能测量是指采用基准测试程序包来度量计算机系统的性能。 4•简述数据流计算机工作原理。（5分） 数据流计算机没有程序计数器，没有中央控制器，指令的执行由数据来驱动，把控制 流变为数据流。当指令所需数据可用时，指令就可以执行。 得 三.综合题(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提出的数据流程序图描述下列语句: if true then (a+b) 2 else (a*c)/d 3、已知16个节点的超立方体网络，要求用E立方体寻径算法，计算从源节点（1010） 到目的节点（0111）的路径，写出计算过程，画出网络拓扑图，并在图上用箭头标出 路径。（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、已知算术表达式E=a-[b（c-de+f-g）+h],现用3个处理机的并行系统处理。要求: 试压缩树高来开发该式并行性。求出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的操作内容 (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、现有8个处理机，编号分别为0~7,用多级互联网络连接。规定2级用PM2-2，1 级用 Shuffle(Shuffle), 0 级用 Cubel。要求： (a) 分别列出PM2-2，Shuffle(Shuffle)，Cubel时，处理机0〜7互连编号。 (b) 画出各级互联网络图。 (c) 在图中画出编号5连通到编号3的路径，并标出开关状态。 （15 分） Cube1