SIMDを使用したHOGの最適化

Question

SIMD命令を使用してHOG記述子の計算を最適化する試みがいくつかあります。OpenCV,DlibおよびSimdです。それらのすべてのHOGヒストグラムに大きさを結果として追加するためにスカラーのコードを使用します。

あり

float histogram[height/8][width/8][18]; 
float ky[height], kx[width]; 
int idx[size]; 
float val[size]; 

for(size_t i = 0; i < size; ++i) 
{ 
    histogram[y/8][x/8][idx[i]] += val[i]*ky[y]*kx[x]; 
    histogram[y/8][x/8 + 1][idx[i]] += val[i]*ky[y]*kx[x + 1]; 
    histogram[y/8 + 1][x/8][idx[i]] += val[i]*ky[y + 1]*kx[x]; 
    histogram[y/8 + 1][x/8 + 1][idx[i]] += val[i]*ky[y + 1]*kx[x + 1]; 
} 

sizeの値は実装からもよるが、一般的には意味は同じです。

私はhistogram calculation with using of SIMDの問題は、単純で効果的な解決策を持っていないことを知っています。しかし、この場合、ヒストグラムのサイズは小さくなります（18）。 SIMDの最適化を助けることができますか？

Answer 1

解決策が見つかりました。それは一時的なバッファです。まず、ヒストグラムを一時バッファに集計します（この操作はベクトル化できます）。その後、我々は（この動作もベクトル化することが可能）、バッファからの出力ヒストグラムに合計を追加します。

float histogram[height/8][width/8][18]; 
float ky[height], kx[width]; 
int idx[size]; 
float val[size]; 
float buf[18][4]; 

for(size_t i = 0; i < size; ++i) 
{ 
    buf[idx[i]][0] += val[i]*ky[y]*kx[x]; 
    buf[idx[i]][1] += val[i]*ky[y]*kx[x + 1]; 
    buf[idx[i]][2] += val[i]*ky[y + 1]*kx[x]; 
    buf[idx[i]][3] += val[i]*ky[y + 1]*kx[x + 1]; 
} 

for(size_t i = 0; i < 18; ++i) 
{ 
    histogram[y/8][x/8][i] += buf[i][0]; 
    histogram[y/8][x/8 + 1][i] += buf[i][1]; 
    histogram[y/8 + 1][x/8][i] += buf[i][2]; 
    histogram[y/8 + 1][x/8 + 1][i] += buf[i][3]; 
} 

Answer 2

SIMDを使用してすべての（平坦化された）ヒストグラムのインデックスとビンの増分を計算することで部分最適化を行うことができます。その後、これらをスカラループで処理します。一時的なビンのインデックスとキャッシュの増分を維持するために、一度に1つの行を処理するように、これを削除したいと思うかもしれません。一時的な中間バッファを使用するため、これは効率が悪いように見えるかもしれませんが、実際には同様のシナリオでは全体的に有用なものがあります。

uint32_t i = 0; 

for (y = 0; y < height; ++y) // for each row 
{ 
    uint32_t inds[width * 4]; // flattened histogram indices for this row 
    float vals[width * 4];  // histogram bin increments for this row 

    // SIMD loop for this row - calculate flattened histogram indices and bin 
    // increments (scalar code shown for reference - converting this loop to 
    // SIMD is left as an exercise for the reader...) 

    for (x = 0; x < width; ++x, ++i) 
    { 
     indices[4*x] = (y/8)*(width/8)*18+(x/8)*18+idx[i]; 
     indices[4*x+1] = (y/8)*(width/8)*18+(x/8 + 1)*18+idx[i]; 
     indices[4*x+2] = (y/8+1)*(width/8)*18+(x/8)*18+idx[i]; 
     indices[4*x+3] = (y/8+1)*(width/8)*18+(x/8 + 1)*18+idx[i]; 

     vals[4*x] = val[i]*ky[y]*kx[x]; 
     vals[4*x+1] = val[i]*ky[y]*kx[x+1]; 
     vals[4*x+2] = val[i]*ky[y+1]*kx[x]; 
     vals[4*x+3] = val[i]*ky[y+1]*kx[x+1]; 
    } 

    // scalar loop for this row 

    float * const histogram_base = &histogram[0][0][0]; // pointer to flattened histogram 

    for (x = 0; x < width * 4; ++x) // for each set of 4 indices/increments in this row 
    { 
     histogram_base[indices[x]] += vals[x]; // update the (flattened) histogram 
    } 

}