每个程序员都应该知道的 40 个算法（四）（1）https://developer.aliyun.com/article/1506366
介绍 CUDA
GPU 最初是为图形处理而设计的。它们被设计来满足处理典型计算机的多媒体数据的优化需求。为此，它们开发了一些特性，使它们与 CPU 有所不同。例如，它们有成千上万的核心，而 CPU 核心数量有限。它们的时钟速度比 CPU 慢得多。GPU 有自己的 DRAM。例如，Nvidia 的 RTX 2080 有 8GB 的 RAM。请注意，GPU 是专门的处理设备，没有通用处理单元的特性，包括中断或寻址设备的手段，例如键盘和鼠标。以下是 GPU 的架构：
GPU 成为主流后不久，数据科学家开始探索 GPU 在高效执行并行操作方面的潜力。由于典型的 GPU 具有数千个 ALU，它有潜力产生数千个并发进程。这使得 GPU 成为优化数据并行计算的架构。因此，能够执行并行计算的算法最适合于 GPU。例如，在视频中进行对象搜索，GPU 的速度至少比 CPU 快 20 倍。图算法在第五章 图算法中讨论过，已知在 GPU 上比在 CPU 上运行得快得多。
为了实现数据科学家充分利用 GPU 进行算法的梦想，Nvidia 在 2007 年创建了一个名为 CUDA 的开源框架，全称为 Compute Unified Device Architecture。CUDA 将 CPU 和 GPU 的工作抽象为主机和设备。主机，即 CPU，负责调用设备，即 GPU。CUDA 架构有各种抽象层，可以表示为以下形式：
请注意，CUDA 在 Nvidia 的 GPU 上运行。它需要在操作系统内核中得到支持。最近，Windows 现在也得到了全面支持。然后，我们有 CUDA Driver API，它充当编程语言 API 和 CUDA 驱动程序之间的桥梁。在顶层，我们支持 C、C+和 Python。
在 CUDA 上设计并行算法
让我们更深入地了解 GPU 如何加速某些处理操作。我们知道，CPU 设计用于顺序执行数据，这导致某些类别的应用程序运行时间显著增加。让我们以处理尺寸为 1,920 x 1,200 的图像为例。可以计算出有 2,204,000 个像素需要处理。顺序处理意味着在传统 CPU 上处理它们需要很长时间。像 Nvidia 的 Tesla 这样的现代 GPU 能够产生惊人数量的 2,204,000 个并行线程来处理像素。对于大多数多媒体应用程序，像素可以独立地进行处理，并且会实现显著加速。如果我们将每个像素映射为一个线程，它们都可以在 O(1)常数时间内进行处理。
但图像处理并不是唯一可以利用数据并行性加速处理的应用。数据并行性可以用于为机器学习库准备数据。事实上，GPU 可以大大减少可并行化算法的执行时间，包括以下内容：
- 为比特币挖矿
- 大规模模拟
- DNA 分析
- 视频和照片分析
GPU 不适用于单程序，多数据（SPMD）。例如，如果我们想要计算一块数据的哈希值，这是一个无法并行运行的单个程序。在这种情况下，GPU 的性能会较慢。
我们想要在 GPU 上运行的代码使用特殊的 CUDA 关键字标记为内核。这些内核用于标记我们打算在 GPU 上并行处理的函数。基于这些内核，GPU 编译器分离出需要在 GPU 和 CPU 上运行的代码。
在 Python 中使用 GPU 进行数据处理
GPU 在多维数据结构的数据处理中非常出色。这些数据结构本质上是可并行化的。让我们看看如何在 Python 中使用 GPU 进行多维数据处理：
- 首先，让我们导入所需的 Python 包：
import numpy as np import cupy as cp import time
- 我们将使用 NumPy 中的多维数组，这是一个传统的使用 CPU 的 Python 包。
- 然后，我们使用 CuPy 数组创建一个多维数组，它使用 GPU。然后，我们将比较时间：
### Running at CPU using Numpy start_time = time.time() myvar_cpu = np.ones((800,800,800)) end_time = time.time() print(end_time - start_time) ### Running at GPU using CuPy start_time = time.time() myvar_gpu = cp.ones((800,800,800)) cp.cuda.Stream.null.synchronize() end_time = time.time() print(end_time - start_time)
如果我们运行这段代码，它将生成以下输出：
请注意，使用 NumPy 创建此数组大约需要 1.13 秒，而使用 CuPy 只需要大约 0.012 秒，这使得在 GPU 中初始化此数组的速度快了 92 倍。
集群计算
集群计算是实现大规模算法并行处理的一种方式。在集群计算中，我们有多个通过高速网络连接的节点。大规模算法被提交为作业。每个作业被分成各种任务，并且每个任务在单独的节点上运行。
Apache Spark 是实现集群计算的最流行方式之一。在 Apache Spark 中，数据被转换为分布式容错数据集，称为Resilient Distributed Datasets（RDDs）。RDDs 是 Apache Spark 的核心抽象。它们是不可变的元素集合，可以并行操作。它们被分割成分区，并分布在节点之间，如下所示：
通过这种并行数据结构，我们可以并行运行算法。
在 Apache Spark 中实现数据处理
让我们看看如何在 Apache Spark 中创建 RDD 并在整个集群上运行分布式处理：
- 为此，首先，我们需要创建一个新的 Spark 会话，如下所示：
from pyspark.sql import SparkSession spark = SparkSession.builder.appName('cloudanum').getOrCreate()
- 一旦我们创建了一个 Spark 会话，我们就可以使用 CSV 文件作为 RDD 的来源。然后，我们将运行以下函数-它将创建一个被抽象为名为
df的 DataFrame 的 RDD。在 Spark 2.0 中添加了将 RDD 抽象为 DataFrame 的功能，这使得处理数据变得更加容易：
df = spark.read.csv('taxi2.csv',inferSchema=True,header=True)
让我们来看看 DataFrame 的列：
- 接下来，我们可以从 DataFrame 创建一个临时表，如下所示：
df.createOrReplaceTempView("main")
- 一旦临时表创建完成，我们就可以运行 SQL 语句来处理数据：
需要注意的重要一点是，尽管它看起来像一个常规的 DataFrame，但它只是一个高级数据结构。在幕后，它是将数据分布到整个集群的 RDD。同样，当我们运行 SQL 函数时，在幕后，它们被转换为并行转换器和减少器，并充分利用集群的能力来处理代码。
混合策略
越来越多的人开始使用云计算来运行大规模算法。这为我们提供了结合向外看和向内看策略的机会。这可以通过在多个虚拟机中配置一个或多个 GPU 来实现，如下面的屏幕截图所示：
充分利用混合架构是一项非常重要的任务。首先将数据分成多个分区。在每个节点上并行化需要较少数据的计算密集型任务在 GPU 上进行。
总结
在本章中，我们研究了并行算法的设计以及大规模算法的设计问题。我们研究了使用并行计算和 GPU 来实现大规模算法。我们还研究了如何使用 Spark 集群来实现大规模算法。
在本章中，我们了解了与大规模算法相关的问题。我们研究了与并行化算法相关的问题以及在此过程中可能产生的潜在瓶颈。
在下一章中，我们将探讨实现算法的一些实际方面。
每个程序员都应该知道的 40 个算法（四）（3）https://developer.aliyun.com/article/1506368
