速度

发布于 2025-01-01 12:38:39 字数 3372 浏览 0 评论 0 收藏 0

速度差异来自许多方面，特别是：

计算复杂性
向量化
扩展到多个核心和节点
局部性

计算复杂性

算法通常使用关于矩阵中的行数和列数的计算复杂度来表示。例如。你可能会发现一个描述为 O(n^2 m) 的算法。

计算复杂性和 O 符号经常出现在技术评论中，所以实践它们是个好主意。你可以在这些网站中了解概念和实践：

向量化

现代 CPU 和 GPU 可以在单个核心上同时对多个元素应用操作。例如，在一个步骤中选取向量中的 4 个浮点数的指数。这称为 SIMD。你不会显式编写 SIMD 代码（它往往需要汇编语言或特殊的 C “内在函数”），而是在像 numpy 这样的库中使用向量化操作，而后者又依赖于专门调整的向量化底层线性代数 API（特别是 BLAS 和 LAPACK）。

矩阵计算包：BLAS 和 LAPACK

BLAS（基本线性代数子程序）：底层矩阵和向量算术运算的规范。这些是用于执行基本向量和矩阵运算的标准积木。 BLAS 起源于 1979 年的 Fortran 库。BLAS 库的示例包括：AMD 核心数学库（ACML），ATLAS，英特尔数学核心库（MKL）和 OpenBLAS。

LAPACK 是用 Fortran 编写的，提供了解决线性方程组，特征值问题和奇异值问题的例程。矩阵因式分解（LU，Cholesky，QR，SVD，Schur）。处理密集和带状矩阵，但不处理一般稀疏矩阵。实数和复数，单精度和双精度。

20 世纪 70 年代和 80 年代：EISPACK（特征值例程）和 LINPACK（线性方程和线性最小二乘例程）库。

LAPACK 最初的目标：使 LINAPCK 和 EISPACK 在共享内存的向量和并行处理器上高效运行，并在现代基于缓存的体系结构上利用缓存（最初于 1992 年发布）。 EISPACK 和 LINPACK 忽略了多层内存架构，并且花费了太多时间来移动数据。

LAPACK 使用高度优化的块操作实现（在每台机器上大量实现），以便尽可能多的计算由 BLAS 执行。

局部性

使用较慢的方式来访问数据（例如，通过互联网）可以比快速方式（例如来自寄存器）慢十亿倍。但慢速存储器远多于快速存储器。因此，一旦我们在快速存储中拥有数据，我们就希望在那里进行所需的任何计算，而不是每次需要时都需要多次加载。此外，对于大多数类型的存储，访问彼此相邻的数据项要快得多，因此我们应该尽量使用附近存储的任何数据，我们知道我们很快就需要它。这两个问题被称为局部性。

不同类型内存的速度

以下是每个人都应该知道的一些数字（来自传奇人物 Jeff Dean ）：

L1 高速缓存引用：0.5 ns
L2 缓存引用：7 ns
主存储器引用 / RAM：100 ns
通过 1 Gbps 网络发送 2K 字节：20,000 ns
从内存顺序读取 1 MB：250,000 ns
在同一数据中心内往返：500,000 ns
磁盘搜索：10,000,000 ns
从网络顺序读取 1 MB：10,000,000 ns
从磁盘顺序读取 1 MB：30,000,000 ns
发送数据包 CA-> Netherlands-> CA：150,000,000 ns

这是一个更新的交互式版本，其中包含这些数字如何变化的时间表。

关键结论：每个连续的存储器类型（至少）比之前的存储器类型差一个数量级。磁盘搜索非常慢。

这个视频有一个很好的例子，展示了几种计算照片模糊的方法，并进行了各种权衡。不要担心出现的 C 代码，只关注矩阵计算的红色和绿色运动图像。

虽然视频是关于一种名为 Halide 的新语言，但它很好地说明了它所引发的问题是普遍存在的。观看 1-13 分钟：

from IPython.display import YouTubeVideo
YouTubeVideo("3uiEyEKji0M")

https://www.youtube.com/embed/3uiEyEKji0M

局部性很难。潜在的权衡：

用于节省内存带宽的冗余计算
牺牲并行性来获得更好的复用

临时性

当计算结果存储在 RAM 中的临时变量中，然后加载该变量来对其进行另一次计算时，就会出现“临时性”问题。这比将数据保存在缓存或寄存器中，并在将最终结果存储到 RAM 之前，进行所有必要的计算要慢很多个数量级。这对我们来说尤其是一个问题，因为 numpy 通常为每一个操作或功能创造临时性。例如。 a = b * c^2 + ln(d) 将创建四个临时值（因为有四个操作和函数）。