原文：
zh.annas-archive.org/md5/8ddea683d78e7bd756401ec665273969译者：飞龙
第十三章：大规模算法
大规模算法旨在解决庞大的复杂问题。大规模算法的特征是由于其数据规模和处理要求的缘故，需要多个执行引擎。本章首先讨论了什么类型的算法最适合并行运行。然后，讨论了与并行化算法相关的问题。接下来，介绍了计算统一设备架构（CUDA）架构，并讨论了如何使用单个图形处理单元（GPU）或一组 GPU 来加速算法。还讨论了需要对算法进行哪些更改才能有效利用 GPU 的性能。最后，本章讨论了集群计算，并讨论了 Apache Spark 如何创建弹性分布式数据集（RDDs）以创建标准算法的极快并行实现。
在本章结束时，您将能够理解与设计大规模算法相关的基本策略。
本章涵盖了以下主题：
- 大规模算法介绍
- 并行算法的设计
- 利用 GPU 的算法
- 利用集群计算理解算法
- 如何利用 GPU 运行大规模算法
- 如何利用集群的能力运行大规模算法
让我们从介绍开始。
大规模算法介绍
人类喜欢受到挑战。几个世纪以来，各种人类创新使我们能够以不同的方式解决真正复杂的问题。从预测蝗虫袭击的下一个目标区域到计算最大的质数，为我们周围的复杂问题提供答案的方法不断发展。随着计算机的出现，我们发现了一种强大的解决复杂算法的新方法。
定义良好的大规模算法
良好设计的大规模算法具有以下两个特征：
- 它旨在使用现有资源池最佳地处理大量数据和处理需求。
- 它是可扩展的。随着问题变得更加复杂，它可以通过提供更多资源来处理复杂性。
实现大规模算法的一种最实用的方法是使用分而治之的策略，即将较大的问题分解为可以独立解决的较小问题。
术语
让我们来看看一些用于量化大规模算法质量的术语。
延迟
延迟是执行单个计算所需的端到端时间。如果*Compute[1]表示从t[1]开始到t[2]*结束的单个计算，则我们可以说以下内容：
延迟 = t[2]-t[1]
吞吐量
在并行计算的背景下，吞吐量是可以同时执行的单个计算的数量。例如，如果在*t[1]*时，我们可以同时执行四个计算，C[1]，C[2]，C[3]和C[4]，那么吞吐量为四。
网络双分带宽
网络中两个相等部分之间的带宽称为网络双分带宽。对于分布式计算要有效工作，这是最重要的参数。如果我们没有足够的网络双分带宽，分布式计算中多个执行引擎的可用性带来的好处将被慢速通信链路所掩盖。
弹性
基础设施对突然增加的处理需求做出反应并通过提供更多资源来满足需求的能力称为弹性。
三大云计算巨头，谷歌、亚马逊和微软可以提供高度弹性的基础设施。由于它们共享资源池的巨大规模，很少有公司有潜力与这三家公司的基础设施弹性相匹敌。
如果基础设施是弹性的，它可以为问题创建可扩展的解决方案。
并行算法的设计
重要的是要注意，并行算法并不是万能的。即使设计最好的并行架构也可能无法达到我们期望的性能。广泛使用的一个定律来设计并行算法是安达尔定律。
安达尔定律
Gene Amdahl 是 20 世纪 60 年代研究并行处理的第一批人之一。他提出了安达尔定律，这个定律至今仍然适用，并可以成为理解设计并行计算解决方案时涉及的各种权衡的基础。安达尔定律可以解释如下：
它基于这样一个概念，即在任何计算过程中，并非所有过程都可以并行执行。将会有一个无法并行化的顺序部分。
让我们看一个具体的例子。假设我们想要读取存储在计算机上的大量文件，并使用这些文件中的数据训练机器学习模型。
整个过程称为 P。很明显，P 可以分为以下两个子过程：
- P1：扫描目录中的文件，创建与输入文件匹配的文件名列表，并传递它。
- P2：读取文件，创建数据处理管道，处理文件并训练模型。
进行顺序过程分析
运行P的时间由T[seq]**§表示。运行P1和P2的时间由Tseq和Tseq表示。很明显，当在单个节点上运行时，我们可以观察到两件事：
- P2在P1完成之前无法开始运行。这由P1 --> P2表示
- Tseq = Tseq + Tseq
假设 P 在单个节点上运行需要 10 分钟。在这 10 分钟中，P1 需要 2 分钟运行，P2 需要 8 分钟在单个节点上运行。如下图所示：
现在要注意的重要事情是P1的性质是顺序的。我们不能通过并行化来加快它。另一方面，P2可以很容易地分成可以并行运行的并行子任务。因此，我们可以通过并行运行它来加快运行速度。
使用云计算的主要好处是拥有大量资源池，其中许多资源可以并行使用。使用这些资源解决问题的计划称为执行计划。安达尔定律被广泛用于识别给定问题和资源池的瓶颈。
进行并行执行分析
如果我们想要使用多个节点加速P，它只会影响P2，乘以一个大于 1 的因子s>1：
过程 P 的加速可以很容易地计算如下：
进程的可并行部分与其总体的比例由b表示，并计算如下：
例如，在前面的情景中，b = 8/10 = 0.8。
简化这些方程将给我们安达尔定律：
在这里，我们有以下内容：
- P是整个过程。
- b是P的可并行部分的比例。
- s是在P的可并行部分实现的加速。
假设我们计划在三个并行节点上运行过程 P：
- P1是顺序部分，不能通过使用并行节点来减少。它将保持在 2 秒。
- P2现在需要 3 秒而不是 9 秒。
因此，P的总运行时间减少到 5 秒，如下图所示：
在前面的例子中，我们可以计算以下内容：
- n[p] = 处理器的数量 = 3
- b = 并行部分 = 9/11 = 81.81%
- s = 速度提升 = 3
现在，让我们看一个典型的图表，解释阿姆达尔定律：
在前面的图表中，我们绘制了不同b值的s和n[p]之间的图表。
理解任务粒度
当我们并行化算法时，一个更大的任务被分成多个并行任务。确定任务应该被分成的最佳并行任务数量并不总是直截了当的。如果并行任务太少，我们将无法从并行计算中获得太多好处。如果任务太多，那么将会产生太多的开销。这也是一个被称为任务粒度的挑战。
负载平衡
在并行计算中，调度程序负责选择执行任务的资源。在没有实现最佳负载平衡的情况下，资源无法充分利用。
局部性问题
在并行处理中，应该避免数据的移动。在可能的情况下，应该在数据所在的节点上本地处理数据，否则会降低并行化的质量。
在 Python 中启用并发处理
在 Python 中启用并行处理的最简单方法是克隆一个当前进程，这将启动一个名为子进程的新并发进程。
Python 程序员，虽然不是生物学家，但已经创造了他们自己的克隆过程。就像克隆的羊一样，克隆副本是原始过程的精确副本。
制定多资源处理策略
最初，大规模算法是在称为超级计算机的巨大机器上运行的。这些超级计算机共享相同的内存空间。资源都是本地的——物理上放置在同一台机器上。这意味着各种处理器之间的通信非常快，它们能够通过共同的内存空间共享相同的变量。随着系统的发展和运行大规模算法的需求增长，超级计算机演变成了分布式共享内存（DSM），其中每个处理节点都拥有一部分物理内存。最终，发展出了松散耦合的集群，依赖处理节点之间的消息传递。对于大规模算法，我们需要找到多个并行运行的执行引擎来解决复杂的问题：
有三种策略可以拥有多个执行引擎：
- 向内寻找：利用计算机上已有的资源。使用 GPU 的数百个核心来运行大规模算法。
- 向外寻找：使用分布式计算来寻找更多的计算资源，这些资源可以共同用于解决手头的大规模问题。
- 混合策略：使用分布式计算，并在每个节点上使用 GPU 或 GPU 阵列来加速算法的运行。
每个程序员都应该知道的 40 个算法（四）（2）https://developer.aliyun.com/article/1506367
