分布式chap-3
第三章 并行程序设计
Foster 方法
划分、通信：处理与机器无关的问题，影响并发性和可扩展性
聚合、映射：处理与机器有关的问题，影响局部性和其他性能问题
划分
将要执行的指令和数据按计算部分拆分成多个小任务。关键在于识别出可以并行执行的任务
通信
确定划分的任务之间需要执行哪些通信
聚合
将前面确定的任务与通信结合成更大的任务。例如任务 A 必须在任务 B 之前执行，那么把他们聚合成一个简单符合任务将会比较明智
映射
将聚合好的任务分配到进程/线程中。要使通信量最小化，是各个进程/线程分配的工作量大致均衡
划分
区域划分
- 划分数据尽可能等大
- 生成多个任务，每个都有一些数据和数据操作集
- 一些经验：首先关注最大的数据结构或最常访问的数据结构
功能划分
- 区域划分的补充
- 任务的数据需求可能脱节或者明显重叠
- 功能划分通常通过流水线实现并发任务集合
区域划分最自然，如果首先用功能划分，则并行算法作为整体会更简单
通信
局部通信
- 每个任务仅与少量的相邻任务通信
- 创建说明数据流的通道
全局通信
- 大量相邻任务和远程任务都提供数据来执行计算
- 通常在设计早期，不为他们创建通道
- 可能导致通信过多或限制并发执行的机会
纯本地通信的算法中，有两个问题可能会阻碍并行执行：
- 算法是集中的：他不分布计算和通信，单个任务必须参与每个操作
- 算法是顺序的：不允许多个计算和通信操作同时进行
常用方法：
分布式通信与计算
分而治之
通信方式 1
分布式通信与计算
- 一种求和算法，N 个任务相连，以便对分布在这些任务中的 N 个数字求和
- 单个求和仍需 N-1 步，但只有当多个求和操作要执行是，才允许并发执行
分而治之
- 划分成两个或多个大小大致相同的较简单问题。
- 划分产生的子问题能够并行解决时，分治算法是有效的
- logN 步
通信方式 2
结构化通信
- 一个任务和他邻近的任务形成一个规则结构，比如树或网格
非结构化通信
- 网络可以是任意图
- 使聚合和映射复杂化
- 如果通信需求是动态的，则程序运行时需频繁应用负载平衡算法，并且必须权衡这些算法的成本与收益
通信总结
- 任务间通信是并行算法开销的一部分
- 最小化并行开销是并行算法设计的一个重要目标
聚合
聚合时，考虑合并是否有用，并确定复制数据和/或计算是否值得
目标
- 提高性能
- 保持程序可扩展性
- 简化编程
提高性能
可以降低通信成本，a：消除通信；b：减少通信次数
更少的任务创建成本和任务调度成本
可扩展性
8x128x256，2、3 维聚合，有一 4CPU 的处理器，可以分为 2x128x256 来执行；
8 个 CPU，分 1x128x256；超过 8 个 CPU，可移植性受损害
讨论
关于聚集和复制，这三个目标导向的决策有时会产生冲突。
- 通过增加计算和通信力度以降低通信成本，在可伸缩性和映射的决策方面保持灵活性，并降低软件的工程成本
增加粒度
- 通过发送更少的数据减少通信时间。即使发送相同数量的数据，也可通过使用更少的消息来实现
- 还可以降低任务创建成本
- 方法：表面对体积效应；复制计算；避免通信
表面对体机效应
- 一个任务的通信需求与它所操作的子域的表面成正比，而计算需求与子域的体积成正比。
复制计算
保持灵活性
- 为了具有可移植性和可扩展性，创建不同数量的任务的能力很重要。
- 在为特定计算机调整代码时，这种灵活性也很有用
- 如果任务在等待远程数据时经常阻塞，那么将多个任务映射到一个处理器是有益的
- 重叠计算和通信：一个任务的通信和另一个任务的计算重叠
- 创建比处理器更多的任务为在可用处理器上平衡计算负载的映射策略提供了更大的范围
降低软件工程成本
- 并行化现有的代码时，另一个问题是与不同划分策略相关的相对开发成本
- 从这个角度看，最有趣的策略可能是那些避免大量代码修改的策略
映射
分配任务给处理器的过程。
开发映射算法的目标通常是最小化总执行时间。
冲突目标：
- 最大化处理器利用率，即系统处理器积极解决问题所需任务的平均时间百分比
- 最小化处理器间通信
使通信次数最少，并且每个进程/线程得到大致相同的工作量
最佳映射：
- 寻找最佳映射是一个 NP-Hard
- 必须依赖于启发式
映射决策树
静态任务数
- 结构化通信
- 每个任务的恒定计算时间
- 最小化通信的方式聚合任务
- 每个处理器创建一个任务
- 每个任务的可变计算时间
- 循环映射任务到处理器
- 每个任务的恒定计算时间
- 非结构化通信
- 使用静态负载平衡算法
动态任务树
- 任务间频繁通信
- 使用动态负载平衡算法
- 许多短期任务（没有任务间通信）
- 使用运行时任务调度算法
