哈尔滨工程大学研究生并行体系结构期末考试资料（并行体系结构11.docx）

简介：
本资料为哈尔滨工程大学研究生课程《并行体系结构》期末考试复习材料，涵盖教学大纲核心知识点与例题解析，适用于备考使用。 哈工程研究生并行体系结构期末考试知识点总结 一、并行计算模型 PRAM 模型（并行随机访问机模型）：机器规模 n 可任意大；基本时间步称为周期；在一个周期内每个处理器只执行一条指令；每一周期内所有处理器同步，同步开销为零；一条指令可以是任何随机访问指令。 BSP 模型（块同步模型）：基本时间步是超步，包括计算、通信和路障；它是松同步、非零开销，并且可变颗粒度的 MIMD 机器模型。 二、并行计算性能 SP2 的点对点通讯表达式为 t(m)=46+0.035m。启动开销 t0=46 μs，渐进带宽 r∞=1/0.035≈28.57MB/s，半峰值消息长度 m12=t0*r∞=1314B。 三、Amdahl 定律 固定问题规模的 Amdahl 定律：Sn=Wα/(W+(1-α) W n)=n / (1 + (n - 1)* α ) → 1/α，当 n→∞ 含义： 对于给定的工作负载，其最大加速比的上限为 1/α。 为了获取好的加速比，应使顺序瓶颈 α 尽可能地小。 如果一个问题由两部分组成，则应设法让较大那部分执行得更快。 考虑开销 T0 的固定问题规模 Amdahl 定律：Sn=W*α/(W+(1-α) W n)+T 0 =n / (1 + (n - 1)* α )+ n *T 0/W→1/α + T 0/W，当 n→∞ 四、基准程序 按应用类型分类有科学计算、商业应用、网络服务和多媒体应用等。 按照计算机系统来分有两种：宏基准程序和微基准程序。 宏基准程序测量的是一个计算机系统的总体性能，但不能揭示导致其运行好坏的原因；而微基准程序则专注于衡量某一方面的性能如 CPU 速度或存储器速度。 五、并行程序中的开销 在并行计算中可以将开销分为三类：负载不平衡开销，并行性相关开销以及交互操作相关的同步和通信等。 额外的并行化成本包括了并行性和交互两个方面。 六、PRAM 步中的计算复杂性 假设存在三个 PRAM 算法 A, B 和 C，当在有 n 个处理器的 PRAM 计算机上执行时，各自的时间复杂度分别为A--7n，B--(nlogn)/4和C--nloglogn。 根据大O符号：算法A最快为 O(n)，接着是 C 即 O(n log(log n))，而 B 最慢即 O(n log n)。 七、并行处理中的通信开销 在进行并行处理时通常认为随着使用的节点数量增加，通讯成本也会随之上升。然而通过实例可以发现这种观点可能是错误的。 例如，在 APT 程序中当使用不超过256个结点时，总的通信量会随机器规模增大而减少。 八、系统性能分析 对于拥有 256 个节点的系统，T0(∞)= T0(256) = 0.0479 秒 计算最大并行性、总工作负载、执行时间、关键路径长度、最大性能值以及平均并行性和颗粒度。 假设忽略通信开销，则加速比（串行时间/ 并行时间）可以用来衡量系统效率。 需要求解该系统的运行时间和加速比分别是多少。 结论：固定负载下的加速比会随着顺序瓶颈和平均开销的增加而急剧下降，单纯通过添加更多的处理器来解决顺序瓶颈问题是无效的。可以通过同时增大机器规模并提高可并行计算的比例来改善性能。