第4讲-并行算法设计的关键技术.ppt

1 第四讲并行算法设计的关键技术 2 并行算法的一般设计过程 设计并行算法的四个阶段划分 Partitioning 通讯 Communication 组合 Agglomeration 映射 Mapping 划分 分解成小的任务 开拓并发性 通讯 确定诸任务间的数据交换 监测划分的合理性 组合 依据任务的局部性 组合成更大的任务 映射 将每个任务分配到处理器上 提高算法的性能 3 PCAM设计过程 4 任务分解任务分配任务交互 PCAM设计过程 5 任务分解 设计并行算法的一个基本的步骤是描述完成给定任务所需要的计算 并把这些计算分解为可以并行执行的子任务集 一个好的任务分解应该具有下面的特点 它应该有很高的并行度 子任务间的交互 通信和同步 应该尽可能的少 递归分解 数据分解 搜索分解 混合分解 6 任务分解 递归分解 递归分解通常用来对采用Divide and conquer 分治 方法的问题进行任务分解 分 治策略表现出一种自然的并行性 考虑下面的问题 对n个元素的序列A进行快速排序 7 快速排序的过程可以用下面的图来示例 其中的深色的元素为选中的轴元素 8 递归分解问题的串行算法并不一定是递归的 比如下面的问题 n个元素的未排序序列A 求A的最小值 下面的串行算法对A采取逐个扫描的方法 Minimum A n min A 0 for i 1 i n i if A i min min A i returnmin 9 这个算法本身没有表现出任何的并行性 实际上与min的使用有关 一种可行的解决办法是采用分治的策略来重新得到一个算法 然后采用递归分解的方法来开发并行性 改写后的算法如下 递归算法 Minimum A 1 n if n 1 returnA 0 lmin Minimum A 1 n 2 rmin Minimum A n 2 1 n if lmin rmin returnlmin elsereturnrmin 10 上面算法的递归树如下图 对8个元素的序列进行操作 所示 该算法的计算时间主要花费在结果的组合阶段 最开始有n个任务可以并行执行 虽然不需要 然后可以并行执行的任务依次减半 沿着树往上走 到根节点时 只能由一个处理器执行来的到最后的结果 11 任务分解 数据分解 对那些具有大型数据结构的算法来说 数据分解是一种非常有用的方法 对输出数据进行划分对中间数据进行划分对输入数据进行划分 12 对输出数据进行划分 考虑下面的算法框架 这个算法有一个输入集 经过处理后 得到一个输出集 如果输出集中的每个元素都是独立计算的 那么 对输出集的任何划分都会有一个对应的并行任务分解方案 这种分解的最大并行度等于输出集的规模 数据分解是一种很有效的发现并行性的方法 13 例1 x b是n维向量 A是一个n n的矩阵 计算矩阵向量积如下 b Ax显然 b是算法的输出 我们来看b的每个元素是如何得到的 b的每个元素可以用下面的公式的到 由于b的各元素的计算可以独立 并行 进行 我们可以将这个计算按照b的元素进行数据划分 n个处理器 每个处理器完成一个元素的计算 14 例2 A B C都是n n的矩阵的矩阵 完成下面的矩阵乘法 C A B这个算法通常被实现为下面的三重循环 for i 0 i n i for j 0 j n j for c i j 0 0 k 0 k n k c i j a i k b k j 它的计算示意图如下 C的每个元素的计算 15 对中间数据进行划分 在很多的算法中 输出集中的数据之间存在复杂的依赖关系 这种情况下 对输出集按照元素进行划分不再可行 比如下面的计算前序和的算法 PrefixSum A n S for j 0 j i j S j S j i 16 对16个元素序列上的前序和计算过程 PrefixSum A n S for j 0 j i j S j S j i 计算前序和 17 考虑前面讨论过的快速排序算法 快速排序算法一个重要步骤是选定一个序列中的一个元素作为轴元素 pivot 现在考虑如何来完成这个步骤 假设序列是一个n个元素的数组 为了简化讨论 我们假设挑选的轴元素在数组中是唯一的 即它的值与其它的数组元素的值都不同 右边的图给出了一个实例 n 16 5被选为轴元素 左边是算法输入 右边是算法输出 对输入数据进行划分 18 1 比较 2 计算前序和 3 拷贝输出 19 算法包括三个阶段 第一阶段每个处理器将自己的序列中的各元素与轴元素进行比较 得到本地序列中比轴元素小的元素数目和大于等于轴元素的元素数目 第二个阶段对上面的数据计算前序和 注意计算小元素数目和大元素数目的方向不同 第三个阶段中每个处理器根据自己本地的前序和 实际上给出了输出数组的下标 来将本地的元素拷贝到输出数组中 20 任务分解 搜索分解 考虑下面的例子 一个大公司为10位高价值的客户 客户是随机挑选的 不过需要满足高价值客户的基本条件 比如每年购买的产品价值超过100万元 颁发10个奖 现在的问题是如何从客户名单中 所有客户名单 随机挑选出10位满足要求的高价值客户 一种可行的解决办法是对客户名单进行随机排列 象洗牌那样 然后给出名单的头10个高价值客户就行 问题是 怎么对这个任务进行分解才能使它可以并行进行 数据分解or搜索分解 21 一种可能的办法是数据分解把客户名单分成10个相等大小的部分 然后使用上面描述的串行算法来在每个小名单中各选出一个高价值客户 这个算法有没有什么问题 如果某些小名单中根本没有高价值客户怎么办 一个弥补措施是采用对每个小名单 都找出 最多 10个高价值客户 不够十个的 能找出多少算多少 这样至少可以保证算法最后能得到10个高价值客户的名单 22 一个更好的分解方法如下 首先把数据库划分为相等的部分 划分数与我们需要找出的客户数量无关 然后对每个部分的纪录进行随机排列 然后对每个子数据库进行并行扫描 每次找到一个高价值客户 把它记录下来 并用一个全局计数器对目前找到的高价值客户数目进行记录 当全局计数器到10时 所有的搜索过程结束 这个例子中给出的方法被称为搜索分解 23 虽然看起来搜索分解方式与数据分解看起来一样 搜索空间可以被看作被划分的数据 但我们可以找到下面的不同点 数据分解得到的任务分解是独立的 每个任务所进行的任务都是确定的 每个任务所进行的计算都会对最后的结果有所贡献 而对搜索分解来说 所有的子任务 合作 完成工作 只要最后答案找到了 所有没有完成的任务也就终结了 因此 和串行算法相比 并行搜索算法所搜索的空间非常不同 24 任务分解 混合分解 对问题进行任务分解需要灵活的应用上面的方法 递归分解 数据分解和搜索分解虽然有不同 但它们之间却不一定相互排斥 因此 在实际的应用中 为了得到更高的并行度 可以将这些分解方法组合使用 如快速排序可同时采用输入数据分解和递归分解来开发并行性 25 任务分配 任务映射与负载平衡 任务分解算法可以用来识别出问题中可以提供的并行性 并且把计算分解为可以并行执行的子任务 下一步是将这些子任务分配给可用的处理器来执行 给出一个子任务集和一个可用处理器集 有很多种可能的方法在它们之间建立某种映射关系 为了判断哪种映射更好 我们需要使用下面的评价标准 分配给每个处理器的计算任务应该均衡 这样才能减少处理器因为等待其他处理器完成计算任务而造成的空闲 不同处理器之间的交互应该最少 这样处理器可以用更多的时间去完成有效的工作 26 由于这种冲突的存在 使得任务的分配变的更像一种艺术 而不是技术 通常采用的一种策略是在任务分配中 先集中目标使负载尽量均衡 然后再对任务分配进行调整 使得交互尽量少 并行算法设计中使用的负载平衡技术可以分为两类 静态负载平衡与动态负载平衡 静态负载平衡技术在算法的实际执行前将计算任务分配给处理器 动态负载平衡技术在算法的实际执行过程中将计算任务分配给处理器 27 在算法中究竟采用静态负载平衡方法还是动态负载平衡方法可以从下面的两点来考虑 计算中的任务是在算法执行过程中动态生成的 还是在算法设计的时候就已经给出的 比如对矩阵乘法来说 计算任务在算法执行前就可以静态的确定下来并分配给处理器 而快速排序算法中的子任务在程序执行的过程中才能完全的确定 下层的子任务由上层的子任务生成 另外的一个判断依据是任务规模 即解决任务所需要的时间 如果所有任务的规模都是已知的 那么可以用这个知识来有效的指导任务的分配 这时静态的方法就足够了 但有些问题的任务的计算规模是无法事先精确知道的 比如很多的搜索问题就需要采用动态负载平衡的方法 28 动态与静态负载平衡 29 静态分配 一个并行程序中存在的并行性和子任务之间的依赖关系可以完全由这个并行程序的任务图来表示 如果任务图是静态的 并且任务的计算规模可以确定 那么就有可能为这个并行程序找到一种最优的任务分配策略 使得负载不平衡度最低 并且处理器之间的交互最少 当采用数据分解的方法来开发并行性时 恰当的分解本身也可以用来平衡负载并最小化处理器间的交互 下面介绍常用的两类数据结构上的数据分解策略 数组和图 30 数组分布策略 块分布 当数组的每个元素相关的计算是均衡的时候 我们可以采用简单的块分布策略 为每个处理器分配相同数量的数组元素 在这种分布策略下 一个d维的数组按块分布到每个处理器上 每个处理器上的数组在某些特定的维上是连续的块 31 32 同样的 我们也可以选择多个维进行块划分 33 数组分布策略 块转轮分布 当矩阵的每个元素所需的计算量不相同时 块分布有可能会导致负载的不均衡 块轮转分布是块分布的一种变形 它可以用于这种情形 34 对二维数组进行行块轮转分布的例子 对二维数组进行二维块轮转分布的例子 35 图的分割策略 面向数组的分布策略用于那些对稠密矩阵进行运算 交互模式十分规则的数据并行算法非常有效 但很多的算法中的数据结构是稀疏矩阵 而且数据元素之间的交互模式十分不规则 实际的应用中 物理现象的数值模拟有很多都是这类的算法 在这些计算中 物理域通常被离散化 并被表示为元素的网格 计算在每个格点上进行 它们只和网格中相邻的一些格点有关 36 使用图中的网格进行湖水污染扩散的数值模拟 37 通常情况下 每个格点的计算量都相同 所以只要我们给每个处理器分配相同数量的网格点 那么负载很容易平衡 但是 这样的对网格点的简单分布会导致高昂的数据共享开销 因为这样的分布并不会试图将相邻的网格点分配到一起 比如 我们将网格点在处理器上随机分布 如下图表示的一样 不同的颜色表示分配到不同的处理器 这会保证每个处理器分配到相同数量的网格点 同时也意味着它们的任务量相同 即负载平衡 但每个处理器为了完成计算 都需要访问大量的相邻的网格点 而这些格点不一定会是本地的 所以需要大量的处理器间的交互 这会带来非常大的额外开销 38 网格点在处理器上随机分布 39 理想情况下 在分布网格点时 我们应该在平衡负载的同时 尽量减少每个处理器为了完成计算所需要访问的数据量 可以用图划分 如图K 划分算法 图的谱划分算法等 的方法来达到这个目标 我们用图来表示上面的计算 计算被表示为图G V E 其中 图中的每个节点u V对应于算法中的计算 而图中的边e E表示它连接的两个节点间的依赖关系 也就是说一条边 u v 表示为了计算u 需要从节点v得到某些信息 这也就意味着节点u和v代表的任务需要某些交互 由于每个节点只需要与相邻的节点进行交互 因此G是一个稀疏图 这时我们可以采用图划分算法来将G划分为p个部分 划分要求每个部分有相同数量的节点 负载平衡要求 同时 连接每个部分间的边数最少 最后 这p个部分被分别分配给p个处理器 40 利用图分割策略网格点在处理器上的分布 41 动态分配 考虑下面的动态负载平衡问题 任务动态产生 但一旦任务被产生 他们就可以立即被调度 然后运行 而不存在其它的依赖关系 而且 相对于可用的处理器数目来说 当前可以提供的任务数量总是足够的 平均来看 而且 任务之间没有相互 或者很少 的交互 这种情形下的任务的负载平衡的困难性主要是因为下面的两个原因 任务是动态产生的 所以有可能出现有的处理器有太多任务 而有的处理器却 吃不饱 任务的计算规模 所需要的执行时间 未知 这样无法有效的在任务产生的时候将任务分配给合适的处理器 42 自调度 self scheduling 每次处理器需要任务时 它直接从全局队列中得到下一个没有被分配的任务 这种一次分配给处理器一个任务的方式 对平衡计算来说是相当有效的 但全局共享队列本身却很容易成为系统的瓶颈 共享本身就通常意味着不佳的可扩展性 特别是当单个任务需要的计算时间很短的时候 块调度 chunkscheduling 当处理器需要新的任务时 它从全局任务队列中得到一组任务 任务组称为块 chunk 在使用这种调度方法的时候 每次取出的任务组中的任务量不能太大 否则有可能会导致负载不均衡 为了在调度开销和负载平衡间找一个平衡点 可以采取下面的方法 随着程序的执行 初始的块可以很大 当任务队列中所剩的任务数量逐渐减少时 同时也逐渐减少块的大小 根据如何降低块的大小 可以开发出一系列新的调度算法 最常见的方法是线性减少块的大小的方法和非线性减少块的大小的方法 比如块的大小成指数降低 常用的动态调度算法 43 任务交互 并行任务之间的交互是完成并行计算的一个重要组成部分 在并行计算中 很多的情况下都会产生并行任务之间的交互 比如数据和任务的共享 以及任务之间的同步 44 数据共享开销 根据底层的计算机体系结构的不同 数据共享可以有不同的形式 在分布存储的计算机系统上 数据开始时分布在各个处理器上 数据共享是通过在处理器之间发送和接收消息来实现的 而在共享存储器的计算机系统中 数据可以通过对存储器系统的直接读写来进行访问 当多个处理器需要对相同的共享数据进行修改的时候 数据共享的额外开销会变得很大 在这种情况下 为了保证计算的正确性 必须保证在任何时间只能有一个处理器可以修改共享的数据 而且 在修改完成之前 也不能读取这个数据 否则 读取的数据有可能错误 这通常通过互斥协议的方法来实现 45 任务访问共享数据的开销可以分解为两个部分 一是访问的启动开销 根据体系结构的不同 这部分开销对应的实际开销也不