c-在Hogwild错误分享！算法

Question

我正在尝试实现Hogwind！线性SVM算法，但我在实现过程中遇到了错误共享问题。

我的代码在下面，但背景是我正在尝试计算哪些样本未通过测试，并生成和更新由该组向量给出的样本。霍格威尔！（据我所知）只是完全异步地对同一内存进行更新。这将产生数学意义上的"噪音"，因为更新时间不正确。

遗憾的是，当我尝试进行这些异步更新时，一级缓存无效，必须重新获取。下面是我的代码。

有没有一种好的方法可以在不丢失异步的情况下修复这种错误的共享？（与其说我是计算机科学家，不如说我是数学家）。这提到使用不同的优化级别可以解决这个问题。

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时接受的"设计"竞赛条件，即使在你指出的论文中是合理的，也一直困扰着我。我仍然不想依赖计算代码（或任何相关代码）的未定义行为。

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

最后要注意的是，您的代码在OpenMP并行化中有一个错误，即您有#pragma for而不是#pragma omp for。不确定这是否是在这里复制时的拼写错误，但最好提及它以备不时之需。