评注


借用已有算法求解新问题

方法描述

找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。 这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径 是一个很好的范例。

评注


PCAM设计过程
问题 划分
通信
组合
映射





划分：是对任务并行的求解，把任务大任务都 打散，打稀碎，分解成小任务。 通信：原来是一个整体，不需要通信，分解后 各个部分之间存在交流了，即通信。 通信属于额外成本，越少越好。 组合：任务组合形成更大的任务，目的是减少 通信。 映射：并行程序的实现过程。 图中：三个处理器，有六个任务，怎样安排来 执行的问题。
任务的合并使得算法更有效 将任务分配到处理器，并保持负载平衡

通讯


组合


映射



权重轮询调度算法(Weighted Round-Robin Scheduling) 上面所讲的轮询调度算法并没有考虑每台 服务器的处理能力，在实际情况中，可能并不 是这种情况。由于每台服务器的配置、安装的 业务应用等不同，其处理能力会不一样。所以， 我们根据服务器的不同处理能力，给每个服务 器分配不同的权值，使其能够接受相应权值数 的服务请求。


由于权重轮询调度算法考虑到了不同服务器的 处理能力，所以这种均衡算法能确保高性能的 服务器得到更多的使用率，避免低性能的服务 器负载过重。所以，在实际应用中比较常见。 总结 轮询调度算法以及权重轮询调度算法的特 点是实现起来比较简洁，并且实用。目前几乎 所有的负载均衡设备均提供这种功能。

PCAM设计方法学
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 小结

映射(实现的考虑，系统来做)
方法描述 负载平衡算法 任务调度算法 映射判据

方法描述
每个任务要映射到具体的处理器，定位 到运行机器上； 任务数大于处理器数时，存在负载平衡 和任务调度问题； 映射的目标：减少算法的执行时间
并行计算 Parallel Computing
并行算法设计（ PCAM ）
主讲人：张琪
并行算法的一般设计方法
串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题

从问题描述开始设计并行算法

方法描述

从问题本身描述出发，不考虑相应的串行算 法，设计一个全新的并行算法。 挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性 的工作；
最短的期望的延迟（Shortest Expected Delay Scheduling SED）

举例来说 ABC三台机器分别权重123 ，连接数也分别是 123。那么如果使用WLC算法的话一个新请求 进入时它可能会分给ABC中的任意一个。使用 sed算法后会进行这样一个运算 A:(1+1)/1 B:(1+2)/2 C:(1+3)/3 根据运算结果，把连接交给C 。
任务调度算法


任务放在集中的或分散的任务池中，使用任务调度 算法将池中的任务分配给特定的处理器。下面是两 种常用调度模式： 经理/雇员模式
w w w w 员工 w p p p ppp 经理 w

非集中模式
w
Min-Min算法

ห้องสมุดไป่ตู้

Min-Min算法是一种实现起来很简单的算法， 算法的执行时间也很快。算法的思想是首先映 射小的任务，并且映射到执行快的机器上。 执行过程为：计算要参与映射事件的每个任务 在各个机器上的期望完成时间，找到每个任务 的最早完成时间及其对应的机器；从中找出具 有最小最早完成时间的任务，将该任务指派给 获得它的机器；指派完成后，更新机器期望就 绪时间并将已完成映射的任务从任务集合中删 除。重复上面的过程，直到所有的任务都被映 射完。
映射判据
采用集中式负载平衡方案，是否存 在通讯瓶颈？ 采用动态负载平衡方案，调度策略 的成本如何？

PCAM设计方法学
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 小结

小结

划分

域分解和功能分解 任务间的数据交换

前两个步骤是在算法层次上的，本部分和 并行机、体系结构有关。 增加粒度： 在划分阶段,致力于尽可能多的任务以增大 并行执行的机会.但定义大量的细粒度任务 不一定产生一个有效的算法,因为这有可能 增加通信的代价和任务创建的代价

表面-容积效应


通讯量与任务子集的表面成正比，计算量 与任务子集的体积成正比； 通信量与其附近的任务数有关，计数量 与任务本身大小有关。

增加重复计算有可能减少通讯量；


二维网格计算 周围有四个，所以计算量是1，通信量是4. 看四个小点 周围有八个，计算量是4，通信量是8.
重复计算

重复计算也叫冗余计算，有时可用冗余计
算来减少通信。
减少通讯量，但增加了计算量，应保持 恰当的平衡； 重复计算的目标应减少算法的总运算时 间； 同时也要保持灵活性和减少软件成本, 降低软件工程代价
0 Σ
3
0 Σ
3
0 Σ
3
0 Σ
3
4 Σ
7
4 Σ
7
4 Σ
7
4 Σ
7
0 Σ
1
0 Σ
1
2 Σ
3
2 Σ
3
4 Σ
5
4 Σ
5
6 Σ
7
6 Σ
7
0
1
2
3
4
5
6
7
蝶式结构求和，使用了重复计算，共需logN步
组合判据
增加粒度是否减少了通讯成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比 例? 是否保持了类似的计算和通讯？ 有没有减少并行执行的机会？
PCAM设计方法学

设计并行算法的四个阶段


划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping)



划分：分解成小的任务，开拓并发性； 通讯：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。

并发的任务 不同的处理器 任务之间存在高通讯的 同一处理器


映射实际是一种权衡，属于NP完全问题


NP就是Non-deterministic Polynomial的问题， 也即是多项式复杂程度的非确定性问题。 NP完全问题是不确定性图灵机在P时间内能解 决的问题，是世界七大数学难题之一。NP完 全问题是NP类中“最难”的问题，也就是说 它们是最可能不属于P类的。这是因为任何NP 中的问题可以在多项式时间内变换成为任何特 定NP完全问题的一个特例。属于计算机科学 理论的一个基本概念。

该算法形式化描述如下： M为所有未调度的任务的集合 （1）判断任务集合M是否为空，不为空，执 行（2）；否则跳到步骤（7）。 （2）对于任务集中的所有任务，求出它们映 射到所有可用机器上的最早完成时间cij。 （3）根据（2）的结果，找出最早完成时间最 小的那个任务mi和所对应的机器hj。 （4）将任务mi映射到机器hj上；并将该任务 从任务集合中删除。 （5）更新机器hj的期望就绪时间rj。 （6）更新其它任务在机器hj上的最早完成时 间；回到（1）。 （7）此次映射事件结束，退出程序。

重复计算

示例：二叉树上N个处理器求N个数 的全和，要求每个处理器均保持全 和。
s s b b
0
b b
1
s
0
s
1
s
2
s
3
b
2
b
3
二叉树上求和，共需2logN步
重复计算

示例：二叉树上N个处理器求N个数的全和， 要求每个处理器均保持全和。
0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7
PCAM设计方法学
划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping) 小结

组合
方法描述 表面-容积效应 重复计算 组合判据

方法描述
组合是由抽象到具体的过程，是将组合 的任务能在一类并行机上有效的执行； 合并小尺寸任务，减少任务数。如果任 务数恰好等于处理器数，则也完成了映 射过程； 如果任务数大于处理器数，需要进行映 射； 通过增加任务的粒度和重复计算，可以 减少通讯成本； 保持映射和扩展的灵活性，降低软件工 程成本；（例如：开发和维护成本）
负载平衡算法
静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的：

递归对剖 局部算法 概率方法 循环映射

静态调度——轮询算法


随着各站点访问量和信息交流量的迅猛增长， 如何使用最小的资源成本，提高网络的效率， 最优化用户体验，已经成为网络管理人员不得 不面对的挑战。 技术上讲，就是ICP--网际网路内容提供者 (internet content provider)行业面临的网络资 源有效利用问题，也就是如何进行对网络的访 问分流，以便能够快速响应用户反应，即：负 载均衡。