198

我正在使用 CUDA、C++、C#、Java 进行一些基准测试,并使用 MATLAB 进行验证和矩阵生成。当我使用 MATLAB 执行矩阵乘法时,2048x2048甚至更大的矩阵几乎立即相乘。

             1024x1024   2048x2048   4096x4096
             ---------   ---------   ---------
CUDA C (ms)      43.11      391.05     3407.99
C++ (ms)       6137.10    64369.29   551390.93
C# (ms)       10509.00   300684.00  2527250.00
Java (ms)      9149.90    92562.28   838357.94
MATLAB (ms)      75.01      423.10     3133.90

只有 CUDA 具有竞争力,但我认为至少 C++ 会有些接近,而不是慢 60 倍。我也不知道如何看待 C# 结果。该算法与 C++ 和 Java 相同,2048但从1024.

MATLAB 执行矩阵乘法的速度如何?

C++ 代码:

float temp = 0;
timer.start();
for(int j = 0; j < rozmer; j++)
{
    for (int k = 0; k < rozmer; k++)
    {
        temp = 0;
        for (int m = 0; m < rozmer; m++)
        {
            temp = temp + matice1[j][m] * matice2[m][k];
        }
        matice3[j][k] = temp;
    }
}
timer.stop();
4

12 回答 12

201

这类问题反复出现,应该比 Stack Overflow 上一次“MATLAB 使用高度优化的库”或“MATLAB 使用 MKL”更清楚地回答。

历史:

矩阵乘法(连同矩阵向量、向量向量乘法和许多矩阵分解)是(是)线性代数中最重要的问题。从早期开始,工程师就一直在用计算机解决这些问题。

我不是历史专家,但显然在那时,每个人都只是用简单的循环重写了他的 FORTRAN 版本。随后出现了一些标准化,并确定了大多数线性代数问题需要解决的“内核”(基本例程)。这些基本操作随后在称为基本线性代数子程序 (BLAS) 的规范中标准化。然后,工程师可以在他们的代码中调用这些标准的、经过良好测试的 BLAS 例程,从而使他们的工作变得更加容易。

布拉斯:

BLAS从level 1(定义标量向量和向量向量运算的第一个版本)到level 2(向量矩阵运算)再到level 3(矩阵矩阵运算),并提供越来越多的“内核”,因此更加标准化以及更多基本的线性代数运算。最初的 FORTRAN 77 实现仍然可以在Netlib 的网站上找到

实现更好的性能:

所以多年来(特别是在 BLAS 1 级和 2 级版本之间:80 年代初),随着向量操作和缓存层次结构的出现,硬件发生了变化。这些演变使得大幅提高 BLAS 子程序的性能成为可能。然后,不同的供应商推出了他们的 BLAS 例程实现,这些例程越来越高效。

我不知道所有的历史实现(那时我还不是出生或孩子),但在 2000 年代初期出现了两个最著名的实现:英特尔 MKL 和 GotoBLAS。您的 Matlab 使用英特尔 MKL,这是一个非常好的优化 BLAS,这解释了您所看到的出色性能。

矩阵乘法的技术细节:

那么为什么Matlab(MKL)在dgemm(双精度通用矩阵-矩阵乘法)上如此之快?简单来说:因为它使用矢量化和良好的数据缓存。用更复杂的术语:请参阅Jonathan Moore 提供的文章。

基本上,当您在提供的 C++ 代码中执行乘法运算时,您根本不适合缓存。由于我怀疑您创建了一个指向行数组的指针数组,因此您在内部循环中对“matice2”的第 k 列的访问:matice2[m][k]非常慢。实际上,当您访问 时matice2[0][k],您必须获取矩阵数组 0 的第 k 个元素。然后在下一次迭代中,您必须访问matice2[1][k],它是另一个数组(数组 1)的第 k 个元素。然后在下一次迭代中,您访问另一个数组,依此类推...由于整个矩阵matice2无法放入最高缓存(它的8*1024*1024字节很大),因此程序必须从主内存中获取所需的元素,从而丢失很多时间。

如果您只是转置矩阵,以便访问将在连续的内存地址中进行,那么您的代码已经运行得更快,因为现在编译器可以同时在缓存中加载整行。试试这个修改后的版本:

timer.start();
float temp = 0;
//transpose matice2
for (int p = 0; p < rozmer; p++)
{
    for (int q = 0; q < rozmer; q++)
    {
        tempmat[p][q] = matice2[q][p];
    }
}
for(int j = 0; j < rozmer; j++)
{
    for (int k = 0; k < rozmer; k++)
    {
        temp = 0;
        for (int m = 0; m < rozmer; m++)
        {
            temp = temp + matice1[j][m] * tempmat[k][m];
        }
        matice3[j][k] = temp;
    }
}
timer.stop();

因此,您可以看到缓存局部性如何显着提高了代码的性能。现在,真正的dgemm实现将其利用到了非常广泛的水平:它们对由 TLB 大小定义的矩阵块执行乘法运算(翻译后备缓冲区,长话短说:可以有效缓存的内容),以便它们流式传输到处理器它可以处理的数据量。另一方面是向量化,它们使用处理器的向量化指令来获得最佳指令吞吐量,这是跨平台 C++ 代码无法做到的。

最后,有人声称这是因为 Strassen 或 Coppersmith-Winograd 算法是错误的,由于上述硬件考虑,这两种算法在实践中都无法实现。

于 2015-07-05T15:03:31.843 回答
92

这是我在装有 Tesla C2070 的机器上使用 MATLAB R2011a + Parallel Computing Toolbox的结果:

>> A = rand(1024); gA = gpuArray(A);
% warm up by executing the operations a couple of times, and then:
>> tic, C = A * A; toc
Elapsed time is 0.075396 seconds.
>> tic, gC = gA * gA; toc
Elapsed time is 0.008621 seconds.

MATLAB 使用高度优化的库进行矩阵乘法,这就是普通 MATLAB 矩阵乘法如此快速的原因。该gpuArray版本使用MAGMA

在装有 Tesla K20c 的机器上使用 R2014a 进行更新timeit,新功能和gputimeit功能:

>> A = rand(1024); gA = gpuArray(A);
>> timeit(@()A*A)
ans =
    0.0324
>> gputimeit(@()gA*gA)
ans =
    0.0022

在具有 16 个物理内核和 Tesla V100 的 WIN64 机器上使用 R2018b 进行更新:

>> timeit(@()A*A)
ans =
    0.0229
>> gputimeit(@()gA*gA)
ans =
   4.8019e-04

(注意:在某些时候(我忘了确切的时间)gpuArray从 MAGMA 切换到 cuBLAS - MAGMA 仍然用于某些gpuArray操作)

于 2011-05-19T12:46:25.770 回答
42

这就是为什么。MATLAB 不会像在 C++ 代码中那样循环遍历每个元素来执行简单的矩阵乘法。

当然,我假设您只是使用C=A*B而不是自己编写乘法函数。

于 2011-05-19T20:58:27.457 回答
20

Matlab 前段时间合并了 LAPACK,所以我假设他们的矩阵乘法至少使用了那么快的东西。LAPACK 源代码和文档很容易获得。

您还可以查看 Goto 和 Van De Geijn 的论文“Anatomy of High-Performance Matrix Multiplication”,网址为http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.1785&rep=rep1&type=pdf

于 2011-05-19T15:50:19.597 回答
13

答案是LAPACKBLAS库使 MATLAB 在矩阵运算方面的速度非常快,而不是 MATLAB 人员的任何专有代码。

在您的 C++ 代码中使用LAPACK和/或BLAS库进行矩阵运算,您应该获得与 MATLAB 相似的性能。这些库应该可以在任何现代系统上免费使用,并且在学术界已经开发了数十年。请注意,有多种实现方式,包括一些封闭源代码,例如Intel MKL

有关 BLAS 如何获得高性能的讨论可在此处获得。


顺便说一句,在我的经验中,直接从 c 调用 LAPACK 库是一种严重的痛苦(但值得)。您需要非常准确地阅读文档。

于 2015-11-07T08:47:52.827 回答
9

When doing matrix multiplying, you use naive multiplication method which takes time of O(n^3).

There exist matrix multiplication algorithm which takes O(n^2.4). Which means that at n=2000 your algorithm requires ~100 times as much computation as the best algorithm.
You should really check the wikipedia page for matrix multiplication for further information on the efficient ways to implement it.

于 2012-11-04T16:30:01.567 回答
7

根据您的 Matlab 版本,我相信它可能已经在使用您的 GPU。

另一件事; Matlab 跟踪矩阵的许多属性;无论是对角线、赫尔墨斯等,并以此为基础专门化其算法。也许它的专业化是基于你传递给它的零矩阵,或者类似的东西?也许它正在缓存重复的函数调用,这会打乱你的时间?也许它优化了重复未使用的矩阵产品?

为防止此类事情发生,请使用随机数矩阵,并确保通过将结果打印到屏幕或磁盘等来强制执行。

于 2011-05-19T11:55:16.910 回答
4

“为什么 matlab 在做 xxx 方面比其他程序更快”的一般答案是 matlab 有很多内置的优化函数。

使用的其他程序通常没有这些功能,因此人们应用他们自己的创造性解决方案,这比专业优化的代码慢得多。

这可以用两种方式解释:

1)常见/理论方法:Matlab 并没有明显更快,你只是做错了基准测试

2)现实的方式:对于这些东西,Matlab 在实践中更快,因为像 c++ 这样的语言太容易以无效的方式使用。

于 2012-09-20T15:55:30.307 回答
3

MATLAB 使用来自英特尔的高度优化的 LAPACK 实现,称为英特尔数学内核库(英特尔 MKL) - 特别是dgemm 函数。速度 这个库利用了处理器特性,包括 SIMD 指令和多核处理器。他们没有记录他们使用的具体算法。如果您要从 C++ 调用英特尔 MKL,您应该会看到类似的性能。

我不确定 MATLAB 使用什么库来进行 GPU 乘法,但可能类似于nVidia CUBLAS

于 2015-09-10T05:53:56.407 回答
2

形成鲜明对比的原因不仅在于 Matlab 的惊人优化(正如许多其他答案已经讨论过的那样),还在于您将矩阵表示为对象的方式。

好像您将矩阵设为列表列表?列表列表包含指向列表的指针,列表中包含您的矩阵元素。包含列表的位置是任意分配的。当您遍历第一个索引(行号?)时,内存访问的时间非常重要。相比之下,您为什么不尝试使用以下方法将矩阵实现为单个列表/向量?

#include <vector>

struct matrix {
    matrix(int x, int y) : n_row(x), n_col(y), M(x * y) {}
    int n_row;
    int n_col;
    std::vector<double> M;
    double &operator()(int i, int j);
};

double &matrix::operator()(int i, int j) {
    return M[n_col * i + j];
}

应使用相同的乘法算法,以使翻牌数相同。(对于大小为 n 的方阵,n^3)

我要求您计时,以便结果与您之前的结果(在同一台机器上)相当。通过比较,您将准确显示内存访问时间的重要性!

于 2014-03-11T04:11:40.557 回答
2

因为MATLAB最初是为数值线性代数(矩阵运算)开发的编程语言,它具有专门为矩阵乘法开发的库。现在MATLAB 还可以为此额外使用GPU(图形处理单元)

如果我们查看您的计算结果:

             1024x1024   2048x2048   4096x4096
             ---------   ---------   ---------
CUDA C (ms)      43.11      391.05     3407.99
C++ (ms)       6137.10    64369.29   551390.93
C# (ms)       10509.00   300684.00  2527250.00
Java (ms)      9149.90    92562.28   838357.94
MATLAB (ms)      75.01      423.10     3133.90

那么我们可以看到,不仅 MATLAB 在矩阵乘法方面如此之快:CUDA C(来自 NVIDIA 的编程语言)比 MATLAB 有一些更好的结果。CUDA C 也有专门为矩阵乘法开发的库,它使用 GPU。

MATLAB 简史

新墨西哥大学计算机科学系主任 Cleve Moler 在 1970 年代后期开始开发 MATLAB。他设计它是为了让他的学生可以访问LINPACK(一个用于执行数值线性代数的软件库)和EISPACK(是一个用于线性代数数值计算的软件库)而无需学习 Fortran。它很快传播到其他大学,并在应用数学界找到了强大的受众。工程师杰克·利特尔 (Jack Little) 在 1983 年莫勒访问斯坦福大学时接触到了它。认识到它的商业潜力,他与莫勒和史蒂夫·班格特一起加入。他们用 C 语言重写了 MATLAB,并于 1984 年创立了 MathWorks 以继续其发展。这些重写的库被称为 JACKPAC。2000 年,MATLAB 被改写为使用一组更新的矩阵操作库 LAPACK(一个用于数值线性代数的标准软件库)。

资源

什么是 CUDA C

CUDA C 还使用专门为矩阵乘法开发的库,如OpenGL(开放图形库)。它还使用 GPU 和 Direct3D(在 MS Windows 上)。

CUDA 平台旨在与 C、C++ 和 Fortran 等编程语言一起使用。这种可访问性使并行编程专家更容易使用 GPU 资源,而之前的 API(如Direct3DOpenGL)需要高级图形编程技能。此外,CUDA 还支持OpenACCOpenCL等编程框架。

在此处输入图像描述

CUDA 处理流程示例:

  1. 将数据从主存复制到 GPU 内存
  2. CPU 启动 GPU 计算内核
  3. GPU 的 CUDA 内核并行执行内核
  4. 将生成的数据从 GPU 内存复制到主内存

比较 CPU 和 GPU 执行速度

我们运行了一个基准测试,其中我们测量了在英特尔至强处理器 X5650 上,然后使用 NVIDIA Tesla C2050 GPU 上执行 50 个时间步长,网格大小为 64、128、512、1024 和 2048 所需的时间。

在此处输入图像描述

对于 2048 的网格大小,该算法显示计算时间减少了 7.5 倍,从 CPU 上的超过一分钟到 GPU 上的不到 10 秒。对数比例图显示,对于小网格大小,CPU 实际上更快。然而,随着技术的发展和成熟,GPU 解决方案越来越能够处理更小的问题,我们预计这一趋势将继续下去。

资源

来自 CUDA C 编程指南的介绍:

受市场对实时、高清 3D 图形永不满足的需求的推动,可编程图形处理器单元或 GPU 已发展成为一种高度并行、多线程、多核处理器,具有巨大的计算能力和非常高的内存带宽,如Figure 1和所示Figure 2

图 1. CPU 和 GPU 的每秒浮点运算次数

在此处输入图像描述

图 2。CPU 和 GPU 的内存带宽

在此处输入图像描述

CPU 和 GPU 浮点能力差异背后的原因是 GPU 专门用于计算密集型、高度并行的计算——这正是图形渲染的意义所在——因此设计成更多的晶体管专门用于数据处理而不是数据缓存和流量控制,如图所示Figure 3

图 3。GPU 将更多晶体管用于数据处理

在此处输入图像描述

更具体地说,GPU 特别适合解决可以表示为数据并行计算的问题 - 相同的程序在许多数据元素上并行执行 - 具有高算术强度 - 算术运算与内存运算的比率。由于对每个数据元素执行相同的程序,因此对复杂的流控制要求较低,并且由于它在许多数据元素上执行并且具有较高的算术强度,因此可以通过计算而不是大数据缓存来隐藏内存访问延迟.

数据并行处理将数据元素映射到并行处理线程。许多处理大型数据集的应用程序可以使用数据并行编程模型来加快计算速度。在 3D 渲染中,大量像素和顶点被映射到并行线程。类似地,图像和媒体处理应用程序(例如渲染图像的后处理、视频编码和解码、图像缩放、立体视觉和模式识别)可以将图像块和像素映射到并行处理线程。事实上,图像渲染和处理领域之外的许多算法都通过数据并行处理来加速,从一般的信号处理或物理模拟到计算金融或计算生物学。

资源

进阶阅读


一些有趣的事实

我已经编写了与 Matlab 一样快的 C++ 矩阵乘法,但它需要一些小心。(在 Matlab 为此使用 GPU 之前)。

来自这个答案的引用。

于 2019-01-17T06:51:40.820 回答
2

在 C++ 中它很慢,因为您没有使用多线程。本质上,如果 A = BC,它们都是矩阵,则 A 的第一行可以独立于第二行计算,依此类推。如果 A、B 和 C 都是 n × n 矩阵,则可以加快乘法速度n^2 的因子,如

a_{i,j} = sum_{k} b_{i,k} c_{k,j}

如果你使用,比如说,Eigen [ http://eigen.tuxfamily.org/dox/GettingStarted.html ],多线程是内置的,线程数是可调的。

于 2015-10-17T23:53:18.277 回答