Hogwild 的虚假分享！算法

Question

我正在尝试实施 Hogwild! Linear SVM 算法，但我运行在我的实施过程中遇到了虚假共享问题。

我的代码在下面，但背景是我正在尝试计算哪些样本未通过我的测试，并制作和更新由那组向量给出的样本。野猪！（据我所知）只是完全异步地对同一内存进行更新。由于不正确的时间更新，这将在数学意义上创建 "noise"。

遗憾的是，当我尝试执行这些异步更新时，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 定义为尽可能浅的循环，我从代码中删除了（或者帮助编译器删除，如果它已经完成的话）大部分计算。突然间很明显，代码几乎只访问数据并且计算很少。因此，除非你有一个多插槽（或多内存控制器）共享内存机器，否则你不会看到这个 OpenMP 并行化有多少加速（如果有的话）。

此外，算法在并行更新 W 时接受的 "by design" 竞争条件，即使在您指出的论文中是合理的，也继续让我感到困惑。我仍然不想依赖计算代码（或与此相关的任何代码）的未定义行为。

无论如何，假设代码按照您的意愿进行扩展，并且确实仅受限于由于错误共享（或者此处确实是真实共享，因为您授权数据冲突）导致的 L1 缓存失效，一个可能的 "solution"将增加 W 数组的大小，例如将其大小加倍，并且仅在每个第二个索引中存储有意义的数据。在您的算法中，这不会改变任何东西。简单地说，您必须乘以 2 X_indices。通过这样做，您可以通过将存储在单个缓存行中的有用数据的数量机械地除以二来进一步限制错误共享的可能性。然而，再次强调，对于受内存限制的代码，增加内存消耗可能不是最好的主意......但是由于它是一个非常简单的测试，只需尝试一下，看看它是否会给你带来任何好处。

最后还要说明的是，您的代码在 OpenMP 并行化中存在错误，因此您使用 #pragma for 而不是 #pragma omp for。不确定这是不是复制到此处时的错字，但最好提一下以防万一。

Hogwild 的虚假分享！算法

False Sharing in Hogwild! Algorithms

c

machine-learning

openmp

false-sharing