增加重复计算有可能减少通讯量；
二维网格计算 周围有四个，所以计算量是1，通信量是4. 看四个小点 周围有八个，计算量是4，通信量是8.
重复计算
重复计算也叫冗余计算，有时可用冗余计
算来减少通信。
减少通讯量，但增加了计算量，应保持 恰当的平衡；
重复计算的目标应减少算法的总运算时 间；
图中：三个处理器，有六个任务，怎样安排来 执行的问题。
PCAM设计方法学
设计并行算法的四个阶段
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping)
划分：分解成小的任务，开拓并发性； 通讯：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。
方法描述
每个任务要映射到具体的处理器，定位 到运行机器上；
任务数大于处理器数时，存在负载平衡 和任务调度问题；
映射的目标：减少算法的执行时间
并发的任务 不同的处理器 任务之间存在高通讯的 同一处理器
映射实际是一种权衡，属于NP完全问题
NP就是Non-deterministic Polynomial的问题， 也即是多项式复杂程度的非确定性问题。
同时也要保持灵活性和减少软件成本, 降低软件工程代价
重复计算
示例：二叉树上N个处理器求N个数 的全和，要求每个处理器均保持全 和。
s
s
b
b
s
s
s
s
b
b
b
b
0
1
2
3
0
1
2
3
二叉树上求和，共需2logN步
重复计算
示例：二叉树上N个处理器求N个数的全和， 要求每个处理器均保持全和。
Σ70
Σ70
递归对剖 局部算法 概率方法 循环映射
静态调度——轮询算法
随着各站点访问量和信息交流量的迅猛增长， 如何使用最小的资源成本，提高网络的效率， 最优化用户体验，已经成为网络管理人员不得 不面对的挑战。
技术上讲，就是ICP--网际网路内容提供者 (internet content provider)行业面临的网络资 源有效利用问题，也就是如何进行对网络的访 问分流，以便能够快速响应用户反应，即：负 载均衡。
轮询调度算法(Round-Robin Scheduling)
轮询调度算法的原理是每一次把来自用户 的请求轮流分配给内部中的服务器，从1开始， 直到N(内部服务器个数)，然后重新开始循环。
增加粒度：
在划分阶段,致力于尽可能多的任务以增大 并行执行的机会.但定义大量的细粒度任务 不一定产生一个有效的算法,因为这有可能 增加通信的代价和任务创建的代价
表面-容积效应
通讯量与任务子集的表面成正比，计算量 与任务子集的体积成正比；
通信量与其附近的任务数有关，计数量 与任务本身大小有关。
评注
挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性
的工作；
借用已有算法求解新问题
方法描述
找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。
评注
这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径
是一个很好的范例。
并行计算 Parallel Computing
并行算法设计（ PCAM ）
主讲人：张琪
并行算法的一般设计方法
串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题
从问题描述开始设计并行算法
方法描述
从问题本身描述出发，不考虑相应的串行算 法，设计一个全新的并行算法。
PCAM设计方法学
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 小结
组合
方法描述 表面-容积效应 重复计算 组合判据
方法描述
组合是由抽象到具体的过程，是将组合 的任务能在一类并行机上有效的执行；
例? 是否保持了类似的计算和通讯？ 有没有减少并行执行的机会？
PCAM设计方法学
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 小结
映射(实现的考虑，系统来做)
方法描述 负载平衡算法 任务调度算法 映射判据
NP完全问题是不确定性图灵机在P时间内能解 决的问题，是世界七大数学难题之一。NP完 全问题是NP类中“最难”的问题，也就是说 它们是最可能不属于P类的。这是因为任何NP 中的问题可以在多项式时间内变换成为任何特 定NP完全问题的一个特例。属于计算机科学 理论的一个基本概念。
负载平衡算法
静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的：
合并小尺寸Βιβλιοθήκη 务，减少任务数。如果任 务数恰好等于处理器数，则也完成了映 射过程；
如果任务数大于处理器数，需要进行映 射；
通过增加任务的粒度和重复计算，可以 减少通讯成本；
保持映射和扩展的灵活性，降低软件工 程成本；（例如：开发和维护成本）
前两个步骤是在算法层次上的，本部分和 并行机、体系结构有关。
PCAM设计过程
问题
划分
通信 组合
映射
划分：是对任务并行的求解，把任务大任务都 打散，打稀碎，分解成小任务。
通信：原来是一个整体，不需要通信，分解后 各个部分之间存在交流了，即通信。
通信属于额外成本，越少越好。
组合：任务组合形成更大的任务，目的是减少 通信。
映射：并行程序的实现过程。
Σ70
Σ70
Σ70
Σ70
Σ70
Σ70
Σ30
Σ30
Σ30
Σ30
Σ74
Σ74
Σ74
Σ74
Σ10
Σ10
Σ32
Σ32
Σ54
Σ54
Σ76
Σ76
0
1
2
3
4
5
6
7
蝶式结构求和，使用了重复计算，共需logN步
组合判据
增加粒度是否减少了通讯成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比