6

我正在尝试使用 open mp 加速稀疏矩阵向量乘积，代码如下：

void zAx(double * z, double * data, long * colind, long * row_ptr, double * x, int M){

long i, j, ckey;
int chunk = 1000;
//int * counts[8]={0};
#pragma omp parallel num_threads(8)
{ 
  #pragma omp for private(ckey,j,i) schedule(static,chunk)
  for (i=0; i<M; i++ ){ 
    z[i]=0;
    for (ckey=row_ptr[i]; ckey<row_ptr[i+1]; ckey++) {
      j = colind[ckey];
      z[i] += data[ckey]*x[j];
    }              
  }
}
}

现在，这段代码运行良好，并产生了正确的结果，但是它只给了我大约 30% 的速度。我检查过线程都获得了相同数量的非零元素（它们是），并且矩阵相当大（300,000 x 300,000），所以我希望开销不是唯一的问题. 我也尝试过使用不同的块大小和线程数运行，我得到了类似的性能。

还有什么我可以尝试从中获得额外速度的东西吗？或者我显然做错了什么？

干杯。

编辑：刚刚注释掉'//int * counts [8] = {0}'，因为它是计算工作分配的剩余部分。没有必要

编辑2（更多细节）：

好的，所以我计时了一个调用这个 5000 次的循环并得到了平均时间：

  • seq：0.0036（秒？）
  • 2 个线程：0.002613
  • 4 线程：0.002308
  • 8 个线程：0.002384

该矩阵的大小为：303544x303544，并具有：2122980个非零元素。

使用更小的矩阵 30000x30000 我得到的时间更像

  • 序列号 0.000303
  • 8 线程 0.000078

所以看起来大尺寸可能是我的问题。

4

2 回答 2

14

欢迎来到内存受限问题的奇妙世界。为了减轻您的痛苦，我想告诉您，稀疏矩阵向量乘法是许多无法在单个多核芯片上有效并行化甚至向量化的事情之一，除非所有数据都可以放在最后一个级别缓存或内存总线真的很宽。

为什么？仅仅是因为计算与内存访问的比率非常低。对于内部循环的每次迭代，您获取一次列索引j（8 个字节）、矩阵元素data（8 个字节）、向量元素的值（8 个字节）和结果的前一个值（因为编译器很少优化访问共享变量）（8 字节）。然后您执行 2 个非常快速的浮点运算 (FLOP) 并执行存储（尽管该+=运算符被转换为一条指令，但它仍然是“获取-修改-写入”指令）。总共加载 32 个字节，并在它们上执行 2 次 FLOP。这使得每个字节 1/16 FLOPs。

支持 SSE 的现代CPU 内核可以执行 4 个双精度 FLOP/周期，这通常会导致每个 CPU 内核 8 GFLOPS（假设基本频率为 2 GHz）。有了 AVX，这个数字就翻了一番，因此在 2 GHz Intel Sandy/Ivy Bridge 或 AMD 同等产品上，每个内核可以获得高达 16 GFLOPS。为了使这种处理能力与数据饱和，给定 1/16 FLOPs/字节，您将需要至少 128 GiB/s 的内存带宽。

像 Xeon X7560 这样的高端 Nehalem-EX 处理器以 2.26 GHz（9.04 GFLOPS/核心）运行，其共享的 L3 缓存（L1 和 L2 缓存是每个核心）提供约 275 GiB/s。在 9,04 GFLOPS/核心时，您需要每个核心 144,64 GiB/s 才能满足zAx例程的内部循环。这意味着在理想情况下，该 CPU 的 L3 高速缓存不能提供超过 2 个完全矢量化乘法内核。

如果没有 SSE 矢量化，双精度的 FLOPS 速率会低两倍，因此可以预期问题会扩展到 4 个线程。一旦你的问题变得比 L3 缓存大，事情就会变得非常糟糕，因为内存总线提供的带宽要少十倍。

尝试以下版本的内部循环，看看编译器是否足够聪明，可以遵循 OpenMP 的宽松内存视图：

#pragma omp for private(ckey,j) schedule(static,chunk)
for (i=0; i<M; i++){
  double zi = 0.0;
  for (ckey=row_ptr[i]; ckey<row_ptr[i+1]; ckey++) {
    j = colind[ckey];
    zi += data[ckey]*x[j];
  }
  z[i] = zi;
}

不幸的是，您无能为力。稀疏矩阵向量乘法与 CPU 插槽数成比例，而不是与 CPU 内核数成比例。您将需要具有独立内存控制器的多插槽系统，例如任何具有多个（后）Nehalem 或 AMD64 处理器的系统。

编辑：优化提示。你真的需要long存储列索引和行指针吗？使用 2122980 个非零元素，你可以很好地使用它int。它将在内部循环中为每个元素节省 4 个字节，在外部循环中为每行节省另外 4 个字节。

于 2012-11-30T12:31:45.887 回答
3

我不能在评论中写这个，所以我会这样做作为答案。我认为这是问题所在，但不是 100% 肯定。

跨线程的共享变量可能会导致问题。我认为这不是问题，但可能是。通常仅在写入时，但如果没有锁，则只会导致数据损坏。不确定 OpenMP 是否在内部进行任何锁定。

您的线程很可能由于锁而停滞，这是多线程运行速度比单线程慢得多的唯一原因。那或者它根本不是你的代码。最好在内存中没有潜在瓶颈的小型数据集上对其进行测试（因此您所做的只是处理数据并仅对zAx 函数计时）。

0.3M^2 = 90B。这意味着您肯定会遇到分页或加载文件的问题。（如果您使用的是 int 的 4 倍大小）

更好的方法可能是在磁盘并行加载 Y 数量时对矩阵的 X 数量进行操作。通过正确选择 X 和 Y，您不会降低速度。如果您正在加载 8GB，正在处理，然后再加载 8GB，您必须等待每次加载数据。

您可以通过监控处理和文件加载什么都不做的时间来选择 X 和 Y = (8GB - X)，从而使处理变得智能。

要检查磁盘访问是否是问题，请尝试使用较小的数据集和时间仅 zAx，看看是否有帮助。如果是，那么它是磁盘。如果没有，那就是代码。

于 2012-11-30T00:08:03.460 回答