image-processing - SIMDでヒストグラムをベクトル化する方法は?

Question

ネオンでヒストグラムを実装しようとしています。ベクトル化することは可能ですか?

Answer 1

残念ながら、ヒストグラムをベクトル化することはほとんど不可能です。

ただし、おそらくスカラーコードをある程度最適化することはできます。一般的なトリックは、2つのヒストグラムを使用し、最後にそれらを結合することです。これにより、ロード/インクリメント/ストアをオーバーラップさせ、それによってシリアル依存関係と関連するレイテンシーの一部を埋めることができます。擬似コード：

init histogram 1 to all 0s
init histogram 2 to all 0s
loop
  get input value 1
  get input value 2
  load count for value 1 from histogram 1
  load count for value 2 from histogram 2
  increment count for histogram 1
  increment count for histogram 2
  store count for value 1 to histogram 1
  store count for value 2 to histogram 2
until done
combine histogram 1 and histogram 2

Answer 2

ermig1979 には Simd プロジェクトがあり、@Paul-R が言及したものと同様のアプローチを使用してヒストグラムを作成した方法を示していますが、SSE2 および AVX2 バリアントも使用しています。

プロジェクト: https://github.com/ermig1979/Simd

ベースファイル: https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp

AVX2 の実装は、 https ://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.cpp で確認できます 。

最後に合計される複数のヒストグラムを作成する基本原則を説明するために、スカラー ソリューションを以下に示します。

void Histogram(const uint8_t * src, size_t width, size_t height, size_t stride, 
    uint32_t * histogram)
{
    uint32_t histograms[4][HISTOGRAM_SIZE];
    memset(histograms, 0, sizeof(uint32_t)*HISTOGRAM_SIZE*4);
    size_t alignedWidth = Simd::AlignLo(width, 4);
    for(size_t row = 0; row < height; ++row)
    {
        size_t col = 0;
        for(; col < alignedWidth; col += 4)
        {
            ++histograms[0][src[col + 0]];
            ++histograms[1][src[col + 1]];
            ++histograms[2][src[col + 2]];
            ++histograms[3][src[col + 3]];
        }
        for(; col < width; ++col)
            ++histograms[0][src[col + 0]];

        src += stride;
    }

    for(size_t i = 0; i < HISTOGRAM_SIZE; ++i)
        histogram[i] = histograms[0][i] + histograms[1][i] + 
            histograms[2][i] + histograms[3][i];
}

Answer 3

@Paul-R、このリンクには、ヒストグラム関数をベクトル化する方法について説明している論文があります。

ヒストグラム関数の SIMD ベクトル化