写入输出数组独立元素是否存在伪共享？CSR矩阵求和代码伪共享咨询

1. 写入输出数组的独立元素时是否存在伪共享？ #

会存在伪共享。

伪共享的核心原因是CPU缓存以缓存行（通常为64字节，x86架构）为最小读写单位。当不同线程写入的数组元素落在同一个缓存行内时，即使这些元素是独立的，CPU缓存一致性协议（如MESI）会要求缓存行在不同核心间同步，导致频繁的缓存失效、刷新操作，从而产生性能损耗，这就是伪共享。

比如float类型占4字节，一个64字节缓存行可容纳16个float元素。若线程0写入sum[0]、线程1写入sum[1]，二者处于同一缓存行，就会触发伪共享。

2. CSR矩阵行求和代码中sum[]的伪共享问题及解决方法 #

是否存在伪共享？ #

存在伪共享。

这段代码中，每个线程负责一个行索引i，最终写入sum[i]。当线程数较多、N较大时，不同线程写入的sum[i]很大概率落在同一缓存行内，触发伪共享，导致缓存同步开销。

另外注意：原代码存在语法错误，外层for循环缺少包裹代码块的大括号，修正后的代码如下：

#pragma omp parallel for  
for (int i = 0; i < N; i++) {
    float row_sum = 0.;
    for (int k = rowOffsets[i]; k < rowOffsets[i+1]; k++){
      row_sum += values[k]; 
    }
    sum[i] = row_sum;
}

无法重新定义sum[]时的伪共享规避方案 #

在不能修改sum[]结构的前提下，可通过以下方法规避伪共享：

• 调整线程调度策略，使用分块静态调度
  利用OpenMP的schedule(static, chunk_size)指定分块大小，让每个线程处理连续的、刚好填满若干缓存行的数组元素。比如针对float类型，设置chunk_size=16（对应64字节缓存行），这样每个线程写入的sum元素集中在连续的缓存行内，同一缓存行只会被一个线程操作，避免跨线程的缓存冲突。示例：

  #pragma omp parallel for schedule(static, 16)
  for (int i = 0; i < N; i++) {
      float row_sum = 0.;
      for (int k = rowOffsets[i]; k < rowOffsets[i+1]; k++){
        row_sum += values[k]; 
      }
      sum[i] = row_sum;
  }
  

• 使用线程本地临时缓冲区，批量写入sum[]
  每个线程先将计算出的行和存储在自己的本地缓冲区中，待处理完所有负责的行后，再一次性将本地缓冲区的数据拷贝到sum[]。这样每个线程在写入sum[]时操作的是连续的内存区域，同一缓存行仅被单个线程访问，消除伪共享。示例：

  #pragma omp parallel
  {
      int tid = omp_get_thread_num();
      int num_threads = omp_get_num_threads();
      int start = tid * (N / num_threads);
      int end = (tid == num_threads - 1) ? N : (tid + 1) * (N / num_threads);
  
      // 线程本地临时存储，避免实时写入sum的冲突
      std::vector<float> local_sums(end - start, 0.0f);
  
      for (int i = start; i < end; i++) {
          float row_sum = 0.f;
          for (int k = rowOffsets[i]; k < rowOffsets[i+1]; k++) {
              row_sum += values[k];
          }
          local_sums[i - start] = row_sum;
      }
  
      // 批量写入sum，此时每个线程操作连续的缓存行，无跨线程冲突
      std::copy(local_sums.begin(), local_sums.end(), sum + start);
  }
  

内容的提问来源于stack exchange，提问作者Rajesh Shashi Kumar