《算法设计与分析》课件 chp9并行算法

并行算法探索多处理器环境下的高效计算方法从串行到并行为什么需要并行算法？在前面的章节中，我们介绍了分治法、动态规划以及随机算法等多种算法设计思想。这些方法通常默认算法在单处理器环境下顺序执行各个步骤，其整体效率受限于串行计算的速度提升。然而，随着多核处理器和大规模分布式系统的广泛应用，单一处理器的性能已经难以满足海量数据处理和高强度计算的需求。并行算法的核心思想并行算法是一类能在多处理器或多核环境中协同工作的算法，其核心思想在于将一个需要解决的问题分解为若干个可并行执行的子任务，并在多个处理单元上同时运行。这样一来，整体运行时间得以大幅缩短，处理效率显著提高。得益于硬件的发展和算法设计的不断创新，并行算法如今在科学计算、人工智能、大数据处理等领域扮演着越来越重要的角色。设计并行算法的关键问题问题划分如何将问题分解为多个相互独立或弱相关的子任务任务分配如何将子任务均匀地分配给各个处理器以实现负载均衡通信与同步如何在各个处理器之间传递必要的数据，并确保数据一致性，同时尽量降低通信和同步的开销效率与扩展性如何衡量并行算法的加速比、效率以及并行度，并探讨在实际系统中可能遇到的瓶颈问题并行数组求和一个简单且直观的并行算法示例并行数组求和：问题描述假设我们有一个长度为n的数组a，需要计算其中所有元素的总和。传统的串行算法通常从头到尾逐一遍历数组，时间复杂度为Θ(n)。而在并行环境下，假设有K个处理器，由于加法运算满足结合性和分配性，我们可以将问题分解为K个子任务。并行求和的基本策略步骤1：计算部分和每个处理器负责计算一段子数组的部分和：其中i是处理器编号，j是部分和的索引。步骤2：合并结果当这些部分的加法完成后，我们需要将K个部分和组合起来。可以由一个处理器来完成这些部分和的求和：并行数组求和算法性能分析：计算时间

性能分析：通信时间在所有处理器计算完成后，还需要将它们计算得到的部分和传输到主处理器进行汇总。通信总时间

合并时间主处理器在汇总这些部分和时还需进行K-1次加法运算：总执行时间与加速比因此，总的并行执行时间为：

理想情况下的加速比

当n很大时，常数项可以忽略，进一步得到：

考虑通信开销的实际情况

比如，当α=0.1，n=10³，K=8时，S(K)约为7.47，而不考虑通信开销的情况下，加速比约为7.63。在n和K不变的前提下，加速比会随着α的增加而进一步的下降。通信开销的重要性在并行算法的设计与分析中，通信开销常常是影响算法可扩展性和实际运行效率的关键因素，其大小与底层计算机体系结构密切相关。不同的并行体系结构（如共享内存、多处理器集群、分布式系统、异构计算等）会导致数据传输方式、延迟、带宽和同步机制等方面存在差异，从而影响并行算法的整体性能。出于简化分析的目的，我们通常在理论讨论中假设处理器间的通信和同步为"零成本"，即不存在额外延迟或带宽占用。这种理想化假设使得我们能将设计精力集中在最大化并行计算性能提升上，而无需过多考虑数据传输和一致性维护问题。衡量并行算法性能的主要指标加速比

效率E(K)=S(K)/K，它描述了并行系统实际利用处理器资源的程度。若E(K)接近1，表明所有处理器都在充分工作；若E(K)明显小于1，则说明处理器之间存在负载不平衡、等待或闲置等问题。并行度设α表示程序中串行部分所占的比例，1-α表示程序中并行部分所占的比例。Amdahl定律表明，在不考虑通信的情况下，加速比可近似表示为：S(K)=1/(α+(1-α)/K)。可见，若α小，则在理想条件下加速比就能随K的增大而线性增长；若算法中串行部分占比较大，则加速比的提升会很快遇到瓶颈。并行算法设计的核心要点总之，并行算法设计的关键在于如何将问题划分为多个可独立并行计算的子任务，同时尽可能降低通信和同步开销。理想情况下，我们期望各处理器上的计算工作量均衡分布，从而实现接近线性的加速比。尽管在现实系统中通信和同步成本不可忽略，但通过合理的算法设计和硬件调优，依然可以大幅提升大规模计算问题的求解效率。并行算法设计的基本步骤01问题分析与划分理解问题的性质，分析数据依赖关系，确定哪些部分可以并行计算，哪些部分必须串行执行。将问题分解为多个子问题或任务，尽可能减少子任务之间的依赖性，以便在多个处理器上独立执行。02任务划分根据子问题的计算量和数据量，将任务合理划分，并将其分配到各个处理器上，力求使每个处理器的负载大致相等，避免出现某些处理器长时间闲置而其他处理器超负荷的情况。03独立并行计算各子任务各处理器独立地对各自的子任务进行计算。04设计同步与通信机制确定任务之间的通信需求，设计数据传输和交换方案，尽量减少通信量和通信延迟。确定各任务之间的同步点，保证共享数据在并行执行过程中不产生竞争或不一致的状态。并行归并排序分治算法的并行化实现并行归并排序：背景下面以并行归并排序为例，深入探讨并行算法的设计思路。归并排序作为一种分治算法，在串行环境下的时间复杂度为Θ(nlogn)。在并行环境中，我们可以利用多个处理器同时进行局部排序和归并，从而显著提升整体效率。假设我们有一个长度为n的数组a，需要对其进行排序，并且可用K个处理器。并行归并排序的基本思路并行归并排序的基本思路是：先将数组均匀划分为K个子数组，每个子数组由不同的处理器独立排序；然后再将这些有序子数组归并成最终的有序数组。划分子数组将数组a均匀划分为K个子数组，每个子数组的长度为s=n/K并行排序每个处理器在本地对其负责的子数组进行排序并行归并将K个已排序的子数组归并成一个整体有序的数组步骤1：划分子数组

步骤2：并行排序

步骤3：并行归并排序完成后，需要将K个已排序的子数组归并成一个整体有序的数组。可采用多轮次两两归并的方案。在第一轮时，将K个已排序的子数组（每个子数组长度为s）分为K/2组，每组包括两个已排序子数组，由K/2个处理器负责归并，因此，第一轮归并的计算延迟为O(s)。在第二轮时，将K/2个已排序的子数组（每个子数组长度为2s）分为K/4组，因此，第二轮归并的计算延迟为O(2s)。依次类推，共需logK次归并轮次。因此，并行归并的计算延迟为：

并行归并排序的时间复杂度在不考虑通信延迟的前提下，整个并行归并排序的时间复杂度为：

理想情况下的加速比分析假设忽略常数项的开销：也就是说，在理想情况下，加速比与处理器数量K成正比。综上所述，通过将数组划分为独立的子任务并在多个处理器上并行排序与归并，我们能够显著缩短归并排序的执行时间。这一案例直观地展示了并行算法设计的基本步骤：问题划分、任务分配、局部并行计算以及结果合并，从而充分发挥多处理器的计算潜力。并行矩阵乘法高性能计算的核心应用并行矩阵乘法：重要性矩阵乘法在科学计算、机器学习（尤其是神经网络训练）、图像处理等领域中具有极其重要的作用。由于矩阵规模往往十分庞大，单机串行算法需要消耗大量计算时间；而矩阵乘法本身具有高度的并行性，这为大规模并行计算提供了良好的契机。在前面的章节中，我们介绍过矩阵乘法的经典算法之一——Strassen算法，该算法通过分治策略将朴素矩阵乘法的时间复杂度从Θ(n³)降到Θ(n^(log₂7))。本节将介绍如何在理想情况下（忽略通信开销）实现矩阵乘法的并行化，并对其性能进行初步分析。矩阵乘法的定义设有两个矩阵A（大小为n×n）和B（大小为n×n），其乘积矩阵C定义为：可以看出，要计算C中的第(i,j)个元素，只需访问A的第i行和B的第j列，而各个位置的元素计算在逻辑上是彼此独立的。因此，一个朴素的并行矩阵乘法思路是让不同的处理器同时计算C中不同位置的元素。基于按行划分的并行矩阵乘法并行矩阵乘法的性能分析假设有两个n×n的矩阵A和B，以及K个处理器。首先，将矩阵A的n行均匀分配给K个处理器，每个处理器负责处理n/K行。为了完成乘法运算，所有处理器均需访问完整的矩阵B。每个处理器在计算其负责的C的n/K行时，总共需要执行的乘法运算次数为：各处理器计算完毕后，将各自得到的C的行合并，得到最终的矩阵C。在理想模型下，我们忽略这一步骤的通信代价，因此，算法的加速比为：即理想条件下，并行矩阵乘法可实现接近线性的加速。并行矩阵乘法的优化策略值得注意的是，上述案例采用了按行划分的方式，该方法实现简单，但在实际应用中可能会受到数据局部性和通信开销的影响。相比之下，按二维分块的方式可以更好地利用处理器缓存，并降低跨处理器之间的数据传输量，从而在大规模并行系统中往往能够取得更优的性能。总之，在理想条件下并行矩阵乘法能够实现近似线性的加速，而在实际部署时应根据具体硬件架构和应用需求选择最合适的数据划分策略，以充分发挥并行计算的优势。并行搜索提升大规模数据检索效率并行搜索：问题背景搜索问题在计算机科学中极为常见，它要求在给定的数据结构或搜索空间中，找到符合某种条件的目标元素或解。在实际应用中，搜索的规模可能十分庞大（例如海量数据库检索），此时串行搜索可能无法在合理时间内完成。通过并行计算将搜索任务拆分给多个处理器或多台机器来同时进行，能够显著提升搜索速度与整体吞吐量。并行线性搜索以并行线性搜索为例，设有一个长度为n的无序数组A，目标是判断某个元素x是否存在于数组中（或找出满足某一布尔条件的所有元素）。最简单的串行方法是对数组中的每个元素进行线性遍历，直至找到目标元素或遍历结束，其时间复杂度为Θ(n)。在并行环境下（忽略通信开销），我们可以将数组均匀划分给K个处理器，每个处理器在大小为n/K的子数组上进行线性搜索。并行线性搜索算法并行线性搜索的性能分析由于每个处理器需要对n/K个元素进行比较，因此在不考虑通信和同步开销的前提下，并行算法的执行时间可近似表示为：

这表明，在理想情况下，并行线性搜索可实现接近K倍的加速。并行二分查找：朴素方案考虑在数组A已排序的前提下，可以使用二分查找在Θ(logn)的时间内完成搜索。若有K个处理器，可将数组A均匀划分为K个子数组（每个子数组包含n/K个元素）。一种朴素的并行二分查找方案是让所有处理器在各自的子数组上分别执行二分查找，因此，每个子数组上的查找时间为Θ(log(n/K))，整体搜索时间也可达到Θ(log(n/K))。与串行二分查找Θ(logn)相比，这种并行策略在理想情况下能显著提高查找速度。并行二分查找：改进方案然而，我们可以做得更好。回顾传统的二分搜索，每次迭代中都会选取数组的中间元素进行比较，判断该元素是否等于目标值，并据此决定继续搜索左半部分或右半部分。也就是说，通过一次比较，可以将搜索范围从n缩小到n/2。在并行环境下，假设有K个处理器，我们可以将数组A平均划分成K+1个子数组，每个子数组的长度大致为n/(K+1)。接下来，每个处理器负责检查一个分割点，即两个子数组之间的边界元素。并行二分查找的核心思想所有处理器在同一轮次中完成一次比较后，利用各自的比较结果，整个序列就被划分成两部分：一部分必定不包含目标值，而另一部分则可能包含目标值。这样，搜索范围便从n缩小到了约n/(K+1)。在缩小后的子序列上，重复上述过程，直到找到目标值或确定目标不存在。并行二分查找：示例演示例如，设数组A={1,4,6,9,10,11,13,14,15,18,20,23,32,45,51}，目标值为45，且处理器数K=3。第一次迭代数组A被分成四份，每个处理器分别比较以下边界元素与目标值：处理器1比较A[4]=9与45（由于9<45，目标值在右侧）处理器2比较A[8]=14与45（由于14<45，目标值在右侧）处理器3比较A[12]=23与45（由于23<45，目标值在右侧）结合所有处理器的比较结果，可以确定目标值位于最后一部分，即可能出现在子数组{32,45,51}中。第二次迭代对该较小子数组进行同样操作：处理器1比较32与45（目标值在右侧）处理器2比较45与45（发现相等）处理器3比较51与45（目标值在左侧）此时，目标值已成功找到，搜索结束。并行二分查找的时间复杂度可见，这种并行二分搜索算法在每次迭代中能将搜索范围缩小为原来的1/(K+1)，因此在最坏情况下，其时间复杂度为O(logK+1(n))。并行图遍历处理大规模图数据的关键技术并行图遍历：背景图遍历（GraphTraversal）是图算法中最核心且基础的操作之一，其典型方法包括广度优先搜索（BFS）和深度优先搜索（DFS）。在并行或分布式环境下，为了在更短时间内处理大规模图数据，我们通常希望将遍历过程分解到多个处理器或多台机器上并行执行，从而显著提升效率与可扩展性。本节将以广度优先搜索为例，分别介绍其串行与并行版本的实现。广度优先搜索（BFS）的基本思路广度优先搜索的基本思路是：从起始点（源点）出发，首先访问距离源点最近的一层节点，然后依次拓展到更远层级，直至遍历所有可达的节点。BFS通常借助队列这一数据结构来维护访问顺序，确保在处理下一层节点之前，当前层的所有节点均已被访问。BFS遍历过程示例为了更清晰地理解BFS的遍历过程，以一个包含6个顶点及若干无向边的示例图为例，假设起始点为0，详细描述每一步的访问过程：访问节点0，将节点0入队列，队列状态为[0]，访问序列为{0}。节点0出队列，节点0的邻居有节点1、节点2和节点3。由于三个节点都未访问过，访问三个节点，并将它们加入队列。队列状态为[1,2,3]，访问序列为{0,1,2,3}。节点1出队列，节点1的邻居有节点0、节点3和节点4，其中节点1和3已访问过，跳过。访问节点4，并加入队列。队列状态为[2,3,4]，访问序列为{0,1,2,3,4}。BFS遍历过程示例（续）节点2出队列，节点2的邻居有节点0和节点3，他们均已访问过，跳过。队列状态为[3,4]，访问序列为{0,1,2,3,4}。节点3出队列，节点3的邻居有节点0、节点1、节点2和节点4，均已访问。队列状态为[4]，访问序列为{0,1,2,3,4}。节点4出队列，节点4的邻居有节点1、节点3和节点5，其中节点1和节点3已访问，跳过。节点5未访问，访问它并加入队列。队列状态为[5]，访问序列为{0,1,2,3,4,5}。节点5出队列，节点5的邻居有节点4，已访问。此时，队列为空，算法结束，BFS的遍历顺序为{0,1,2,3,4,5}。并行BFS的核心思想从上述BFS遍历过程的描述中可以看出，算法每次从队列中取出一个节点进行处理，等当前层所有节点处理完毕后，再转向下一层。在具备多个处理器的环境下，可以将同一层的所有节点均匀分配给各个处理器，使它们同时进行处理。具体而言，将当前层的所有节点分配给各个处理器，每个处理器负责处理分配到的节点，并对其邻居进行探索和标记。这样，多个处理器能够并行地扩展下一层的节点，从而显著缩短整体遍历所需的时间。并行BFS示例演示以示例图为例，假设有3个处理器，遍历过程如下：起始点为节点0，当前仅有一个节点需要处理，而系统中有3个处理器可用，因此由处理器P0负责。P0访问节点0的邻居{1,2,3}，将这3个节点入队列。此时，队列状态为[1,2,3]，访问序列为{0,1,2,3}。队列中有3个节点，可分别分配给3个处理器。假设P0处理节点1，P1处理节点2，P2处理节点3，三个处理器并行执行。P0发现节点1的邻居0和3都已访问过，而节点4未访问；P1发现节点2的邻居中，节点0和3都已访问过，无新增顶点；P2发现节点3的邻居中，节点0、1和2均已访问，但节点4尚未访问。需要注意的是，P0和P2均检测到节点4未被访问，因此必须通过同步机制确保节点4只被加入队列一次。待所有处理器执行完毕后，队列更新为[4]，访问序列变为{0,1,2,3,4}。并行BFS示例演示（续）队列中仅剩一个节点4，由处理器P0处理。节点4的邻居包括节点1、节点3和节点5，其中节点1和节点3已访问，被跳过；而节点5尚未访问，因此访问节点5并将其加入队列。此时，队列状态为[5]，访问序列更新为{0,1,2,3,4,5}。节点5从队列中出队，因其没有尚未访问的邻居，队列为空，算法终止。上述案例表明，在第一层时能够充分利用三个处理器并行处理多个节点，但在其他层中若仅有单个节点待处理，处理器利用率就会大幅降低。然而，在理想情况下，如果每一层队列中的节点数足够多，并且处理器数量远少于队列中的节点数，则并行BFS可实现接近线性的加速效果。并行全排列生成利用阶乘数系统实现高效并行并行全排列生成：问题背景全排列问题是计算机科学中一个经典的组合问题，其目标是生成给定一组元素的所有可能排列。全排列在密码学、搜索算法、优化问题等诸多领域都有着广泛应用。在前面的章节中，我们讨论了几种全排列生成的算法，本节将探讨如何在并行计算模型下，利用有限数量的处理器高效地生成全排列。给定一个包含n个元素的集合S={1,2,...,n}，其全排列共有n!种。例如，对于S={1,2,3}，其全排列为：{123,132,213,231,312,321}。并行全排列生成的基本策略

更一般地，若处理器数K小于n时，可以采用任务划分策略：将n!个排列均匀分配给K个处理器，每个处理器负责生成其中一部分排列，即每个处理器需要生成