并行计算期末考试重点：SIMD、MPI与CUDA并行模型

"2019年春季学期的并行计算期末考试试题，涉及并行计算的多种模型、算法效率、编程模型以及CUDA同步方法等核心知识点。" 在这次并行计算期末考试中，试题主要考察了以下几个方面的内容： 1. **并行计算体系结构分类**：题目中提到了SIMD-SM/MIMD-SM/SIMD-DM/MIMD-DM四种模型，PRAM(向量随机访问机)模型是（1）类型，APRAM模型是（2）类型，LogP模型是（3）类型。SIMD（单指令多数据）和MIMD（多指令多数据）是根据处理单元执行指令的方式区分的，而SM（共享内存）和DM（分布式内存）则基于内存架构。 2. **并行算法效率**：如果一个并行算法A在运行时间T(n)内执行运算量W(n)，那么使用p台处理器可以在（4）时间内完成。这是并行算法效率的基本概念，通常用工作负载和时间复杂度来衡量。 3. **SIMD结构上的算法性能**：对于求最大值的算法，在SIMD-EREW（无冲突单指令流数据）结构上，使用n/2个处理器可以在（5）时间内完成；而在SIMD-CRCW（冲突检测单指令流数据）结构上，使用n^2个处理器可以在（6）时间内完成。这反映了不同SIMD结构在处理并行计算时的效率差异。 4. **并行计算方法**：高斯-赛德尔迭代法五点格式的A矩阵是（7）对角矩阵，可以通过（8）方法进行并行化。高斯-赛德尔迭代法是求解线性系统的迭代方法，可以利用并行计算加速。 5. **并行编程模型**：OpenMP属于（9）共享内存并行编程模型，而MPI（Message Passing Interface）属于（10）分布式内存并行编程模型。 简答题部分涉及了以下知识点： 1. **并行计算概念**：SIMD（单指令多数据）、SPMD（单进程多数据）、SMP（对称多处理器）、PCAM（并行计算机体系结构模型）和Warp（CUDA中的线程束）的概念解释。 2. **MPI消息标签的作用**：MPI中使用消息标签来区分不同的消息，确保正确地将消息发送到目的地。 3. **稀疏矩阵求解方法**：稀疏方程组通常使用迭代法（如共轭梯度法）而非直接法（如高斯消元法）的原因，主要是因为迭代法更适合处理大规模稀疏问题，内存需求小且更高效。 4. **CUDA中的同步**：CUDA中CPU与GPU、线程块内、线程块间的同步方法和相关代码示例。 综合题部分则包含： 1. **OpenMP并行编程**：通过补全代码实现一个简单的并行计算任务，即计算两个数组的点乘结果，同时要求用另一种方式实现求和部分。 2. **环上收集算法**：描述环上收集（all-to-one）的选路算法（CT），并分析时间复杂度。 3. **PRAM下的前缀和算法**：分析课本中的算法7.9是否为并行成本最优，如果是哪种类型（EREW/CREW/CRCW），以及如何改进使其成为并行成本最优，并给出相应的伪代码和成本分析。 这些题目覆盖了并行计算的基础理论、模型、算法效率和实际编程应用，全面考察了学生对并行计算的理解和应用能力。