第一章绪论
1.1 什么是并行计算机？
答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信和协作，能快速高效求解大型的复杂的问题。
1.2 简述Flynn分类法：
答：根据指令流和数据流的多重性将计算机分为：
1）单指令单数据流SISD
2）单指令多数据流SIMD
3）多指令单数据流MISD
4）多指令多数据流MIMD
1.3 简述当代的并行机系统
答：当代并行机系统主要有：
1）并行向量机（PVP）
2）对称多处理机（SMP）
3）大规模并行处理机（MPP）
4）分布式共享存储（DSM）处理机
5）工作站机群（COW）
1.4 为什么需要并行计算机？
答：1）加快计算速度
2）提高计算精度
3）满足快速时效要求
4）进行无法替代的模拟计算
1.5 简述处理器并行度的发展趋势
答：1）位级并行
2）指令级并行
3）线程级并行
1.6 简述SIMD阵列机的特点
答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。
2）所有的处理单元（PE）必须是同步的。
1
3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。
2 2
1m 4）阵列机是一种专用的计算机，用于处理一些专门的问题。
1.7 简述多计算机系统的演变
答：分为三个阶段：
1）1983-1987年为第一代，代表机器有：Ipsc/1、Ameteks/14等。
2）1988-1992年为第二代，代表机器有：Paragon 、Intel delta 等。
3）1993-1997年为第三代，代表机器有：MIT 的J-machine 。
1.8 简述并行计算机的访存模型
答：1）均匀存储访问模型（UMA ）
2）非均匀存储访问模型（NUMA ）
3）全高速缓存存储访问模型（COMA ）
4）高速缓存一致性非均匀访问模型（CC-NUMA ）
1.9 简述均匀存储访问模型的特点
答：1）物理存储器被所有处理器均匀共享。
2）所有处理器访问任何存储字的时间相同。
3）每台处理器可带私有高速缓存。
4）外围设备也可以一定的形式共享。
1.10简述非均匀存储访问模型的特点
答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。
2）处理器访问存储器的时间不一样。
3）每台处理器可带私有高速缓存，外备也可以某种的形式共享。
第二章 性能评测
2.1 使用40MHZ 主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表2.13所示。试计算执行该程序的有效CPI 、MIPS 速率及总的CPU 执行时间。 解：CPI=total cycles / total instructions
=（45000*1+32000*2+15000*2+8000*2）/（45000+32000+15000+8000） =1.55
MIPS=时钟频率 / (CPI*106)=(40*106) / (1.55*106)=25.8
CPU 执行时间= total cycles /时钟频率=0.00375s
2.2欲在40MHZ 主频的标量处理器上执行20万条目标代码指令程序。假定该程序中含有4种主要类型之指令，各指令所占的比例及CPI 数如表2.14所示，试计算：
①在单处理机上执行该程序的平均CPI 。
②由①所得结果，计算相应的MIPS 速率。
解：（1）CPI=1*60%+2*18%+4*12%+8*10%
=2.12
（2）MIPS=时钟频率 / (CPI*106)= (40*106) / (2.12*106)=18.9
2.1 2.3已知SP2并行计算机的通信开销表达式为：t （m ）=46+（0.035）m ，试计算： ①渐近带宽r ∞=?
②半峰值信息长度 = ? [提示：t o =46μs] 解：（1）渐近带宽r ∞=1 / 0.035=28.6MB/S
(2) 半峰值消息长度m 1/2=to* r ∞=46us*28.6MB/S=1315.6B
2.4并行机性能评测的意义。
答：意义有： 1）发挥并行机长处，提高并行机的使用效率。
2）减少用户购机盲目性，降低投资风险。
3）改进系统结构设计，提高机器的性能。
4）促进软/硬件结合，合理功能划分。
5）优化“结构-算法-应用”的最佳组合。
6）提供客观、公正的评价并行机的标准。
2.5如何进行并行机性能评测
答：1）机器级性能评测：CPU和存储器的某些基本性能指标；并行和通信开销分析；并行机的可用性与好用性以及机器成本、价格与性/价比。
2）算法级性能评测：加速比、效率、扩展性。
3）程序级性能评测：Benchmark。
2.6 简述Gustafson定律的出发点
答：1）对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变。
2）除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。
2.7 已知一程序可并行代码占比例为80%，将其在有10个处理器的系统中运行，求其加速比？并求其极限加速比？并分析其结构带来的影响
解：加速比=1/(20%+80%/10)=1/(0.2+0.08)=3.57。
极限加速比，即处理器个数无穷大的时候呈现的加速比=1/20%=5。
这个极限加速比，换个角度说是，Amdahl定律在很长一段时间影响了人们对开发并行计算机的信心，对于本例，因为就算你把处理器做到无穷也只能得到5倍的加速比，同时有一点更明显，就是处理器数目增加到一定程度后，加速比的增长非常缓慢。
2.8 简述影响加速的因素
答：1）求解问题中的串行分量。
2）并行处理器所引起的额外开销。
3）加大的处理器数超过的算法的并发程度。
2.9 为什么增加问题规模可以在一定程度提高加速
答：1）较大的问题规模可提高较大的并发度。
2）额外开销的增加可能慢于有效计算的增加。
3）算法中串行分量的比例不是固定不变的。
2.10 进行可扩放行研究的主要意义
答：1）确定解决某类问题用某类并行算法和某类并行体系结构结合，可以有效的利用大量的处理器。
2）对于运行于某种体系结构的并行机的某种算法当移到大规模处理机上的性能。
3）对于某类固定规模的问题，确定在某类并行机上的最优处理器数目和最大的加速比。
4）用于指导改进并行算法和并行体系结构，以使并行算法能尽可能充分利用可扩充的。大量的处理器。
第三章互连网络
3.1 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-
元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。
答：
推广至M元树时，k级M元树总结点数N的表达式为：
3
N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m);
3.2二元胖树如图3.46所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？ 答：8输入的完全混洗三级互联网络。
3.3 四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？
答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。
3.4 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？
答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4
B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6
3.5 一个N=2^k 个节点的 de Bruijin 网络如图3.48。。。。试问：该网络的直径和对剖宽度是多少？
答：N=2^k 个节点的 de Bruijin 网络 直径d=k 对剖宽带w=2^(k-1)
3.6 一个N=2^n 个节点的洗牌交换网络如图3.49所示。试问：此网络节点度==？网络直径==？网络对剖宽度==？
答：N=2^n 个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4
3.7 一个N=（k+1）2^k 个节点的蝶形网络如图3.50所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？
答：N=（k+1）2^k 个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k
3.9 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）
答：
5
3.10 如图3.51所示，信包的片0，1，2，3要分别去向目的地A ，B ，C ，D 。此时片0占据信道CB ，片1占据信道DC ，片2占据信道AD ，片3占据信道BA 。试问：
1）这将会发生什么现象？
2）如果采用X-Y 选路策略，可避免上述现象吗？为什么？
答： 1）通路中形成环，发生死锁
2）如果采用X-Y 策略则不会发生死锁。因为采用X-Y 策略时其实质是对资源（这里是通道）进行按序分配（永远是x 方向优先于y 方向，反方向路由是y 方向优先于x 方向），因此根据死锁避免的原则判断，此时不会发生死锁。
3.12 在二维网孔中，试构造一个与X-Y 选路等价的查表路由。
答： 所构造路由表描述如下：
1）每个节点包括两张路由表x 表和y 表
2）每个节点包含其以后节点信息，如节点【1，2】x 表内容为:【2，2】【3，2】y 表内容为：【1，3】
选路方法：
节点路由时进行查表：先查x 表即进行x 方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y 表，直到到达目的地。
第四章 对称多处理机系统
4.1参照图4.20，试解释为什么采用WT 策略进程从2P 迁移到1P 时，或采用WB 策略将包含共享变量X 的进程从1
P 迁移到2P 时，会造成高速缓存的不一致。
处理器高速缓存共享
存储器迁移写通写总线
过回之前
图4.20 进程迁移所造成的不一致性
答：采用WT 策略进程从2P 迁移到1P 后，2P
写共享变量X 为X ’，并且更新主存数据为X ’，此时1P 共享变量值仍然为X ，与2P 和主存X ’不一致。采用WB 策略进程从1P 迁移到2P 后，1P 写共享变量X 为X ’，但此时2P
缓存与主存变量值仍然为X ，造车不一致。 4.2参照图4.21所示，试解释为什么：①在采用WT 策略的高速缓存中，当I/O 处理器将
6 一个新的数据'
X 写回主存时会造成高速缓存和主存间的不一致；②在采用WB 策略的高速缓存中，当直接从主存输出数据时会造成不一致。
处理器（写直达）总线
（写回）高速缓存
I/O处理机
图4.21 绕过高速缓存的I/O 操作所造成的不一致性
答：①中I/O 处理器将数据X ’写回主存，因为高速缓存采用WT 策略，此时P1和P2相应的高速缓存值还是X ，所以造成高速缓存与主存不一致。②直接从主存输出数据X ，因为高速缓存采用WB 策略，可能高速缓存中的数据已经被修改过，所以造成不一致。
4.3 试解释采用WB 策略的写更新和写无效协议的一致性维护过程。其中
X 为更新前高速
缓存中的拷贝，'
X 为修改后的高速缓存块，I 为无效的高速缓存块。
（b）处理器P 1执行写无效操作后
（c）处理器P 1执行写更新操作后
（a）写操作前答：处理器P1写共享变量X 为X ’，写更新协议如图(c)所示，同时更新其他核中存在高速缓存拷贝的值为X ’;写无效协议如图(b)所示，无效其他核中存在高速缓存拷贝，从而维护了一致性过程。
4.4 两种基于总线的共享内存多处理机分别实现了Illinois MESI 协议和Dragon 协议，对于
下面给定的每个内存存取序列，试比较在这两种多处理机上的执行代价，并就序列及一致性协议的特点来说明为什么有这样的性能差别。序列①r1 w1 r1 w1 r2 w2 r2 w2 r3 w3 r3 w3；序列②r1 r2 r3 w1 w2 w3 r1 r2 r3 w3 w1；序列③r1 r2 r3 r3 w1 w1 w1 w1 w2 w3；所有的存取操作都针对同一个内存位置，r/w 代表读/写，数字代表发出该操作的处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/写高速缓存命中，代价1个时钟周期；缺失引起简单的总线事务（如BusUpgr ，BusUpd ），60个时钟周期；缺失引起整个高速缓存块传输，90时钟周期。假设所有高速缓存是写回式。 答：读写命中、总线事务、块传输分别简记为H 、B 、T 。MESI 协议：①BTH H H H BTH BH H H BTH BH H H 共5B+12H+3T=582时钟周期②BTH BTH BTH BH BTH BTH BTH BTH H BH BTH 共10B+12H+8T=1330时钟周期③BTH BTH BTH H BH H H H BTH BTH 共6B+10H+4T=730时钟周期。 Dragon 协议：①BTH H H H BTH BTH H BTH BTH BTH H BTH 共7B+12H+7T=882时钟周期②BTH BTH BTH BTH BTH BTH H H H H BTTH BTH 共8B+12H+8T=1212时钟周期③BTH BTH BTH H BTH BTH BTH BTH BTH BTH 共9B+10H+9T=1360时钟周期。由结果得出，①、③序列用MESI 协议时间更少，而②序列用Dragon 协议时间更少。综上可知，如果同一块在写操作之后频
繁被多个核读操作采用Dragon协议更好一些，因为Dragon协议写操作后会更新其它核副本。如果一个同多次连续对同一块进行写操作MESI协议更有效，因为它不需要更新其它核副本，只需要总线事务无效其它核即可。
4.5考虑以下代码段，说明在顺序一致性模型下，可能的结果是什么？假设在代码开始执行
时，所有变量初始化为0。
a.
P1 P2 P3
A=1 U=A V=B
B=1 W=A
b.
P1 P2 P3 P4
A=1 U=A B=1 W=B
V=B X=A
答：顺序一致性模型性下，保护每个进程都按程序序来发生内存操作，这样会有多种可能结果，这里假设最简单情况，即P1、P2、P3依次进行。则a中U = V = W = 1，b中U=X=W=1，V=0。
4.6参照4.6.1中讨论多级高速缓存包含性的术语，假设L1和L2都是2-路组相联，n2>n1，
b1=b2，且替换策略用FIFO来代替LRU，试问包含性是否还是自然满足？如果替换策略是随机替换呢？
答：如果采用FIFO替换策略包含性自然满足，因为L1和L2都是2路组相联，FIFO保证了L1与L2在发生替换时会换出相同的缓存块，维护了包含性。如果采取随机替换策略，存在L1与L2替换不是相同块的情况，故不满足包含性。
4.7针对以下高速缓存情况，试给出一个使得高速缓存的包含性不满足的内存存取序列？
L1 高速缓存容量32字节，2-路组相联，每个高速缓存块8个字节，使用LRU替换算法；L2 高速缓存容量128字节，4-路组相联，每个高速缓存块8个字节，使用LRU替换算法。
答：假设m1、m2、m3块映射到一级Cache和二级Cache的同一组中，考虑如下内存存取序列R m1，R m2，R m1，R m3，由LRU替换算法知道，当R m3执行后，L1中被替换出的是m2，L2中被替换出的是m1，此时m1块在L1却不在L2中，不满足包含性。
4.8在4.6中关于分事务总线的讨论中，依赖于处理器与高速缓存的接口，下面情况有可能
发生：一个使无效请求紧跟在数据响应之后，使得处理器还没有真正存取这个高速缓存块之前，该高速缓存块就被使无效了。为什么会发生这种情况，如何解决?
答：考虑如下情景：SMP目录一致性协议中，核1读缺失请求数据块A，主存响应请求传送数据块A给核1，同时核2对数据块A进行写操作，到主存中查得核1拥有副本，向核1发使无效请求。如此，一个使无效请求紧跟在数据响应之后。解决方法，可以使每个核真正存取高速缓存块后向主存发回应，然后再允许其它对此块操作的使无效或其它请求。
4.9利用LL-SC操作实现一个Test&Set操作。
答：Test&Set：ll reg1,location /*Load-locked the location to reg1 */
7
bnz reg1,lock /* if locatin was locked,try again*/
mov reg2,1 /*set reg2 1*/
sc location,reg2 /*store reg2 conditional into location*/
4.10在4.7.4部分描述具有感觉反转的路障算法中，如果将Unlock语句不放在if条件语句
的每个分支中，而是紧接放在计数器增1语句后，会发生什么问题？为什么会发生这个问题？
答：再进入下一个路障时可能会发生计数器重新清0现象，导致无法越过路障。考虑如下情景：第一次进入路障时，最后两个进入路障的进程分别为1、2。假设最后进入路障的进程为2进程，2进程执行共享变量加一操作并解锁。然后2进程执行一条if条件语句，此时由于某种原因换出或睡眠，而此时共享变量的值已经为p。如果1进程此时正执行if条件语句，则清零计数器，设置标志，其它进程越过路障。到目前为止没有出现问题，问题出现在下一次进入路障。进程再一次进入路障，此时会执行共享变量加一操作。如果此时2进程被换入或被唤醒，会重新清零共享变量，使之前到达路障的进程的加一操作无效，导致无法越过路障。
第五章大规模并行处理机系统
5.1简述大规模并行处理机的定义，原理和优点？
答：并行处理机有时也称为阵列处理机，它使用按地址访问的随机存储器，以单指令流多数据流方式工作，主要用于要求大量高速进行向量矩阵运算的应用领域。并行处理机的并行性来源于资源重复，它把大量相同的处理单元（PE）通过互联网络（ICN）连接起来，在统一的控制器（CU）控制下，对各自分配来的数据并行地完成同一条指令所规定的操作。PE是不带指令控制部件的算术逻辑运算单元。并行处理机具有强大的向量运算能力，具有向量化功能的高级语言编译程序有助于提高并行处理机的通用性，减少编译时间。
5.2并行处理机有两种基本结构类型，请问是哪两种？并作简单介绍。
答：采用分布存储器的并行处理结构和采用集中式共享存储器的并行处理结构。分布式存储器的并行处理结构中，每一个处理机都有自己的存储器，只要控制部件将并行处理的程序分配至各处理机，它们便能并行处理，各自从自己的存储器中取得信息。而共享存储多处理机结构中的存储器是集中共享的，由于多个处理机共享，在各处理机访问共享存储器时会发生竞争。因此，需采取措施尽可能避免竞争的发生。
5.3简单说明多计算机系统和多处理机系统的区别。
答：他们虽然都属于多机系统但是他们区别在于：（1）多处理机是多台处理机组成的单机系统，多计算机是多台独立的计算机。（2）多处理机中各处理机逻辑上受同一的OS控制，而多计算机的OS逻辑上独立.(3)多处理机间以单一数据，向量。数组和文件交互作用，多计算机经通道或者通信线路以数据传输的方式进行。（4）多处理机作业，任务，指令，数据各级并行，多计算机多个作业并行。
5.4举例说明MPP的应用领域及其采用的关键技术。
答：全球气候预报，基因工程，飞行动力学，海洋环流，流体动力学，超导建模，量子染色动力学，视觉。采用的关键技术有VLSI，可扩张技术，共享虚拟存储技术。
5.5多处理机的主要特点包括
答：
8
（1）结构的灵活性。与SIMD计算机相比，多处理机的结构具有较强的通用性，它可以
同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。2）程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并行性体现在指令外部，即表现在多个任务之间。3）并行任务派生。多处理机是多指令流操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。
4）进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。
5.6在并行多处理机系统中的私有Cache会引起Cache中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache一致性问题。请问有哪些原因导致这个问题？答：
1）出现Cache一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。共享可写数据引起的不一致性。比如P1、P2两台处理机各自的本地高速缓冲存储器C1、C2中都有共享存储器是M中某个数据X的拷贝，当P1把X的值变成X/后，如果P1采用写通过策略，内存中的数据也变为X/，C2中还是X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。2）进程迁移引起的数据不一致性。P1中有共享数据X的拷贝，某时刻P1进程把它修改为X/并采用了写回策略，由于某种原因进程从P1迁移到了P2上，它读取数据时得到X，而这个X是“过时”的。3）I/O传输所造成的数据不一致性。假设P1和P2的本地缓存C1、C2中都有某数据X的拷贝，当I/O处理机将一个新的数据X/写入内存时，就导致了内存和Cache之间的数据不一致性。
5.7分别确定在下列两种计算机系统中，计算表达式所需的时间：s=A1*B1+A2*B2+…A4*B4。
a) 有4个处理器的SIMD系统；b) 有4个处理机的MIMD系统。假设访存取指和取数的时间可以忽略不计；加法与乘法分别需要2拍和4拍；在SIMD和MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在SIMD系统中，PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的的通路。
答：假设4个PE分别为PE0，PE1，PE2，PE3。利用SIMD计算机计算上述表达式，4个乘法可以同时进行，用时=4个时间单位；然后进行PE0到PE1，PE2到PE3的数据传送，用时=1个时间单位。在PE1和PE3中形成部分和，用时=2个时间单位。接着进行PE1到PE3的部分和传送，用时=1*2=2个时间单位。最后，在PE3中形成最终结果，用时=2个时间单位。因此，利用SIMD计算机计算上述表达式总共用时=4（乘法）+1（传送）+2（加法）+2（传送）+2（加法）=11个时间单位。而利用MIMD计算机计算上述表达式，除了在第二次传送节省1个时间单位以外，其他与SIMD相同。因此用时=4（乘法）+1（传送）+2（加法）+1（传送）+2（加法）=10个时间单位。
5.8假定有一个处理机台数为p的共享存储器多处理机系统。设m为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。
设t为共享存储器的平均存储时间，x为使用本地存储器的单处理机MIPS速率，再假定在多处理机上执行n条指令。
9
现在假设p=32,m=0.4,t=1μs,要让多处理机的有效性能达到56MIPS，需要每台处理机
10 的MIPS 效率是多少？
A.2
B.4
C.5.83
D.40
答：B
5.9试在含一个PE 的SISD 机和在含n 个PE 且连接成一线性环的SIMD 机上计算下列求内积
的表达式：其中n=2k
∑=?=n
i i i B A s 1
假设完成每次ADD 操作需要2个单元时间，完成每次MULTIPLY 操作需要4个单位时间，沿双向环在相邻PE 间移数需1个单位时间
(1) SISD 计算机上计算s 需要多少时间
(2) SIMD 计算机上计算s 需要多少时间
(3) SIMD 机计算s 相对于SISD 计算的加速比是多少？
答：
(1) 4n+2(n-1)
(2) 124-++n k
(3)
()n
k n n ++-+23124
5.10如果一台SIMD 计算机和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求？
答：一台具有n 个处理单元的SIMD 计算机与一台具有一条n 级流水线并且时钟周期为前者1/n 的流水线处理机的计算性能相当，两者均是每个时钟周
期产生n 个计算结果。但是，SIMD 计算机需要n 倍的硬件（n 个处理单元），而流水线处理机中流水线部件的时钟速率要求比前者快n 倍，同时还需要存储器的带宽也是前者的n 倍。
第六章 机群系统
6.1 试区分和例示下列关于机群的术语：
1）专用机群和非专用机群；
2）同构机群和异构机群；
3）专用型机群和企业型机群。
答：
1） 根据节点的拥有情况，分为专用机群和非专用机群，在专用机群中所有的资源是共享的，
并行应用可以在整个机群上运行，而在非专用机群中，全局应用通过窃取CPU 时间获得运行，非专用机群中由于存在本地用户和远地用户对处理器的竞争，带来了进程迁移和负载平衡问题。
2） 根据节点的配置分为同构机群和异构机群，同构机群中各节点有相似的的体系，并且使
用相同的操作系统，而异构机群中节点可以有不同的体系，运行的操作系统也可以不同。
3） 专用型机群的特点是紧耦合的、同构的，通过一个前端系统进行集中式管理，常用来代
替传统的大型超级计算机系统；而企业型机群是松耦合的，一般由异构节点构成，节点可以有多个属主，机群管理者对节点有有限的管理权。
6.2 试解释和例示一下有关单一系统映像的术语：
1）单一文件层次结构；
2）单一控制点；
3）单一存储空间；
4）单一进程空间；
5）单一输入/输出和网络。
答：
1）用户进入系统后所见的文件系统是一个单一的文件和目录层次结构，该系统透明的将本地磁盘、全局磁盘和其他文件设备结合起来。
2）整个机群可以从一个单一的节点对整个机群或某一单一的节点进行管理和控制。
3）将机群中分布于各个节点的本地存储器实现为一个大的、集中式的存储器。
4）所有的用户进程，不管它们驻留在哪个节点上，都属于一个单一的进程空间，并且共享一个统一的进程识别方案。
5）单一输入/输出意味着任何节点均可访问多个外设。单一网络是任一节点能访问机群中的任一网络连接。
6.3 就Solaris MC系统回答下列问题：
1）Solaris MC 支持习题6.2 中单一系统映像的哪些特征？不支持哪些特征？
2）对那些Solaris MC 支持的特征，解释一下Solaris MC是如何解决的。
答：
1）支持单一文件层次结构、单一进程空间、单一网络和单一I/O空间。不支持单一控制点和单一的存储空间。
2）Solaris使用了一个叫PXFS的全局文件系统GFS。PXFS文件系统的主要特点包括：单一系统映像、一致的语义及高性能。PXFS通过在VFS/vnode接口上截取文件访问操作实现单一系统映像，保证了单一文件层次结构。
Solaris MC提供了一个全局进程标示符pid可定位系统所有进程，一个进程可以迁移到其他节点，但它的宿主节点中总记录有进程的当前位置，它通过在Solaris核心层上面增加一个全局进程以实现单一进程空间，每个节点有一个节点管理程序，每个本地进程有一个虚拟进程对象vproc，vproc保留每个父进程和子进程的信息，实现了全局进程的管理。
单一网络和I/O空间通过一致设备命名技术和单一网络技术实现。
6.4 举例解释并比较以下有关机群作业管理系统的术语：
1）串行作业与并行作业；
2）批处理作业与交互式作业；
3）机群作业和外来作业；
4）专用模式、空间共享模式、时间共享模式；
5）独立调度与组调度。
答：
1）串行作业在单节点上运行，并行作业使用多个节点。
2）批处理作业通常需要较多的资源，如大量的内存和较长的CPU时间，但不需要迅速的反应；交互式作业要求较快的周转时间，其输入输出直接指向终端设备，这些工作一般不需要大量资源，用户期望它们迅速得到执行而不必放入队列中。
11
3）机群作业时通过使用JMS功能分布实现的用户作业，用户服务器位于任一主机节点，
资源管理器跨越所有的机群节点。外来作业在JMS之外生成的，如NOW上的一个工作站拥有者启动的外部作业，它不提交给JMS。
4）专用模式：任一时候只有一个作业在机群上运行，任一时候也只有一个作业进程分配给一个节点。空间共享模式：多个作业可以在不重叠的节点区域上运行。时间共享模式：在专用模式和空间共享模式下，只有一个用户进程分配给一个节点，但是所有的系统进程或监护程序仍在同一个节点上运行。
5）独立调度：各节点OS进行自己的调度，但这会显著损坏并行作业的性能，因为并行作业的进程间需要交互。组调度：将并行作业的所有进程一起调度。一个进程激活时，所有进程都被激活。
6.5 针对LSF回答下列问题：
1）对LSF的四种作业类型各举一个例子；
2）举一个例子说明外来作业；
3）对一个有1000个服务器的机群，为什么LSF负载分配机制优于：1整个机群只有一个LIM或者2所有LIM都是主机？说明原因。
答：
1）交互式：用户使用lshosts命令就可以列出每个服务器节点的静态资源，实现交互。批处理：lsbatch实用程序允许通过LSF提交、监控和执行批处理作业。串行：用户一旦进入lstcsh shell，发送的每条命令自动在最适合的节点上执行。并行：lsmake实用程序是UNIX make实用程序时一个并行版本，允许在多个节点同时处理一个Makefile。
2）不通过LSF执行的称为外来作业。例如执行一些本地作业：字处理，web网络浏览等。3）机群的服务器数目太多，如果只采用一个LIM会导致LIM的负责过重，不能及时的处理响应所有服务器的请求和分派所有机群作业；如果采用2会导致LIM之间相互交换负载信息过多，导致网络通信量过大。
6.6 为什么在分布式文件系统中，UNIX语义难以实现？有哪些放松的文件共享语义？采用放松的文件共享语义会有一些什么缺点？
答：
在UNIX语义中，一个修改过的块应该立刻被所有其他应用程序见到。然而分布式的文件系统中，多个节点可能存放了同一文件块的拷贝，当其中一个节点修改文件可的拷贝时，其他节点不能立刻就知道，这就使得UNIX语义难以实现。放松的文件共享语义有：对话语义、类事物语义、不可改变的共享文件语义等。采用放松的文件共享语义要求应用程序员修改程序代码，以适用这种新的语义，这就增加了程序员的负担。
6.7 试解释在机群并行文件系统中，为什么采用软件RAID、高速缓存机制和预取能够提高文件系统性能。
答：
软件RAID是文件系统负责分布数据和维护容错级别，能够和RAID5有一样的性能，实现机群磁盘间的数据分布，提高了I/O系统的传输带宽。高速缓存是将应用程序要取的块放在CACHE中，根据局部性原理，应用程序可以基本上从CACHE中读取数据块，而不要通过读取内存或硬盘，提高了读取速度。预取是在真正读取数据块之前就将这些数据块读入内存，这也提高了I/O性能，改善了文件系统性能。
6.8 讨论并行文件系统协作化高速缓存的基本技术前提是什么？这个前提有什么意义？
12
答：
基本技术前提是互联网络的速度很快，一个节点需要的文件块在其他节点的缓存中，那么就不需要从磁盘读，而是直接从其他节点的缓存中读出。这个前提的意义是可以提高系统的性能，使得节点间的协作化缓存变得更有意义。
6.9 回答以下关于Berkeley NOW项目的问题：
1）Berkeley NOW项目支持单一系统映像的哪几个方面？即单入口点、单文件层次结构、单控制点、单存储空间、单进程空间哪个的哪几项？并解释如何支持。
2）解释Berkeley NOW项目用来提高性能的四个结构特征。
3）解释Berkeley NOW项目和SP机群四个体系结构的差异，并讨论各自的优点。
答：
1）通过用户级整个机群软件GLUNIX，提供单一系统映像。开发了一种新的无服务器网络文件系统xFS，以支持单一文件层次结构。
2）主动消息通信协议，支持有效的通信；机群软件GLUNIX提供单一的系统映像、资源管理和可用性；xFS支持可扩放性和单一文件层次结构的高可用性；软件框架WebOS构筑高可用性、渐增可扩放性。
3）SP机群的体系结构特征：每个节点都是RS/600工作站，并有自己的局部磁盘；每个节点内驻留一个完整的AIX；各节点通过其I/O总线连接到专门设计的多级高速网络；尽量使用标准工作站部件。这样的优点是简单性和灵活性。
6.10考虑xFS，并回答下列问题：
1）解释xFS和集中式文件服务器的两个不同点，并讨论各自的优点；
2）解释xFS用来提高可用性的主要技术；
3）解释xFS用来减轻小—写问题的主要技术。
答：
1）无服务器文件系统xFS将文件服务的功能分布到机器的所有节点上，xFS中所有的服务器和客户的功能由分散的所有节点实现之。这与集中文件服务器的中央存储、中央缓存、中央管理不同。xFS的优点是采用分布式管理和协同文件缓存以及冗余磁盘阵列，这提高了系统的可用性以及I/O的性能和吞吐量。集中式文件服务器会减少缓存的不一致性，管理简单。
2）xFS提高可用性的主要技术是采用廉价冗余磁盘阵列RAID。无工作站文件系统能用来生成软件RAID，以提高性能和高可用性。现在xFS使用单奇偶校验磁盘条。一个文件数据块在多个存储服务器节点上按条划分，在另一个节点上有奇偶校验块。如果一个节点失效，失效磁盘的内容，可利用其余盘和奇偶盘之异或操作重建之。
3）xFS使用日志条的方法解决小—写问题：每个用户首先将写接合到各用户的日志上；然后此日志采用日志段提交给磁盘，每个段系由K-1个日志片组成，它与奇偶校验片以道送给K个存储服务器。
第七章分布式共享存储系统
7.1什么是分布式共享存储系统，它相对于共享存储系统与分布式系统有哪些优点？
答：分布式共享存储系统，是把共享存储器分成许多模块并分布于各处理机之中。分布式系统中采用消息传递通信，性能提高了，但多地址空间不利于程序员编程。共享存储系统支持传统的单地址空间，但共享必然引起冲突，形成瓶颈，于是分布式共享存储系统结合两者的优点。
13
7.2释放一致性模型(RC)把处理器一致性(PC)和弱一致性模型(WC)的优点结合在一起了。
14
试回答下面有关这些一致性模型的问题：
a) 比较这三种一致性模型的实现要求。
b)评论每种一致性模型的优缺点。
答：a)处理器一致性要求：①在任一取数操作LOAD 允许被执行之前，所有在同一处理器中先于这一LOAD 的取数操作都已完成；②在任一存数操作STORE 允许执行之前，所有在同一处理器中先于这一STORE 的访存操作（包括取数操作和存数操作）都已完成。弱一致性模型要求：①同步操作的执行满足顺序一致性条件；②在任一普通访存操作允许被执行之前，所有在同一处理器中先于这一访存操作的同步操作都已完成；③在任一同步操作允许被执行之前，所有在同一处理器中先于这一同步操作的普通访存操作都已完成。释放一致性模型要求：①在任一普通访存操作允许被执行之前，所有在同一处理器中先于这一访存操作的获取操作acquire 都已完成；②在任一释放操作release 允许被执行之前，所有在同一处理器中先于这一release 的普通访存操作都已完成；③同步操作的执行满足顺序一致性条件。
b)三种模型对存储顺序要求逐渐降低，可优化程度逐渐增加，但是对程序员的要求也越来越高，所以释放性一致性是性能与复杂度的折中。
7.3在DSM 系统的顺序一致性存储模型下，有三个并行执行的进程如下所示，试问001110是不是一个合法的输出？并加以解释。
P1 P2 P3
A=1;
B=1; C=1; Print(b,c); Print(a,c); Print(a,b);
答：不是一个合法输出。考虑顺序一致性存储模型，每个进程的程序序会被维护，那么无论哪个进程最后执行Print 语句，则之前的A=1，B=1,C=1都已经完成，所以输出的两后两项必为11，所以001110不是合法输出。
7.4试分类下面来自三个处理器的引用流的高速缓存缺失。假设每一个处理器的高速缓存只有一个4个字的高速缓存行，字W0到W3、W4到W7分别处于同一个高速缓存行。
如果一行有多个引用，我们假设P1在P2之前发射、P2在P3之前发射内存引用，符号
15 答：操作序号3、6、8、12-15都是单操作。操作序号1、2、9-11为无关存储操作，由于不在同一块中。操作序号4、7为对同一缓存块的连续两次LD ，需要按序进行。
7.5假设系统中共有512个处理器和1GB 主存，每个节点内有8个处理器对目录可见，一个高速缓存行的大小为64字节，那么在(a) 满位向量方案和(b) Dr i B(i=3)模型下目录的存储成本各是多少？
答：分别为总容量的12.%和5.47%。
7.6 细数一下中心目录与分布式目录方案的实现方法与各自的使用情况。
答：中心目录是用一个中心目录存放所有高速缓存目录的拷贝，中心目录能提供为保证一致性所需要的全部信息。因此，其容量非常大且必须采用联想方法进行检索，这和单个高速缓存的目录类似。大型多处理机系统采用中心目录会有冲突和检索时间过长两个缺点。
分布式目录方案是由Censier 和Feautrier 提出来。在分布式目录中每个存储器模块维护各自的目录，目录中记录着每个存储器块的状态和当前的信息，其中状态信息是本地的，而当前信息指明哪些高速缓存中有该存储器块的拷贝。
一般来说，在共享存储上实现中心目录，而在分布式系统上实现分布式目录方案更为合适一些，但这也并不是绝对的。
7.7在研究DSM 的读写代价和实现问题时有这样两种算法，即中央服务器算法和迁移算法：中央服务器算法是指使用一个中央服务器，负责为所有对共享数据的访问提供服务并保持共享数据唯一的副本；迁移算法是指要访问的数据总是被迁移到访问它的节点中。两种算法图示如下：
现假设报文数量不会导致网络阻塞，服务员的阻塞没有严重到能够极大地延迟远程进程访问，访问本地数据的代价与远程访问代价相比微不足道，报文传递也是可靠的。试分析两种算法的适合情况。
答：中央服务器算法，每次顾客发送数据请求到中央服务器，地址计算简单，适合多个顾客频繁轮流读写。迁移算法每次确定位置需要一定开销，适用于单个顾客频繁对数据读写，因为访问数据总是被迁移到访问节点里。
7.8下面是运行在一个硬件维护高速缓存一致性的多处理机上的程序段，假设所有值初始 为0。
P1 P2 P3 P4 A=1 U=A W=A A=2
V=A X =A
只有一个共享变量A，假设一个用户知道所有高速缓存拷贝的地址并且可直接对(不需要和目录节点协商)拷贝进行更新，假设采用写更新协议。试构造出一个写原子性被违背的情况：
说明产生的结果违背了顺序一致性；
答：如果进程P1首先对含有共享变量A的数据块进行写操作，进程P2、P3执行U=A和W=A，分别将U、W置为1。此时P4对共享变量A进行写操作，并且同时更新P1、P2、P3中的值，此后P2、P3再执行V=A，X=A，此时V与X被置为了2。对于进程2来说，结果违背了顺序一致性。
7.9参照下述代码段：
问：000000是不是PARM一致性内存模型的合法输出？解释原因说明顺序一致性与PARM 一致性区别？
a=1; b=1; c=1;
Print(b, c); Print(a, c); Print(a, b);
(a)P1 (b) P2 (c)P3
答：在PARM一致性内存模型下，000000是合法输出，因为PARM不关注存储相关性，即同一进程程序序可以优化，这样各进程先执行打印完再执行赋值则出现如上情况。顺序一致性与PARM一致性的区别就是于是否关注存储相关性。
7.10有两个并行的过程P1、P2（如下图所示），在顺序一致性模型下，试列出所有可能的
6种语句交错执行顺序，使两进程不可能同时被kill。
a=1; b=1;
if(b= =0)kill(P2); if(a= =0)kill(P1);
(P1) (P2)
答：（1）a=1;
if(a= =0)kill(P1);
b=1;
if(b= =0)kill(P2);
(2) a=1;
b=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
(3) b=1;
if(a= =0)kill(P1);
a=1;
if(b= =0)kill(P2);
(4) b=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
a=1;
(5) a=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
16
b=1;
(6) if(a= =0)kill(P1);
if(b= =0)kill(P2);
a=1;
b=1;
分析以上6种情况，在满足顺序一致性模型前提下，不会存在P1、P2同时被KILL的情况。
17
计算机系统结构试题及答案 一、单项选择题（本大题共20小题，每小题2分，共20分） 1．以下正确的是（）。 A）机箱是计算机的外特性，属系统结构的研究范围 B）集成电路芯片的设计是计算机组成原理的研究范围 C）加法器的设计是计算机实现的研究内容 D）计算机性能评价是计算机系统结构的研究范围 2．在流水线相关处理中，采用（）会产生“写-写”相关和“先读后写”相关。 A）猜测法B）顺序流动 C）异步流动 D）相关专用通路3．非线性流水线是指（） Ａ）存在分叉连接的流水线Ｂ）存在反向连接的流水线 Ｃ）一个任务使用多个功能段的流水线Ｄ）动态连接的流水线4．网络直径与网络的（）有关 A）度B）链路总数 C）结点间通信经过的最多链路数D）通信延迟 5．下列关于存储器的描述，哪个是正确的（） A）多体交叉存储器主要解决扩充容量问题 B）Cache的功能全由硬件完成 C）Cache与主存统一编址，即主存空间的某一部分属于Cache D）“主存—外存”的存储层次是为了弥补主存速度的不足 6．在单指令流多数据流计算机中各处理单元必须（）。 A）以同步方式在同一时间内执行不同的指令 B）以同步方式在同一时间内执行相同的指令 C）以异步方式在同一时间内执行相同的指令 D）以异步方式在同一时间内执行不同的指令 7．虚拟存储器地址变换是指（）。 A）多用户虚地址与实地址如何一一对应 B）程序的逻辑地址变换成主存实地址 C）程序执行时将虚地址变换成对应的实存地址 D）指令的符号地址变换成二进制地址
8．反映网络在理想通信模式下通信带宽的特性是（） A）度B）直径C）带宽总和D）等分带宽 9．依据Michael J.Flynn提出的按指令流和数据流的多倍性对计算机系统分类，Illiac IV计算机属于（）A）SISD B）SIMD C）MISD D）MIMD 10．全相联地址映象是指（）。 A）任何主存页都可装入Cache中任何页的位置 B) 一个虚页只装进固定的主存实页位置 C ) 组之间是固定的，而组内任何主存页可以装入任何Cache页位置 D) 组间可任意装入，组内是固定装入 二、名词解释题（本大题共5小题，每小题4分，共20分）解释每小题所给名词的含义，若解释正确则给分，若 解释错误则无分，若解释不准确或不全面，则酌情扣分。 1．目录表 2．阻塞网络 3. 写直达法 4. 乱序流动 5. 向量链接技术 三、简答题（本大题共4小题，共25分） 1.（5分）存储程序计算机(冯氏机)在系统结构上的主要特点是什么？ 2．（5分）在cache容量一定的情况下,增加cache中的块大小能否达到提高cache命中率的效果?为什么? 3．（5分）解释数据相关（局部相关）与控制相关（全局相关）。 4．（10分）有哪几种向量处理方式？它们对向量处理机的结构要求有何不同？ 四、综合题（本大题共4小题，共35分） 1. (5分)某计算机系统采用浮点运算部件后使浮点运算速度提高到原来的20倍，而系统运行一程序 的整体性能提高到原来的10倍，试计算该程序中浮点操作所占的比例。
第一章计算机体系结构的基本概念 1.层次结构——计算机系统可以按语言的功能划分为多级层次结构，每一层以不同的语言为 2.计算机体系结构：程序员看到的计算机的属性，即概念性结构和功能特性。 3.实质是计算机系统中软硬件界面的确定。 4.翻译——（基于层次结构）先把N+1级程序全部变换成N级程序之后，再去执行N级程序， 在执行过程中，N+1级程序不再被访问。 5.解释——每当一条N+1级指令被译码后，就直接去执行一串等效的N级指令，然后再去取下 一条N+1级指令，依此重复执行。 6.体系结构——程序员所看到的计算机的属性，即概念性结构与功能特性。主要研究计算机 系统软件和硬件的功能分配以及如何最佳、最合理地实现分配给硬件的功能。 8.透明性——在计算机技术中，对本来存在的事物或属性，从某一角度来看又好像不存在的 概念称为透明性。 9.系列机——在一个厂家生产的具有相同的体系结构，但具有不同的组成和实现的一系列不 同型号的机器。 10.软件兼容——同一个软件可以不加修改地运行于体系结构相同的各档机器上，而且它们所 获得的结果一样，差别只在于运行的时间不同。 11.兼容机——不同厂家生产的、具有相同体系结构的计算机。 12.计算机组成——计算机体系结构的逻辑实现。 13.计算机实现——计算机组成的物理实现。 14.存储程序计算机（冯·诺依曼结构）——采用存储程序原理，将程序和数据存放在同一存 储器中。指令在存储器中按其执行顺序存储，由指令计数器指明每条指令所在的单元地址。 15.并行性——在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。 16.时间重叠——在并行性中引入时间因素，即多个处理过程在时间上相互错开，轮流重叠地 使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。 17.资源重复——在并行性中引入时间因素，是根据“以数量取胜”的原则，通过重复设置资源， 尤其是硬件资源，大幅度提高计算机系统的性能。
2014年《并行计算系统》复习题 1.（15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM）
⑤工作站机群（COW） 2.（10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短
访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2
对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10 并行比例因子:9/10 （2）如果有10个处理机并行执行该程序，可达到的加速比是多少？10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？10/(9/20 + 1)= 6.897 5.（15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。 可扩放性包括: 1.机器规模的可扩放性
填空题 1.从2002年以来，计算机性能的年增长率下降到了约30％。其主要原因是：①大功耗问题； ②可以进一步有效地开发的指令级并行性已经很少；③存储器访问速度的提高缓慢。 2. 可移植性是指一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。实现可移植性的常用方法有3种：系列机，模拟和仿真，统一高级语言。 2.通用寄存器型指令集结构计算机在灵活性和提高性能方面有明显的优势。主要体现在①寄存器的访问 速度比存储器快；②对编译器而言，能更加容易有效地分配和使用寄存器；③寄存器可以用来存放变量。 3.MIPS的数据寻址方式只有立即数寻址和偏移量寻址。 4.向量处理机的结构由所采用的向量处理方式决定。有两种典型的结构；存储器-存储器型结构和寄存器-寄存器型结构。 5.Cache-主存层次的工作由硬件实现，对系统程序员是透明的。 6.降低Cache不命中率最直接的方法是增加Cache的容量。不过，这种方法不但会增加成本，而且还可能增加命中时间，这种方法在片外Cache中用得比较多。 7.大多数磁盘阵列的组成可以由以下两个特征来区分：数据交叉存放的粒度、冗余数据的计算方法以及在磁盘阵列中的存放方式。 8.时延和带宽是用来评估互连网络性能的两个基本指标。时延包括通信时延和网络时延。 9.计算机系统可分为SISD、SIMD、MISD和MIMD四类，许多早期并行处理机是SIMD计算机，近年来，MIMD已经成为通用多处理机系统结构的选择。这是因为MIMD具有灵活性，并且MIMD 能充分利用现有微处理器的性价比优势。 判断题 1.从计算机语言的角度，系统结构把计算机系统按功能划分成多级层次结构，其中，第2级是操作系统虚拟机，第３级是汇编语言虚拟机。（错） 2.计算机系统中提高并行性的3种途径中，资源重复是在并行性概念中引入时间因素，加快硬件周转而赢得时间。（错） 3.指令集结构中采用多种寻址方式可能会增加实现的复杂度和使用这些寻址方式的指令的CPI。（对） 4.指令条数多，通常超过200条，是设计RISC的原则之一。（错） 5.根据流水线中各功能段之间是否有反馈回路，可把流水线分为线性流水线和非线性流水线。（对） 6.在多级存储体系中，“主存一辅存”层次的存储管理实现主要由软件实现。（对） 7.失效率和平均访存时间都可评价存储系统的性能，它们都和机器的硬件速度有关。(错) 8.RAID的特点有容量大，速度快、可靠性高，同时保存数据无冗余信息。(对) 9.在多处理机的互连网络中，交叉开关网络属于动态互连网络。（对） 10.机群是一种价格低廉、易于构建、可扩缩性极强的并行计算机系统。（对） 名词解释 1.RISC 精简指令集计算机是一种执行较少类型计算机指令的微处理器 2.请求字优先 调块时，首先向存储器请求CPU所要的请求字。请求字一旦到达，就立即送往CPU，让CPU继续执行，同时从存储器调入该块的其余部分。 3.单一系统映像
第1章计算机系统结构的基本概念 (1) 第2章指令集结构的分类 (10) 第3章流水线技术 (15) 第4章指令级并行 (37) 第5章存储层次 (55) 第6章输入输出系统 (70) 第7章互连网络 (41) 第8章多处理机 (45) 第9章机群 (45) 第1章计算机系统结构的基本概念 1.1 解释下列术语 层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。 虚拟机：用软件实现的机器。 翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。
解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。 计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。 计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。 系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。 Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。 程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。
Reviews on parallel programming并行计算英文班复习考试范围及题型：（1—10章） 1 基本概念解释；Translation (Chinese) 2 问答题。Questions and answer 3 算法的画图描述。Graphical description on algorithms 4 编程。Algorithms Reviews on parallel programming并行计算 1 基本概念解释；Translation (Chinese) SMP MPP Cluster of Workstation Parallelism, pipelining, Network topology, diameter of a network, Bisection width, data decomposition, task dependency graphs granularity concurrency process processor, linear array, mesh, hypercube, reduction,
prefix-sum, gather, scatter, thread s, mutual exclusion shared address space, synchronization, the degree of concurrency, Dual of a communication operation, 2 问答题。Questions and answer Chapter 1 第1章 1) Why we need parallel computing? 1）为什么我们需要并行计算？ 答： 2) Please explain what are the main difference between parallel computing and sequential computing 2）解释并行计算与串行计算在算法设计中的主要不同点在那里？ 答： Chapter 2 第2章 1) What are SIMD, SPMD and MIMD denote? 1）解释SIMD, SPMD 和 MIMD是什么含义。 答： 2) Please draw a typical architecture of SIMD and a typical architecture of MIMD to explan. 2）请绘制一个典型的SIMD的体系结构和MIMD的架构。 答：
第1章计算机系统结构得基本概念 (1) 第2章指令集结构得分类 (4) 第3章流水线技术 (6) 第4章指令级并行 (16) 第5章存储层次 (25) 第6章输入输出系统 (31) 第7章互连网络 (41) 第8章多处理机 (45) 第9章机群 (45) 第1章计算机系统结构得基本概念 1、1 解释下列术语 层次机构:按照计算机语言从低级到高级得次序,把计算机系统按功能划分成多级层次结构,每一层以一种不同得语言为特征。这些层次依次为:微程序机器级,传统机器语言机器级,汇编语言机器级,高级语言机器级,应用语言机器级等。 虚拟机:用软件实现得机器。 翻译:先用转换程序把高一级机器上得程序转换为低一级机器上等效得程序,然后再在这低一级机器上运行,实现程序得功能。 解释:对于高一级机器上得程序中得每一条语句或指令,都就是转去执行低一级机器上得一段等效程序。执行完后,再去高一级机器取下一条语句或指令,再进行解释执行,如此反复,直到解释执行完整个程序。 计算机系统结构:传统机器程序员所瞧到得计算机属性,即概念性结构与功能特性。 在计算机技术中,把这种本来存在得事物或属性,但从某种角度瞧又好像不存在得概念称为透明性。 计算机组成:计算机系统结构得逻辑实现,包含物理机器级中得数据流与控制流得组成以及逻辑设计等。 计算机实现:计算机组成得物理实现,包括处理机、主存等部件得物理结构,器件得集成度与速度,模块、插件、底板得划分与连接,信号传输,电源、冷却及整机装配技术等。 系统加速比:对系统中某部分进行改进时,改进后系统性能提高得倍数。 Amdahl定律:当对一个系统中得某个部件进行改进后,所能获得得整个系统性能得提高,受限于该部件得执行时间占总执行时间得百分比。 程序得局部性原理:程序执行时所访问得存储器地址不就是随机分布得,而就是相对地簇聚。包括时间局部性与空间局部性。 CPI:每条指令执行得平均时钟周期数。 测试程序套件:由各种不同得真实应用程序构成得一组测试程序,用来测试计算机在各个方面得处理性能。 存储程序计算机:冯·诺依曼结构计算机。其基本点就是指令驱动。程序预先存放在计算机存储器中,机器一旦启动,就能按照程序指定得逻辑顺序执行这些程序,自动完成由程序所描述得处理工作。 系列机:由同一厂家生产得具有相同系统结构、但具有不同组成与实现得一系列不同型号得计算机。 软件兼容:一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
计算机体系结构试题及答案 1、计算机高性能发展受益于：(1) 电路技术的发展；(2) 计算机体系结构技术的发展。 2、层次结构：计算机系统可以按语言的功能划分为多级层次结构，每一层以不同的语言为特征。第六级：应用语言虚拟机-> 第五级：高级语言虚拟机-> 第四级：汇编语言虚拟机-> 第三级：操作系统虚拟机->第二级：机器语言(传统机器级) -> 第一级：微程序机器级。 3、计算机体系结构：程序员所看到的计算机的属性，即概括性结构与功能特性。 4、透明性：在计算机技术中，对本来存在的事物或属性，从某一角度来看又好像不存在的概念称为透明性。 5、Amdahl 提出的体系结构是指机器语言级程序员所看见的计算机属性。 6、经典计算机体系结构概念的实质3是计算机系统中软、硬件界面的确定，也就是指令集的设计，该界面之上由软件的功能实现，界面之下由硬件和固件的功能来实现。 7、计算机组织是计算机系统的逻辑实现；计算机实现是计算机系统的物理实现。
8、计算机体系结构、计算机组织、计算机实现的区别和联系？ 答：一种体系结构可以有多种组成，一种组成可以有多种物理实现，体系结构包括对组织与实现的研究。 9、系列机：是指具有相同的体系结构但具有不同组织和实现的一系列不同型号的机器。 10、软件兼容：即同一个软件可以不加修改地运行于系统结构相同的 各机器，而且它们所获得的结果一样，差别只在于运行时间的不同。 11、兼容机：不同厂家生产的、具有相同体系结构的计算机。 12、向后兼容是软件兼容的根本特征，也是系列机的根本特征。 13、当今计算机领域市场可划分为：服务器、桌面系统、嵌入式计算三大领域。 14、摩尔定律：集成电路密度大约每两年翻一番。 15、定量分析技术基础（1）性能的评测：（a）响应时间：从事件开始到结束之间的时间；计算机完成某一任务所花费的全部时间。（b）流量：单位时间内所完成的工作量。（c ）假定两台计算机x 、y；x 比y 快意思为：对于给定任务，x 的响应时间比y少。x的性能是y的几倍是指：响应时间x / 响应时间y = n ，响应时间与性能成反比。
计算机体系结构课后答案
计算机体系结构课后答案 【篇一：计算机体系结构习题(含答案)】 1、尾数用补码、小数表示，阶码用移码、整数表示，尾数字长p=6（不包括符号位），阶码字长q=6（不包括符号位），为数基值rm=16，阶码基值re=2。对于规格化浮点数，用十进制表达式写出如下数据（对于前11项，还要写出16进值编码）。 （1）最大尾数（8）最小正数 （2）最小正尾数（9）最大负数 （3）最小尾数（10）最小负数 （4）最大负尾数（11）浮点零 （5）最大阶码（12）表数精度 （6）最小阶码（13）表数效率 （7）最大正数（14）能表示的规格化浮点数个数 2．一台计算机系统要求浮点数的精度不低于10-7.2，表数范围正数不小于1038，且正、负数对称。尾数用原码、纯小数表示，阶码用移码、整数表示。 (1) 设计这种浮点数的格式 (2) 计算（1）所设计浮点数格式实际上能够表示的最大正数、最大负数、表数精度和表数效率。 3．某处理机要求浮点数在正数区的积累误差不大于2-p-1 ，其中，p是浮点数的尾数长度。 (1) 选择合适的舍入方法。
(2) 确定警戒位位数。 (3) 计算在正数区的误差范围。 4．假设有a和b两种不同类型的处理机，a处理机中的数据不带标志符，其指令字长和数据字长均为32位。b处理机的数据带有标志符，每个数据的字长增加至36位，其中有4位是标志符，它的指令数由最多256条减少到不到64条。如果每执行一条指令平均要访问两个操作数，每个存放在存储器中的操作数平均要被访问8次。对于一个由1000条指令组成的程序，分别计算这个程序在a处理机和b处理机中所占用的存储空间大小（包括指令和数据），从中得到什么启发？ 5．一台模型机共有7条指令，各指令的使用频率分别为35%，25%，20%，10%，5%，3%和2%，有8个通用数据寄存器，2个变址寄存器。 (1) 要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。 6．某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令3类，并假设每个地址字 段的长度均为6位。 (1) 如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这3类指令分配操作码。 (2) 如果要求3类指令的比例大致为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这3类指令分配操作码。 7．别用变址寻址方式和间接寻址方式编写一个程序，求c=a+b，其中，a与b都是由n个元素组成的一维数组。比较两个程序，并回答下列问题： (1) 从程序的复杂程度看，哪一种寻址方式更好？
一．名词解释 2:1Cache经验规则：大小为N的直接印象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。 通道处理机：通道的专用处理机，来专门负责整个计算机体系的输入/输出工作。通道处理机只能执行有限的一组输入/输出指令。 透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。 向量处理机：设置了向量数据表示和相应的向量指令的流水线处理机称为向量处理机。 虚拟Cache：直接用虚拟地址进行访问的Cache 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。 同构型多处理机系统：由多个同类型或至少担负同等功能的处理机组成，它们同时处理同一作业中能并行执行的多个任务。 堆栈型机器：CPU 中存储操作数的单元是堆栈的机器。 累加器型机器：CPU 中存储操作数的单元是累加器的机器。 通用寄存器型机器：CPU 中存储操作数的单元是通用寄存器的机器。 数据相关：考虑两条指令i和j，i在j的前面，如果下述条件之一成立，则称指令j与指令i数据相关： （1）指令j使用指令i产生的结果； （2）指令j与指令k数据相关，而指令k又与指令i数据相关。 定向：用来解决写后读冲突的。在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不见得是马上就要用该结果。如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。 指令级并行：简称ILP。是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。 指令的动态调度：是指在保持数据流和异常行为的情况下，通过硬件对指令执行顺序进行重新安排，以提高流水线的利用率且减少停顿现象。是由硬件在程序实际运行时实施的。 指令的静态调度：是指依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化的。 失效率：CPU访存时，在一级存储器中找不到所需信息的概率。 失效开销：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。 强制性失效：当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。 容量失效：如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。 冲突失效：在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。RAID：廉价磁盘冗余阵列或独立磁盘冗余阵列。 通道：专门负责整个计算机系统输入/输出工作的专用处理机，能执行有限的一组输入输出指令。 通道流量：指一个通道在数据传送期间，单位时间内能够传送的数据量。 互连网络：一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系
计算机网络课后习题答案（第三章） (2009-12-14 18:16:22) 转载▼ 标签： 课程-计算机 教育 第三章数据链路层 3-01 数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。 “电路接通了”表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是“数据链路接通了”，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。 3-02 数据链路层中的链路控制包括哪些功能?试讨论数据链路层做成可靠的链路层有哪些优点和缺点. 答：链路管理 帧定界 流量控制 差错控制 将数据和控制信息区分开 透明传输 寻址 可靠的链路层的优点和缺点取决于所应用的环境：对于干扰严重的信道，可靠的链路层可以将重传范围约束在局部链路，防止全网络的传输效率受损；对于优质信道，采用可靠的链路层会增大资源开销，影响传输效率。 3-03 网络适配器的作用是什么?网络适配器工作在哪一层? 答：适配器（即网卡）来实现数据链路层和物理层这两层的协议的硬件和软件 网络适配器工作在TCP/IP协议中的网络接口层（OSI中的数据链里层和物理层） 3-04 数据链路层的三个基本问题(帧定界、透明传输和差错检测)为什么都必须加以解决？ 答：帧定界是分组交换的必然要求 透明传输避免消息符号与帧定界符号相混淆
3.某模型机有10条指令I1～I10，它们的使用频度分别为0.3，0.24，0.16，0.12，0.07，0.04，0.03，0.02， 0.01，0.01。 (1)计算采用等长操作码表示时的信息冗余量。 (2)要求操作码的平均长度最短，试设计操作码的编码，并计算所设计操作码的平均长度。 (3)只有二种码长，试设计平均码长最短的扩展操作码编码并计算平均码长。 (4)只有二种码长，试设计平均码长最短的等长扩展码编码并计算平均码长。 3.(1)采用等长操作码表示时的信息冗余量为33.5%。 (2)操作码的Huffman编码法如表2.2所示，此种编码的平均码长为2.7位。 表2.2 操作码的Huffman编码法、2-5扩展码和2-4等长扩展码编码法 指令指令使用 频度p i Huffman编码 操作码 长度l i 2-5扩展码 操作码 长度l i 2-4等长扩 展码 操作码 长度l i I1 0.3 0 0 2 0 0 2 0 0 2 I2 0.24 1 0 2 0 1 2 0 1 2 I3 0.16 0 1 0 3 1 0 2 1 0 0 0 4 I4 0.12 0 1 1 3 1 1 0 0 0 5 1 0 0 1 4 I5 0.07 1 1 0 3 1 1 0 0 1 5 1 0 1 0 4 I6 0.04 1 1 1 0 0 5 1 1 0 1 0 5 1 0 1 1 4 I7 0.03 1 1 1 0 1 5 1 1 0 1 1 5 1 1 0 0 4 I8 0.02 1 1 1 1 0 5 1 1 1 0 0 5 1 1 0 1 4 I9 0.01 1 1 1 1 1 0 6 1 1 1 0 1 5 1 1 1 0 4 I10 0.01 1 1 1 1 1 1 6 1 1 1 1 0 5 1 1 1 1 4 (3)操作码的2-5扩展码编码法如表2.2所示，此种编码的平均码长为2.9位。 (4)操作码的2-4等长扩展码编码法如表2.2所示，此种编码的平均码长为2.92位。 5.若某机设计有如下格式的指令： 三地址指令12种，一地址指令254种，设指令字的长度为16位，每个地址码字段的位数均为4位。若操作码的编码采用扩展操作码，问二地址指令最多可以设计多少种？ 5.二地址指令最多可以设计48种。 6.一台模型机共有9条指令I1～I9，各指令的使用频度分别为30%，20%，20%，10%，8%，6%，3%，2%，1%。该模型机有8位和16位两种指令字长。8位字长指令为寄存器-寄存器（R-R）二地址类型，16位字长指令为寄存器-存储器（R-M）二地址变址寻址类型。 (1)试设计有二种码长的扩展操作码，使其平均码长最短，并计算此种编码的平均码长。 (2)在(1)的基础上，该机允许使用多少个可编址的通用寄存器？ (3)若采用通用寄存器作为变址寄存器，试设计该机的两种指令格式，并标出各字段的位数。 (4)计算变址寻址的偏移地址范围。 6.(1)操作码的2-5扩展码编码法如表2.3所示，此种编码的平均码长为2.9位。 表2.3 操作码的Huffman编码法和2-4等长扩展码编码法 指令指令使用频度p i 2-5扩展码操作码长度l i I1 0.3 0 0 2 I2 0.2 0 1 2 I3 0.2 1 0 2 I4 0.1 1 1 0 0 0 5 I5 0.08 1 1 0 0 1 5
第二章习题（P69-70） 一、复习题 1．简述冯?诺依曼原理，冯?诺依曼结构计算机包含哪几部分部件，其结构以何部件为中心？ 答：冯?诺依曼理论的要点包括：指令像数据那样存放在存储器中，并可以像数据那样进行处理；指令格式使用二进制机器码表示；用程序存储控制方式工作。这3条合称冯?诺依曼原理 冯?诺依曼计算机由五大部分组成：运算器、控制器、存储器、输入设备、输出设备，整个结构一般以运算器为中心，也可以以控制器为中心。 (P51-P54) 2．简述计算机体系结构与组成、实现之间的关系。 答：计算机体系结构通常是指程序设计人员所见到的计算机系统的属性，是硬件子系统的结构概念及其功能特性。计算机组成（computer organization）是依据计算机体系结构确定并且分配了硬件系统的概念结构和功能特性的基础上，设计计算机各部件的具体组成，它们之间的连接关系，实现机器指令级的各种功能和特性。同时，为实现指令的控制功能，还需要设计相应的软件系统来构成一个完整的运算系统。计算机实现，是计算机组成的物理实现, 就是把完成逻辑设计的计算机组成方案转换为真实的计算机。计算机体系结构、计算机组成和计算机实现是三个不同的概念，各自有不同的含义，但是又有着密切的联系，而且随着时间和技术的进步，这些含意也会有所改变。在某些情况下，有时也无须特意地去区分计算机体系结构和计算机组成的不同含义。 (P47-P48) 3．根据指令系统结构划分，现代计算机包含哪两种主要的体系结构？ 答：根据指令系统结构划分，现代计算机主要包含：CISC和RISC两种结构。 (P55) 4．简述RISC技术的特点？ 答：从指令系统结构上看，RISC 体系结构一般具有如下特点： (1) 精简指令系统。可以通过对过去大量的机器语言程序进行指令使用频度的统计，来选取其中常用的基本指令，并根据对操作系统、高级语言和应用环境等的支持增设一些最常用的指令; (2) 减少指令系统可采用的寻址方式种类，一般限制在2或3种; (3) 在指令的功能、格式和编码设计上尽可能地简化和规整，让所有指令尽可能等长; (4) 单机器周期指令，即大多数的指令都可以在一个机器周期内完成，并且允许处理器在同一时间内执行一系列的指令。 (P57-58) 5．有人认为，RISC技术将全面替代CISC，这种观点是否正确，说明理由？ 答：不正确。与CISC 架构相比较，RISC计算机具备结构简单、易于设计和程序执行效率高的特点，但并不能认为RISC 架构就可以取代CISC 架构。事实上，RISC 和CISC 各有优势，CISC计算机功能丰富，指令执行更加灵活，这些时RISC计算机无法比拟的，当今时代，两者正在逐步融合，成为CPU设计的新趋势。 (P55-59) 6．什么是流水线技术？ 答：流水线技术，指的是允许一个机器周期内的计算机各处理步骤重叠进行。特别是，当执行一条指令时，可以读取下一条指令，也就意味着，在任何一个时刻可以有不止一条指令在“流水线”上，每条指令处在不同的执行阶段。这样，即便读取和执行每条指令的时间保持不变，而计算机的总的吞吐量提高了。 (P60-62) 7．多处理器结构包含哪几种主要的体系结构，分别有什么特点？ 答：多处理器系统：主要通过资源共享，让共享输入/输出子系统、数据库资源及共享或不共享存储的一组处理机在统一的操作系统全盘控制下，实现软件和硬件各级上相互作用，达到时间和空间上的异步并行。 SIMD计算机有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为他们
第三章互连网络 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。 答： 推广至M元树时，k级M元树总结点数N的表达式为： N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m); 二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络 答：8输入的完全混洗三级互联网络。 四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树 答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么 答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 一个N=2^k个节点的 de Bruijin 。 。。。试问：该网络的直径和对剖宽度是多少 答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1)
一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度== 答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度= 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问： 1）这将会发生什么现象 2）如果采用X-Y选路策略，可避免上述现象吗为什么 答： 1）通路中形成环，发生死锁
计算机学院研究生《并行计算》课程 考试试题 （2010级研究生，2011.1） 1．（12分）定义图中节点u 和v 之间的距离为从u 到v 最短路径的长度。已知一个d 维的超立方体，1）指定其中的一个源节点s ，问有多少个节点与s 的距离为i ，其中0≤i ≤d 。证明你的结论。2）证明如果在一个超立方体中节点u 与节点v 的距离为i ，则存在i ！条从u 到v 的长度为i 的路径。 1)有i d C 个节点与s 的距离为i 。 证明：由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节 点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有i d C 种选择方式，即与s 的距离为i 得节点就有i d C 个。 2) 证明：由1）所述可知： 节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为： ''121D .........j j i j i d D D D D D +-+，则现在就是要求得从 121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多 少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。所以存在i ！条从u 到v 的长度为i 的路径。 2．（18分）6个并行程序的执行时间，用I-VI 表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。
第1章计算机系统结构的基本概念 1.1 解释下列术语 层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。 虚拟机：用软件实现的机器。 翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。 解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。 计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。 计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。 系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。 Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。 程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。 CPI：每条指令执行的平均时钟周期数。 测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的处理性能。 存储程序计算机：冯·诺依曼结构计算机。其基本点是指令驱动。程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。 系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。 软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。 向上（下）兼容：按某档计算机编制的程序，不加修改就能运行于比它高（低）档的计算机。向后（前）兼容：按某个时期投入市场的某种型号计算机编制的程序，不加修改地就能运行于在它之后（前）投入市场的计算机。 兼容机：由不同公司厂家生产的具有相同系统结构的计算机。 模拟：用软件的方法在一台现有的计算机（称为宿主机）上实现另一台计算机（称为虚拟机）的指令系统。 仿真：用一台现有计算机（称为宿主机）上的微程序去解释实现另一台计算机（称为目标机）的指令系统。 并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相
2.1 对于一颗K 级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m 个子节点）时，试写出总节点数N 的表达式。 答： 推广至M 元树时，k 级M 元树总结点数N 的表达式为： N=1+m 1+m 2+...+m （k-1）=(1-m k )*1/(1-m); 2.4 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？ 答： N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径 d=9，节点度n=4 4.11 一个在p 个处理器上运行的并行程序加速比是p-1，根据Amdahl 定律，串行分量为多少? 答： p/(1+f(p-1))=p-1, f=1/(p-1)2 5.5假定开始时P i (1《i 《n)存有数据 d i ，所谓累加求和是指用 ∑=i j i d 1，来代替中的原始值d i ，算法5.3给出了在PRAM 模型上累加求和算法。 Input: di are kept in Pi, where Output: replaces di in processor Pi Begin for j=0 to logn-1 do for i=2j +1 to n par-do (i) di= d i + d i-2j (ii) Pi=di end for end for End (1）试用n=8为例子，按照上述算法逐步计算出累加和。 (2）分析算法的时间复杂度。
6.3 7.2（1） 例:A={1,3,6,8,11,13} p=6;B={2,4,5,7,10,12,14} ,q=7 p =3, q =3 A={1,3,6*,8,11,13*} B={2,4,5*,7,10 ,12*,14}, B ’={2,4,5,6*,7,10 12,13*,14} A11={1,3} , A12={8,11} , A13={} B11={2,4,5} , B12={7,10 12} , B13={14} A11={1,3*} , A12={8,11*} , B11={2,4*,5} , B12={7,10* , 12} , B11’={2, 3* , 4,5} , B12’={7,10 , 11* , 12} , A111={1},A112={} A121={8},A122={} B111={2},B112={4,5} B121={7,10 },B122={12} A111={1 *} A121={8 *} B111={2 *} B121={7,10 * } 33 54 21 13 33 82 40 72