3

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

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

可悲的是，当我尝试进行这些异步更新时，L1 缓存已失效并且必须重新获取。下面是我的代码。

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

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;
  }
}
4

1 回答 1

3

我对您提到的算法知之甚少，但在我看来，它在全球范围内的内存限制比计算限制要多得多。为了说服您，这里快速重写您的代码：

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，即使在您指出的论文中证明是合理的，仍然让我感到困惑。我仍然不想依赖计算代码（或与此相关的任何代码）的未定义行为。

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

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

于 2015-11-26T08:11:24.843 回答