c - Hogwild 中的虚假分享!算法

Question

我正在尝试实现 Hogwild! Linear SVM算法，但我的实现遇到了错误共享问题。

我的代码如下，但背景是我正在尝试计算哪些样本未通过测试，并制作和更新由该组 vector 给出的样本。霍格狂野! (据我了解)只是使同一内存的更新完全异步。由于时间更新不正确，这会产生数学意义上的“噪音”。

遗憾的是，当我尝试执行这些异步更新时，L1 缓存已失效，必须重新获取。下面是我的代码。

有没有一个好的方法可以修复这个错误共享而不丢失异步？ (我更像是一名数学家而不是计算机科学家)。 This提到使用不同的优化级别可以解决这个问题。

void update(size_t epoch, const double *X_data, const int *X_indices,
            const int *X_indptr, const int *Y, double *W,
            double reg, double step_size, size_t nodes,
            size_t X_height, size_t X_width) {

  size_t i, j;
  double step = step_size/(1 + epoch);
  double c;

#pragma omp parallel shared(W, X_data, X_indices, X_indptr, Y) private(i, j, c)
  {
#pragma for schedule(static)
    for (i=0;i<X_height;i++) {
      c = 0.0;
      for (j=X_indptr[i];j<X_indptr[i+1];j++)
        c += X_data[j]*W[X_indices[j]]; // Scaled to discount the MPI scaling                                                

      if (Y[i]*c > 1)
        continue;

      for (j=X_indptr[i];j<X_indptr[i+1];j++)
        W[X_indices[j]] += step*Y[i]*X_data[j]/(X_height*nodes);
    } // END FOR OMP PARALLELIZED                                                                                            

#pragma for schedule(static) // Might not do much                                                                            
    for (i=0;i<X_width;i++) // (1 - self.reg*step)*self.W/self.nodes +                                                       
      W[i] *= (1 - reg*step)/nodes;
  }
}

Answer 1

我对你提到的算法不太了解，但在我看来，它在全局范围内的内存限制比计算限制要大得多。为了说服您，这里是对您的代码的快速重写:

void update( size_t epoch, const double *X_data, const int *X_indices,
             const int *X_indptr, const int *Y, double *W,
             double reg, double step_size, size_t nodes,
             size_t X_height, size_t X_width ) {

    const double step = step_size / ( 1 + epoch );
    const double ratio = step / ( X_height * nodes );
    const double tapper = ( 1 - reg * step ) / nodes;

    #pragma omp parallel 
    {
        #pragma omp for schedule( static )
        for ( size_t i = 0; i < X_height; i++ ) {
            double c = 0;
            for ( int j = X_indptr[i]; j < X_indptr[i+1]; j++ ) {
                c += X_data[j] * W[X_indices[j]]; // Scaled to discount the MPI scaling
            }
            if ( Y[i] * c <= 1 ) {
                double ratioYi = Y[i] * ratio;
                for ( int j = X_indptr[i]; j < X_indptr[i+1]; j++ ) {
                    // ATTENTION: this will collide across threads and have undefined result BY DESIGN
                    W[X_indices[j]] += ratioYi * X_data[j];
                }
            }
        } // END FOR OMP PARALLELIZED

        #pragma omp for schedule( static ) // Might not do much
        for ( size_t i = 0; i < X_width; i++ ) { // (1 - self.reg*step)*self.W/self.nodes +
            W[i] *= tapper;
        }
    }
}

如您所见，我做了一些更改。其中大多数纯粹是风格上的(如缩进、间距、变量声明位置等)，但有些确实很重要。例如，通过在循环中定义尽可能浅的 ratio 和 ratioYi，我删除了(或帮助编译器删除，它会这样做吗)大部分计算从代码中。突然之间很明显，代码几乎只访问数据并且计算很少。因此，除非您有一个多插槽(或多内存 Controller )共享内存机器，否则您不会从 OpenMP 并行化中看到太多加速(如果有的话)。

此外，算法在并行更新 W 时接受的“设计”竞争条件，即使在您指出的论文中是合理的，仍然让我困惑。我仍然不想依赖计算代码(或与此相关的任何代码)的未定义行为。

无论如何，假设代码执行您想要的操作、扩展，并且实际上仅受由于错误共享(或者实际上是真正的共享，因为您授权数据冲突)导致的 L1 缓存失效的限制，一个可能的“解决方案”是增加W 数组的大小，例如将其大小加倍，并且仅在每个第二索引存储有意义的数据。在你的算法中，这不会改变任何东西。简而言之，您必须乘以 2 X_indices。通过这样做，您可以通过机械地将单个缓存行中存储的有用数据的数量除以二来进一步限制错误共享的可能性。然而，同样，对于受内存限制的代码，增加内存消耗可能不是最好的主意...但由于这是一个非常简单的测试，只需尝试一下，看看它是否会给您带来任何好处。

最后还要指出的是，您的代码在 OpenMP 并行化中存在错误，即您使用的是 #pragma for 而不是 #pragma omp for。不确定这是否是在此处复制时出现的拼写错误，但最好提及以防万一。