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.机器规模的可扩放性
系统性能是如何随着处理机数目的增加而改善的 2.问题规模的可扩放性
系统的性能是如何随着数据规模和负载规模的增加而改善 3.技术的可扩放性
系统的性能上如何随着技术的改变而改善
可扩放性研究的目的:
确定解决某类问题时何种并行算法与何种并行体系结构的组合，可以有效的利用大量的处理器；
对于运用于某种并行机上的某种算法，根据在小规模处理机的运行性能预测移植到大规模处理机上的运行性能;
对固定问题规模，确定最优处理机数和可获得的最大的加速比
6. （15分）给出五个基本的并行计算模型，并说明其各自的优缺点。 ①PRAM：SIMD-SM 优点：
适于表示和分析并行计算的复杂性；
隐匿了并行计算机的大部底层细节（如通信、同步），从而易于使用。 缺点：
不适于MIMD计算机，存在存储器竞争和通信延迟问题。 ②APRAM:MIMD-SM 优点：
保存了PRAM的简单性；
可编程性和可调试性（correctness）好； 易于进行程序复杂性分析。 缺点：
不适于具有分布式存储器的MIMD计算机。 ③BSP：MIMD-DM 优点:
把计算和通信分割开来；
使用hashing自动进行存储器和通信管理； 提供了一个编程环境。 缺点：
显式的同步机制限制并行计算机数据的增加； 在一个Superstep中最多只能传递h各报文。 ④LogP：MIMD-DM 优点：
可捕捉并行计算机的（同步）通信瓶颈（通过发送或接收L/g 个报文）； 可隐匿拓扑结构，路由算法和网络协议的细节； 可用于共享变量，报文传递和数据并行处理等方案。 缺点：
受限于网络的通信能力（当进行处理机数量扩充时）； 难以计算同步开销和进行算法描述和设计。 ⑤C3模型
优点：
考虑了一对一和一对多的通信方案细节； 反应了受拥塞影响的计算性能。 缺点：
模型的参数较复杂；
算法的设计与分析和计算机的结构状况有关。
7. （15分）说明并行算法的基本设计过程。 ①划分（P） 目的
开发并行性的可行性 方法
数据分解+功能分解 规划
常用的数据，通信频率的进程分为一组 判据（Check list 的设计问题） ②通信（C） 目的
根据任务执行的需要交换数据后；协调任务的执行 通信要求
在域分解中的确定通信要求 在功能分解时，容易确定通信需求
通信模式
局部通信 结构化 静态 同步 全局通信 非结构化 动态 异步 判据（测试表的设计问题） ③组合（A） 目的
按性能要求和时间的代价来考察前两阶段的结果对小的任务进行必要的组合以减少通信开销和提交性能 需回答8个方面的问题 判据（测试表的设计问题） ④匹配（M） 目的
将每个任务分配到一个处理机上，降低通信开销和执行时间，提高处理机利用率
判据（涉及策略，方法和测试表设计等问题）