并行计算机系统课件.ppt

第九章 并行计算机系统的程序设计 第一节 并行计算机系统的数据通信 第二节 Cache与存储器的数据一致性 第三节 多处理机的同步 第四节 并行程序设计模型 第一节 并行计算机系统的数据通信 数据包 寻径信息 序号 数据内容 校验位 协议号 时间戳 MPI Message passing interface 用于多处理器系统和集群系统 进程通过调用库函数进行消息收发通信 支持异构计算 标准的消息传递函数库 点到点通信函数 群集通信函数 不是一种语言 消息传递机制 点对点通信 群集通信 MPI的点对点通信机制 发送操作模型 标准的 同步或缓存的（取决于实现） 缓存的 把发送缓存复制到缓存后返回 同步的 缓存被接收方读取后返回 就绪的 在接收方就绪时启动发送（启动发送后即返回） 发送/接收操作模型 阻塞的 等到消息复制到缓存后返回 非阻塞的 启动发送/接收后即返回 MPI点对点通信函数例子 MPI_INIT 启动MPI计算 MPI_FINALIZE 结束MPI计算 MPI_COMM_SIZE 确定进程数 MPI_COMM_RANK 确定自己的进程号 MPI_SEND 标准地发送一条消息 MPI_BSEND 发送一条缓存的消息 MPI_SSEND 发送一条同步的消息 MPI_RESEND 发送一条就绪的消息 MPI的聚合通信机制 同步方式 同步发送和阻塞接收 所有进程都完成调用时返回（屏障同步） 特异方式 distinguished 一对多通信 散播 广播 多对一通信 归约 求最大值、最小值、总和、乘积等 收集 MPI群集通信函数例子 MPI_Bcast 一对多广播同样的消息 MPI_Gather 多对一收集各个进程的消息 MPI_Allgather 全局收集 MPI_Scatter 一对多散播不同的消息 MPI_Alltoall 每个进程给所有其他进程发送一个消息 每个进程从所有其他进程接收一个消息 MPI_Reduce 多对一归约 MPI_Reduce_scatter 归约并散播 MPI_Barrier 屏障同步 第一节 并行计算机系统的数据通信 1. 存储转发store-and-forward 问题：延迟大，缓存多 第一节 并行计算机系统的数据通信 2. 电路交换circuit switching 问题：冲突多，利用率低 第一节 并行计算机系统的数据通信 3. 虚拟切换virtual cut-through 问题：缓存多 第一节 并行计算机系统的数据通信 4. 虫孔寻径wormhole 问题：死锁和活锁 第一节 并行计算机系统的数据通信 虫孔寻径与存储转发的比较 例9-1 设多处理器计算机中两个结点之间的距离为10，一个处理器发出的消息包含100个片段（flit），假设每个时钟周期可以在连路上传递一个片段，问在存储转发和虫孔寻径两种方式下消息的传递最快分别需要花费多少时间？ 第二节 Cache与存储器的数据一致性 共享存储器多处理机系统的问题 访存冲突与数据一致性 数据多个副本之间的相同性 数据的一致性类型 串行一致性 弱化一致性 处理机一致性 松散一致性 数据一致性 串行一致性sequential consistency 处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。 在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。 对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得1。 数据一致性 弱化一致性weak consistency 程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。 处理机一致性processor consistency 每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。 松散一致性release consistency 采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。 数据一致性的实现 软件方法 编译分析 避免cache共享数据 总线监测 各cache设置监测部件 MESI协议 目录表法 全映射 有限目录 链式目录 SCI 总线监测 所有cache不断监测总线上的每一个地址 总线使得写操作变成串行的 Cache 失效时需要确定数据块的位置 write invalidate protocol invalidates other copies on a write. 多