哈工程，研究生，并行体系结构，期末考试，并行体系结构11.docx

"哈工程研究生并行体系结构期末考试知识点总结" 一、并行计算模型 * PRAM 模型（并行随机访问机模型）：机器规模 n 可任意大；基本时间步称为周期；在一个周期内每个处理器只执行一条指令；每一周期内所有处理器同步，同步开销为零；一条指令可以是任何随机访问指令。 * BSP 模型（块同步模型）：基本时间步是超步，包括计算、通信和路障；它是松同步、非零开销，且可变颗粒度的 MIMD 机器模型。 二、并行计算性能 * SP2 的点对点通讯表达式：t(m)=46+0.035m * 启动开销 t0=46 μs，渐进带宽 r∞=1/0.035=28.57MB/s，半峰值消息长度 m1/2= t0* r∞=1314B 三、Amdahl 定律 * 固定问题规模 Amdahl 定律：Sn=WαW+(1−α )(W /n)=n1+(n−1)α → 1α，当 n→∞ * 含义： 1. 对于给定的工作负载，其最大加速比的上限为 1/α。 2. 为获取好的加速比，很重要的是应使顺序瓶颈 α 尽可能地小。 3. 当一个问题由以上两部分组成时，我们应设法使较大部分执行的更快。 * 考虑开销 T0 的固定问题规模 Amdahl 定律：Sn=WαW+(1−α )(W /n)+T 0 =n1+(n−1)α+ nT 0W→1α+ T 0W，当 n→∞ 四、基准程序 * 按应用类型：科学计算、商业应用、网络服务、多媒体应用等 * 按计算机系统来分：宏基准程序、微基准程序两类 + 宏基准程序：测量一个计算机系统的总体性能。但不能揭示系统运行好坏的原因。 + 微基准程序：测量一个计算机系统的某一特定方面性能，如 CPU 速度、存储器速度操作系统性能、I/O 速度等。 五、并行程序中的开销 * 并行程序中的开销可分为 3 类：负载不平衡开销、并行性开销、交互开销（包括同步、通信和聚集） * 额外开销：并行开销，交互开销 六、PRAM 步中的计算复杂性 * 假设有三个 PRAM 算法 A、B 和 C，当在一个有 n 个处理器的 PRAM 计算机上执行时，各自的时间复杂性为A--7n，B--(nlogn)／4，C--nloglogn * 根据大 O 标志：算法 A 最快：(O(n))，C 次之：O(nloglogn)，B 为最慢：O(nlogn) 七、并行处理中的通信开销 * 并行处理中的一个观念是通信开销随所使用结点数的增加而增长。但由上面例子可见，这可能是错的。 * 在 APT 程序中当所使用结点不多于 256 时，总的通信开销随机器规模增加而减少。 八、系统性能分析 * 系统 256 个结点，T0(∞)=T0(256)=0.0479s * 求最大并行性、总工作负载、执行时间、关键路径、最大性能值、平均并行性、平均颗粒度 * 忽略通信开销，该系统较单一节点完成该程序的加速比加速比=串行时间/并行时间 * 系统运行时间和加速比分别是多少 * 结论：固定负载加速比随顺序瓶颈和平均开销增加而急剧下降，顺序瓶颈问题无法单纯用增加系统的处理器数目来解决。可以通过增加机器的规模的同时，增加可并行计算。