3

ホグワイルドを実装しようとしています！線形 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 倍にして、2 番目のインデックスごとに意味のあるデータのみを格納します。あなたのアルゴリズムでは、これは何も変わりません。簡単に言えば、 2 を掛ける必要がありますX_indices。そうすることで、1 つのキャッシュ ラインに保存されている有用なデータの数を機械的に 2 で割ることによって、偽共有の可能性をさらに制限できます。ただし、メモリに依存するコードの場合、メモリ消費量を増やすことは最善の方法ではない可能性があります...しかし、テストは非常に簡単なので、試してみて、メリットがあるかどうかを確認してください。

最後に、あなたのコードには OpenMP の並列化にバグがあり#pragma for、#pragma omp for. ここにコピーするときにこれがタイプミスだったのかどうかはわかりませんが、念のため言及しておくことをお勧めします.

于 2015-11-26T08:11:24.843 に答える