使用开放式mp的慢稀疏矩阵向量积（CSR）
我正在尝试使用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}’，因为它是计算工作分配的剩余部分。 不需要
Edit2（更多细节）：
好的，所以我定时拨打这个5000次并获得平均时间的循环：
- seq：0.0036（秒？）
- 2个主题：0.002613
- 4个主题：0.002308
- 8个主题：0.002384
矩阵的大小为： 303544×303544，并且具有： 2122980非零元素。
使用更小的矩阵30000×30000，我得到更多的时间
- seq 0.000303
- 8个主题0.000078
所以似乎大尺寸可能是我的问题。
欢迎来到记忆受限问题的精彩世界。 为了减轻您的痛苦，我想告诉您，稀疏矩阵向量乘法是在单个多核芯片上无法有效并行化甚至矢量化的众多因素之一，除非所有数据都适合最后一个级缓存或内存总线真的很宽 。
为什么？ 仅仅因为计算与内存访问的比率非常低。 对于内部循环的每次迭代，您将列索引转换为j （8字节），将矩阵元素转换为data （8字节），向量元素的值（8字节）和结果的先前值（自编译器以来）很少优化对共享变量的访问）（8字节）。 然后执行2个非常快速的浮点运算（FLOP）并执行存储（尽管+=运算符被转换为单个指令，它仍然是“fetch-modify-write”）。 总共加载32个字节，然后对它们执行2个FLOP。 这使得每字节1/16 FLOP。
具有现代SSEfunction的CPU内核可以执行4个双精度FLOP /周期，这通常会导致每个CPU内核8 GFLOPS（假设基本频率为2 GHz）。 使用AVX，数量增加了一倍，因此在2 GHz Intel Sandy / Ivy Bridge或AMD等效产品上，每核心最高可达16 GFLOPS。 为了使数据处理能力饱和，给定1/16 FLOP /字节，您需要至少128 GiB / s的内存带宽。
像Xeon X7560这样的高端Nehalem-EX处理器运行速度为2,26 GHz（9,04 GFLOPS /核心），其共享L3缓存（L1和L2缓存为每核）可提供约275 GiB / s。 在9,04 GFLOPS / core时，每个核心需要144,64 GiB / s才能为zAx例程的内循环提供zAx 。 这意味着在理想情况下，此CPU的L3缓存无法提供超过2个完全向量化的乘法内核。
如果没有SSE矢量化，FLOPS速率是双精度的两倍，因此人们可以预期该问题可以扩展到4个线程。 一旦您的问题变得比L3缓存大，事情变得非常糟糕，因为内存总线的带宽减少了大约十倍。
尝试使用以下版本的内部循环，看看编译器是否足够智能，以便遵循OpenMP的宽松内存视图：
#pragma omp for private(ckey,j) schedule(static,chunk) for (i=0; i
不幸的是，你无能为力。 稀疏矩阵向量乘法与CPU插槽的数量成比例，而不是CPU核心的数量。 您需要一个带有独立内存控制器的多插槽系统，例如任何具有多个（后）Nehalem或AMD64处理器的系统。
编辑：优化提示。 你真的需要long来存储列索引和行指针吗？ 使用2122980非零元素，您可以使用int代替。 它将节省内部循环中每个元素加载4个字节，并在外部循环中每行加载另外4个字节。
我不能在评论中写这个，所以我会这样做作为答案。 我认为这是问题，但不是100％肯定。
跨线程的共享变量可能会导致问题。 我不认为这是一个问题，但可能是。 通常只有在写入时，如果没有锁定，那么它只会导致数据损坏。 不确定OpenMP是否在内部进行任何锁定。
由于锁定，您的线程可能会停滞，这是multithreading与单个线程成比例运行速度慢得多的唯一原因。 那或者根本不是你的代码。 最好是在内存中没有潜在瓶颈的小数据集上进行测试（所以你所做的只是处理数据并只计时zAxfunction）。
0.3M ^ 2 = 90B。 这意味着您肯定会遇到分页或加载文件的问题。 （如果你使用的是4倍大小的int）
更好的方法可能是在磁盘的X量上进行操作，同时磁盘并行加载Y量。 通过正确选择X和Y，您的速度不会有太大降低。 如果您正在加载8GB，处理，然后再加载8GB，则必须每次都要等待加载数据。
您可以通过监视处理和文件加载什么也不做的时间来选择X和Y =（8GB-X）来使处理变得智能化。
要检查并查看磁盘访问是否存在问题，请尝试使用较小的数据集并仅使用zAx时间并查看是否有帮助。 如果它确实那么它就是磁盘。 如果没有，那就是代码。