并行程序设计(15)

参数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的所有数据的计算。 流水线设计技术

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库并行程序设计(15)在线全文阅读。