并行计算复习资料答案

4. BSP模型在简明性、性能的可预测性、可移植性和结构化可编程性等方面更受人欢迎和喜爱。

三者关系：

LogP和PRAM模型是并行计算模型的两个极端. BSP模型可以看成是上述两个模型的折衷.

相比之下,LogP模型过于复杂,缺乏有效的分析和性能预测的模型,而PRAM则过于简单,无法真实地描述物理机器。

BSP模型较好地综合了其它两个模型优点,在面向物理机器实现方面优于PRAM模型,而和LogP模型相比,又更加便于进行算法设计和性能预测。

（6）比较在 PRAM 模型和 BSP 模型上，计算两个 N 阶向量内积的算法及其复杂度。 PRAM点积：

BSP点积

每个处理器处理A的N/P个数值和B的N/P个数值，共N/P次乘法和N/P-1次加法

(7)什么是加速比（speed up） 、并行效率（efficiency）和可扩展性（scalability）? 如何描 述在不同约束下的加速比？

加速比：串行执行时间为 Ts ，使用 q 个处理机并行执行的时间为 Tp (q)，则加速比为

Sp(q)=Ts/Tp(q)。简单的说，并行系统的加速比是指对于一个给定的应用，并行算法

（或并行程序） 的执行速度相对于串行算法（或串行程序）的执行速度快了多少倍。

并行效率：设q个处理机的加速比为Sp（q），则并行算法的效率Ep（q）＝Sp（q）/q。

反映了并行系统中处理器的利用程度。