1

後で適応しきい値処理ルーチンで使用するために、合計面積テーブルを作成しようとしています。このコードはタイム クリティカルなソフトウェアで使用されるため、コードからできるだけ多くのサイクルを絞り出そうとしています。

パフォーマンスのために、テーブルはすべてのピクセルの符号なし整数です。

プロファイラーをアタッチすると、x-pass の実行時にパフォーマンスの最大のボトルネックが発生することがわかります。

計算の簡単な数式は次のとおりです。

sat_[y * width + x] = sat_[y * width + x - 1] + buff_[y * width + x]
where the running sum resets at every new y position.

この場合、sat_は SAT を表す符号なし整数の 1 次元ポインタでbuff_あり、8 ビットの符号なしモノクロ バッファです。

私の実装は次のようになります。

uint *pSat = sat_;
char *pBuff = buff_;

for (size_t y = 0; y < height; ++y, pSat += width, pBuff += width)
{
    uint curr = 0;
    for (uint x = 0; x < width; x += 4)
    {
        pSat[x + 0] = curr += pBuff[x + 0];
        pSat[x + 1] = curr += pBuff[x + 1];
        pSat[x + 2] = curr += pBuff[x + 2];
        pSat[x + 3] = curr += pBuff[x + 3];
    }
}

私のコンパイラ（VC11）が私のためにそれをしなかったので、ループは手動で展開されます。私が抱えている問題は、セグメンテーション ルーチン全体がそのループを実行するだけで非常に長い時間を費やしていることです。何がそれを高速化できるかについて誰か考えているかどうか疑問に思っています。私は SSE のすべてのセットと、このルーチンが実行される任意のマシンの AVX にアクセスできるので、そこに何かがあれば非常に便利です。

また、最後のサイクルを絞り出したら、これをマルチコアに拡張する予定ですが、モデルをより複雑にする前に、シングル スレッドの計算をできるだけ厳密にしたいと考えています。

4

2 に答える 2

2

各行に沿って依存関係チェーンが実行されています。それぞれの結果は前の結果に依存します。したがって、その方向にベクトル化/並列化することはできません。

ただし、各行は他のすべての行から独立しているように聞こえるため、複数の行を同時に計算することでベクトル化/並列化できます。ベクトル命令がメモリ内の隣接する要素にアクセスできるようにするには、配列を転置する必要があります。*

しかし、それは問題を引き起こします。行に沿って歩くことは、キャッシュの観点からは絶対にひどいものになります (すべての反復がキャッシュ ミスになります)。これを解決する方法は、ループの順序を入れ替えることです。

ただし、各要素は正確に 1 回読み取られることに注意してください。そして、要素ごとにほとんど計算を行っていません。したがって、基本的には、CPU 使用率が 100% に達するかなり前に、メイン メモリの帯域幅によって制限されます。

※この制限はAVX2で解除されるかも知れませんが…

于 2013-03-06T23:15:53.850 に答える
1

アルゴリズム的には、これをさらに最適化するためにできることはないと思います。説明でOLAPキューブという用語を使用していなくても、基本的にはOLAPキューブを構築しているだけです。使用しているコードは、OLAPキューブを構築するための標準的なアプローチです。

使用しているハードウェアの詳細を提供すると、いくつかの最適化が利用できる場合があります。たとえば、高速である場合とそうでない場合があるGPUプログラミングアプローチがあります。注：このスレッドに関する別の投稿では、並列化は不可能であると述べられています。これは必ずしも正しいとは限りません...アルゴリズムを並列に実装することはできませんが、データレベルの並列処理を維持するアルゴリズムがあり、GPUアプローチで利用できます。

于 2013-03-07T01:29:53.390 に答える