2

私は、他の誰かの次のコードの実行時間を改善する「名誉」を持っています。(これはキャニー アルゴリズムからの非最大抑制です。) 最初に考えたのは、SSE 固有のコードを使用することでした。私はこの分野では非常に新しいので、私の質問は次のとおりです。

これを行う機会はありますか？もしそうなら、誰かが私にいくつかのヒントを与えることができますか?

void vNonMaximumSupression(
          float* fpDst, 
          float const*const fpMagnitude, 
          unsigned char  const*const ucpGradient,                                                                           ///< [in] 0 -> 0°, 1 -> 45°, 2 -> 90°, 3 -> 135°
int iXCount, 
int iXOffset, 
int iYCount, 
int ignoreX, 
int ignoreY)
{
    memset(fpDst, 0, sizeof(fpDst[0]) * iXCount * iXOffset);

    for (int y = ignoreY; y < iYCount - ignoreY; ++y)
    {
        for (int x = ignoreX; x < iXCount - ignoreX; ++x)
        {
            int idx = iXOffset * y + x;
            unsigned char dir = ucpGradient[idx];
            float fMag = fpMagnitude[idx];

            if (dir == 0 && fpMagnitude[idx - 1]           < fMag && fMag > fpMagnitude[idx + 1] ||
                dir == 1 && fpMagnitude[idx - iXCount + 1] < fMag && fMag > fpMagnitude[idx + iXCount - 1] ||
                dir == 2 && fpMagnitude[idx - iXCount]     < fMag && fMag > fpMagnitude[idx + iXCount] ||
                dir == 3 && fpMagnitude[idx - iXCount - 1] < fMag && fMag > fpMagnitude[idx + iXCount + 1]
                )
                    fpDst[idx] = fMag;
            else
                fpDst[idx] = 0;
        }
    }
}
4

1 に答える 1

5

討論

@harold が指摘したように、ここでのベクトル化の主な問題は、アルゴリズムが各ピクセル (方向行列で指定) に異なるオフセットを使用することです。ベクトル化のいくつかの潜在的な方法を考えることができます。

  1. @nikie: すべてのブランチを一度に評価します。つまり、各ピクセルをその隣接するすべてのピクセルと比較します。これらの比較の結果は、方向の値に従ってブレンドされます。
  2. @PeterCordes: 多数のピクセルを SSE レジスタにロード_mm_shuffle_epi8し、指定された方向の隣接ピクセルのみを選択するために使用します。次に、2 つのベクトル化された比較を実行します。
  3. (me): スカラー命令を使用して、方向に沿って適切な 2 つの隣接ピクセルをロードします。次に、4 つのピクセルのこれらの値を SSE レジスタに結合します。最後に、SSE で 2 つの比較を行います。

4 ピクセルのパックの場合、18 個の隣接ピクセルから選択できるため、2 番目のアプローチを効率的に実装するのは非常に困難です。それにはあまりにも多くのシャッフルが必要になると思います。

最初のアプローチは良さそうに見えますが、1 ピクセルあたり 4 倍の操作を実行することになります。ベクトル命令の高速化は、あまりにも多くの計算が行われると圧倒されると思います。

3番目のアプローチを使用することをお勧めします。以下に、パフォーマンスを改善するためのヒントを示します。

ハイブリッド アプローチ

まず第一に、スカラー コードをできるだけ高速に作成したいと考えています。提示されたコードには分岐が多すぎます。それらのほとんどは、たとえば方向による切り替えなど、予測できません。

ブランチを削除するにはdelta = {1, stride - 1, stride, stride + 1}、方向からインデックス オフセットを与える array を作成することをお勧めします。この配列を使用することで、(分岐なしで) 比較する隣接ピクセルのインデックスを見つけることができます。次に、2 つの比較を行います。最後に、res = (isMax ? curr : 0);コンパイラが分岐のないコードを生成できることを期待して、 のような三項演算子を書くことができます。

残念ながら、コンパイラ (少なくとも MSVC2013) は、 による分岐を避けるほどスマートではありませんisMax。そのため、内部サイクルをスカラー SSE 組み込み関数で書き直すことでメリットが得られます。ガイドを参照してください。_ssコードは完全にスカラーであるため、主に で終わる組み込み関数が必要です。

最後に、隣接するピクセルをロードすることを除いて、すべてをベクトル化できます。隣接するピクセルをロードするために_mm_setr_ps、スカラー引数で組み込み関数を使用して、コンパイラに適切なコードを生成するように依頼できます =)

__m128 forw = _mm_setr_ps(src[idx+0 + offset0], src[idx+1 + offset1], src[idx+2 + offset2], src[idx+3 + offset3]);
__m128 back = _mm_setr_ps(src[idx+0 - offset0], src[idx+1 - offset1], src[idx+2 - offset2], src[idx+3 - offset3]);

私はちょうどそれを自分で実装しました。Ivy Bridge 3.4Ghz のシングル スレッドでテスト済み。解像度 1024 x 1024 のランダム画像がソースとして使用されました。結果 (ミリ秒単位) は次のとおりです。

original: 13.078     //your code
branchless: 8.556    //'branchless' code
scalarsse: 2.151     //after rewriting to sse intrinsics
hybrid: 1.159        //partially vectorized code

各ステップでパフォーマンスの向上が確認されています。最終的なコードでは、1 メガピクセルの画像を処理するのに 1 ミリ秒を少し超える時間が必要です。合計で約11​​.3倍の高速化。確かに、GPU でより良いパフォーマンスを得ることができます =)

提示された情報が、手順を再現するのに十分であることを願っています。ひどいスポイラーをお探しの場合は、ここでこれらすべてのステージの実装をご覧ください。

于 2015-09-16T15:23:12.507 に答える