参数2:处理器模块之间点到点信息传递的路由器 参数3:执行以时间间隔L为周期的路障同步器 特点:
将处理器和路由器分开,强调了计算任务和通信任务的分开,而路由器仅施行点到点的消息传递,不提供组合、复制或广播等功能,这样做既掩盖了具体的互联网络拓扑,又简化了通信协议
采用路障方式的以硬件实现的全局同步是在可控的粗粒度级,从而提供了执行紧耦合同步式并行算法的有效方式,而程序员并无过分的负担
在分析BSP模型的性能时,假定局部操作可在一个时间步内完成,而在每一超级步中,一个处理器至多发送或接受h条消息(h-relation)
LogP模型是一种分布存储的、点到点通信的多处理机模型,其中通信网络由一组参数来描述,但它并不涉及到具体的网络结构,也不假定算法一定要用显式的消息传递操作进行描述。 1.2 并行计算性能评测 并行程序执行时间
等于从并行程序开始执行到所有进程执行完毕,墙上时钟走过的时间,也称为墙上时间 (wall clock time)。对各个进程,墙上时间可进一步分解为计算CPU时间、通信CPU时间、同步开销时间、同步导致的进程空闲时间。 加速比性能定律 Amdahl定律 Gustafson定律 Sun和Ni定律
并行程序性能评价方法
浮点峰值性能与实际浮点性能 数值效率和并行效率 1.3 并行算法设计技术
划分设计技术 ; 分治设计技术 ; 平衡树设计技术 ; 倍增设计技术 ; 流水线设计技术 划分设计:
将原问题划分成p个独立的规模几乎相等的子问题; p台处理器并行地求解各子问题。 Remark:
划分重点在于:子问题易解,组合成原问题的解方便 常见划分方法
均匀划分;方根划分;对数划分;功能划分 并行分治设计步骤
将输入划分成若干个规模相等的子问题; 同时(并行地)递归求解这些子问题;
并行地归并子问题的解,直至得到原问题的解。 平衡树设计技术
以树的叶结点为输入,中间结点为处理结点,由叶向根或由根向叶逐层进行并行处理。 倍增设计技术
又称指针跳跃(pointer jumping)技术,特别适合于处理链表或有向树之类的数据结构;
当递归调用时,所要处理数据之间的距离逐步加倍,经过k步后即可完成距离为2k的所有数据的计算。 流水线设计技术