13并行计算补考资料

1、UMA UMA是Uniform Memory Access （均匀存储访问）模型的缩写。在这种并行机中所 有的处理器均匀共享物理存储器。所有处理器访问任何存储字需要相同的时间（此即为均匀 存储访问名称的来源）。每台处理器可以有私有高速缓存。UMA的结构如下图所示。其中P 表示处理器，SM表示共享存储器。NUMA NUMA是Non-Uniform Memory Access （非均匀存储访问）模型的缩写。在NUMA 中，共享存储器在物理上是分布的，所有的本地存储器构成了全局地址空间。NUMA与UMA 的区别在于处理器访问本地存储器和群内共享存储器比访问远程存储器或全局共享存储器 快（此即非均匀存

2、储访问名称的由来）。下图中（a）表示共享本地存储器的NUMA结构，（b） 为层次式机群NUMA结构。LM表示本地存储器，GSM表示全局共享存储器，P表示处理器， CSM表示群内共享存储器，CIN表示机群互连网络。COMA COMA是Cache-Only Memory Architecture （全高速缓存存储结构）模型的缩写。 COMA实际是NUMA的一种特例，将NUMA中的分布存储器换成高速缓存就得到了 COMA。在COMA 中，每个结点上没有存储层次结构，所有的高速缓存构成了全局地址空间。访问远程高速缓 存要借助分布的高速缓存目录。COMA结构如下图所示。D表示高速缓存目录，C表示高速缓

3、存，P表示处理器。CC-NUMA CC-NUMA 是 Cache-Coherent Non-Uniform Memory AccessC 高速缓存一致性非 均匀存储访问）模型的缩写。CC-NUMA结构的并行机实际上是将一些SMP机作为结点互 连起来而构成的并行机。这样可以改善SMP机的可扩展性。绝大多数商用CC-NUMA多处 理机系统使用基于目录的高速缓存一致性协议；它的存储器在物理上是分布的，所有的局部 存储器构成了共享的全局地址空间（所以它实际上是一个DSM系统），因此它保留了 SMP 易于编程的优点。它最显著的优点是程序员无需明确地在结点上分配数据，系统的硬件和软 件开始时自动在各结点分

4、配数据。在程序运行过程中，高速缓存一致性硬件会自动地将数据 移至需要它的地方。CC-NUMA注重开拓数据的局部性和增强系统的可扩展性。在实际应用 中，大多数的数据访问都可在本结点内完成，网络上传输的主要是高速缓存无效性信息而不 是数据。CC-NUMA和COMA的共同特点是它们都对高速缓存一致性提供硬件支持，而在另一 种访存模型 NCC-NUMA（Non-Cache Coherent Non-Uniform Memory Access）中，则没有对 高速缓存的一致性提供硬件支持。NORMA NORMA是No-Remote Memory Access（非远程存储访问）模型的缩写。在NORMA 中，

5、所有的存储器都是处理器私有的，仅能由其处理器访问。各处理器之间通过消息传递方 式通信。MPP多采用这种结构。均匀访存模型（UMA）：均匀访存模型（UMA）中所有的物理存储器均被共享，即处 理器访问他们的时间是一样的。这种系统因为高度的资源共享也被称为紧耦合系统。非均匀访存模型（NUMA）：非均匀访存模型（NUMA）的特点是：被共享的存储物 理上是分布的，所有这些存储器的集合就是全局地址空间。所以处理处理访问这些存储器的 时间是不一样的，显然访问本地存储器要比访问全局共享存储器或者远程存储器要快些。另 外，存储器分层次，分为本地存储器，群内共享存储器，全局共享存储器。全高速缓存访存模型（COMA

6、）：是非均匀访存模型（NUMA）的一种特例，其中处理 各个节点无存储层次之分，各个节点的高速缓存构成了全部地址空间。一致性高速缓存非均匀存储访问模型（CC-NUMA）：每一个节点都是一个对称多处理 机，实际上是一个分布式多处理共享系统，在商业中大多数访问都在本地中进行，而网络上 传输的数据大多数用于高速缓存的无效性。非远程存储访问模型（NORMA）：非远程存储访问模型（NORMA）特点是：存储器保 存在本地或者是全局的共享分布式物理结构上，而并非是在远程地区存储。五种并行计算机体系结构1.并行向量处理机（PVP）貌型结杓I女又开关工 工Z3大规模并行处理机-CMPP） |SM2对称多机系统（S

7、MP）4分布式共享存储器多机系统（DSM）C2us1:c3mDesigned lletzwork |5工作站机群（COW）五种典型的访存模型答：（1）均匀访存模型（UMA）：均匀访存模型（UMA）中所有的物理存储器均被共享， 即处理器访问他们的时间是一样的。这种系统因为高度的资源共享也被称为紧耦合系统。（2）非均匀访存模型（NUMA）：非均匀访存模型（NUMA）的特点是：被共享的存 储物理上是分布的，所有这些存储器的集合就是全局地址空间。所以处理处理访问这些存储 器的时间是不一样的，显然访问本地存储器要比访问全局共享存储器或者远程存储器要快 些。另外，存储器分层次，分为本地存储器，群内共享存储

8、器，全局共享存储器。（3）全高速缓存访存模型（COMA）：是非均匀访存模型（NUMA）的一种特例，其 中处理各个节点无存储层次之分，各个节点的高速缓存构成了全部地址空间。（4）一致性高速缓存非均匀存储访问模型（CC-NUMA）：每一个节点都是一个对称多 处理机，实际上是一个分布式多处理共享系统，在商业中大多数访问都在本地中进行，而网 络上传输的数据大多数用于高速缓存的无效性。（5）非远程存储访问模型（NORMA）：非远程存储访问模型（NORMA）特点是：存 储器保存在本地或者是全局的共享分布式物理结构上，而并非是在远程地区存储。对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明

9、该网络是否是一 个对称网络。对剖宽度8对称，因为从任意节点上观看网络都是一样的。设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时， 不可并行化的部分为1个小时。问：（1）该程序的串行比例因子是多少，并行比例因子是多少？（2）如果有10个处理机并行执行该程序，可达到的加速比是多少?（3）如果有20个处理机并行执行该程序，可达到的加速比是多少?答：（1） 0.1 0.9-Ws+Wps=-(2)1 + 9 _ x =土26+110-Ws+Wp s=- -WsP=畀=6.89+120什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？答：一个计算

10、机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处 理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而 增加。主要包括：并行计算要调整的是处理数p和问题规模W。两者可按照不同的比例调整， 此比例关系（可能是线性的，多项式的或者指数型的）反映了可扩放的程度。研究目的是：确定解决某类问题用什么并行算法与何种并行体系组织结合，可以有效的 利用大量处理器。对于运行于某体系结构的并行机上的某种算法，当移植到大规模处理机上 后运行的性能。对于固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大 加速比。用于指导改进算法和并行体系结构，以使并行算法尽可能

11、的充分利用可扩充的大 量处理器。五个基本的并行计算模型，并说明其各自的优缺点。（1）PRAM : SIMD-SM 模型优点：适于表示和分析并行计算的复杂性；隐匿了并行计算机的大部底层细节（如通信、同步），从而易于使用。缺点：不适于MIMD计算机，存在存储器竞争和通信延迟问题。（2）APRAM:MIMD-SM 优点：保存了 PRAM的简单性；可编程性和可调试性（correctness）好；易于进行程序复杂性分析。缺点：不适于具有分布式存储器的MIMD计算机。（3）BSP: MIMD-DM 优点:把计算和通信分割开来；使用hashing自动进行存储器和通信管理；提供了一个编程环境。缺点：显式的同步机制限制并行计算机数据的增加；在一个Superstep中最多只能传递h各报文。（4）LogP: MIMD-DM 优点：可捕捉并行计算机的（同步）通信瓶颈（通过 S/R L/g报文）;可隐匿拓扑结构，路由算法和网络协议的细节；可用于共享变量，报文传递和数据并行处理等方案。缺点：受限于网络的通信能力（当进行处理机数量扩充时）；难以计算同步开销和进行算法描述和设计。（5）C3模型