c++ - for ループを並列化してもパフォーマンスは向上しません

Question

ベイヤー画像チャンネルを RGB に変換するアルゴリズムがあります。私の実装ではfor、ベイヤー チャネルを反復処理し、ベイヤー インデックスから RGB インデックスを計算し、ベイヤー チャネルからそのピクセルの値を設定する単一のネストされたループがあります。ここで注目すべき主な点は、各ピクセルは他のピクセルとは独立して計算できる (以前の計算に依存しない) ため、このアルゴリズムは自然に並列化の候補になるということです。ただし、計算は、すべてのスレッドが同時にアクセスするが変更されないいくつかのプリセット配列に依存します。

ただし、メインforを MSと並列化しようとするとcuncurrency::parallel_for、パフォーマンスが向上しませんでした。実際、4 コア CPU で実行されるサイズ 3264X2540 の入力の場合、非並列バージョンは ~34 ミリ秒で実行され、並列バージョンは ~69 ミリ秒で実行されました (10 回の実行の平均)。実際に操作が並列化されていることを確認しました (タスク用に 3 つの新しいスレッドが作成されました)。

Intel のコンパイラを使用するとtbb::parallel_for、ほぼ正確な結果が得られました。比較のために、ループC#も使用したこのアルゴリズムの実装から始めたところ、parallel_forほぼ X4 のパフォーマンス向上が見られました (C++この特定のタスクC++ではシングルコアでも高速だったので選択しました)。

私のコードがうまく並列化できない理由は何ですか?

私のコード:

template<typename T>
void static ConvertBayerToRgbImageAsIs(T* BayerChannel, T* RgbChannel, int Width, int Height, ColorSpace ColorSpace)
{
        //Translates index offset in Bayer image to channel offset in RGB image
        int offsets[4];
        //calculate offsets according to color space
        switch (ColorSpace)
        {
        case ColorSpace::BGGR:
            offsets[0] = 2;
            offsets[1] = 1;
            offsets[2] = 1;
            offsets[3] = 0;
            break;
        ...other color spaces
        }
        memset(RgbChannel, 0, Width * Height * 3 * sizeof(T));
        parallel_for(0, Height, [&] (int row)
        {
            for (auto col = 0, bayerIndex = row * Width; col < Width; col++, bayerIndex++)
            {
                auto offset = (row%2)*2 + (col%2); //0...3
                auto rgbIndex = bayerIndex * 3 + offsets[offset];
                RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
            }
        });
}

Answer 1

まず第一に、アルゴリズムはメモリ帯域幅が制限されています。つまり、メモリのロード/ストアは、実行するインデックス計算よりも重要です。

SSE/のようなベクトル演算もAVX役に立ちません。集中的な計算を行っているわけではありません。

反復ごとの作業量を増やすことも無意味です.PPLとTBBは十分に賢く、反復ごとにスレッドを作成しないようにします. 適切なパーティションを使用し、さらに局所性を維持しようとします. たとえば、ここからの引用ですTBB::parallel_for：

ワーカー スレッドが使用可能な場合、parallel_for反復の実行順序は非決定論的です。正確性について特定の実行順序に依存しないでください。ただし、効率のために、parallel_for は値の連続実行で動作する傾向があると考えてください。

本当に重要なのは、メモリ操作を減らすことです。入力バッファまたは出力バッファに対する余分なトラバーサルはパフォーマンスに悪影響を与えるため、削除するmemsetか並行して行う必要があります。

入力データと出力データを完全にトラバースしています。最新のハードウェアではメモリ操作が 64 バイトのチャンクで行われているため、出力で何かをスキップしても問題ありません。したがって、size入力と出力を計算しtime、アルゴリズムを測定し、除算size/time結果をシステムの最大特性と比較します（たとえば、ベンチマークで測定します）。

Microsoft PPL、OpenMPおよびのテストを行いましたNative for。結果は次のとおりです (身長の 8 倍を使用しました)。

Native_For       0.21 s
OpenMP_For       0.15 s
Intel_TBB_For    0.15 s
MS_PPL_For       0.15 s

削除するmemset場合:

Native_For       0.15 s
OpenMP_For       0.09 s
Intel_TBB_For    0.09 s
MS_PPL_For       0.09 s

ご覧のとおりmemset(高度に最適化されています) は、かなりの量の実行時間を担当しています。これは、アルゴリズムがメモリに制限されていることを示しています。

完全なソースコード:

#include <boost/exception/detail/type_info.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/progress.hpp>
#include <tbb/tbb.h>
#include <iostream>
#include <ostream>
#include <vector>
#include <string>
#include <omp.h>
#include <ppl.h>

using namespace boost;
using namespace std;

const auto Width = 3264;
const auto Height = 2540*8;

struct MS_PPL_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        concurrency::parallel_for(first,last,f);
    }
};

struct Intel_TBB_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        tbb::parallel_for(first,last,f);
    }
};

struct Native_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        for(; first!=last; ++first) f(first);
    }
};

struct OpenMP_For
{
    template<typename F,typename Index>
    void operator()(Index first,Index last,F f) const
    {
        #pragma omp parallel for
        for(auto i=first; i<last; ++i) f(i);
    }
};

template<typename T>
struct ConvertBayerToRgbImageAsIs
{
    const T* BayerChannel;
    T* RgbChannel;
    template<typename For>
    void operator()(For for_)
    {
        cout << type_name<For>() << "\t";
        progress_timer t;
        int offsets[] = {2,1,1,0};
        //memset(RgbChannel, 0, Width * Height * 3 * sizeof(T));
        for_(0, Height, [&] (int row)
        {
            for (auto col = 0, bayerIndex = row * Width; col < Width; col++, bayerIndex++)
            {
                auto offset = (row % 2)*2 + (col % 2); //0...3
                auto rgbIndex = bayerIndex * 3 + offsets[offset];
                RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
            }
        });
    }
};

int main()
{
    vector<float> bayer(Width*Height);
    vector<float> rgb(Width*Height*3);
    ConvertBayerToRgbImageAsIs<float> work = {&bayer[0],&rgb[0]};
    for(auto i=0;i!=4;++i)
    {
        mpl::for_each<mpl::vector<Native_For, OpenMP_For,Intel_TBB_For,MS_PPL_For>>(work);
        cout << string(16,'_') << endl;
    }
}

Answer 2

ここに私の提案があります：

1. より大きなチャンクを並行して計算する
2. モジュロ/乗算を取り除く

3. 内側のループを展開して 1 つの完全なピクセルを計算します (コードを簡素化します)

   template<typename T> void static ConvertBayerToRgbImageAsIsNew(T* BayerChannel, T* RgbChannel, int Width, int Height)
   {
       // convert BGGR->RGB
       // have as many threads as the hardware concurrency is
       parallel_for(0, Height, static_cast<int>(Height/(thread::hardware_concurrency())), [&] (int stride)
       {
           for (auto row = stride; row<2*stride; row++)
           {
               for (auto col = row*Width, rgbCol =row*Width; col < row*Width+Width; rgbCol +=3, col+=4)
               {
                   RgbChannel[rgbCol+0]  = BayerChannel[col+3];
                   RgbChannel[rgbCol+1]  = BayerChannel[col+1];
                   // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
                   RgbChannel[rgbCol+2]  = BayerChannel[col+0];
               }
           }
       });
   }
   

このコードは元のバージョンより 60% 高速ですが、私のラップトップでは並列化されていないバージョンの半分の速度しかありません。これは、他の人がすでに指摘しているように、アルゴリズムのメモリ境界によるものと思われます。

編集：しかし、私はそれに満足していませんでした. から に移動すると、並列パフォーマンスが大幅に向上しparallel_forますstd::async。

int hc = thread::hardware_concurrency();
future<void>* res = new future<void>[hc];
for (int i = 0; i<hc; ++i)
{
    res[i] = async(Converter<char>(bayerChannel, rgbChannel, rows, cols, rows/hc*i, rows/hc*(i+1)));
}
for (int i = 0; i<hc; ++i)
{
    res[i].wait();
}
delete [] res;

コンバーターが単純なクラスである場合：

template <class T> class Converter
{
public:
Converter(T* BayerChannel, T* RgbChannel, int Width, int Height, int startRow, int endRow) : 
    BayerChannel(BayerChannel), RgbChannel(RgbChannel), Width(Width), Height(Height), startRow(startRow), endRow(endRow)
{
}
void operator()()
{
    // convert BGGR->RGB
    for(int row = startRow; row < endRow; row++)
    {
        for (auto col = row*Width, rgbCol =row*Width; col < row*Width+Width; rgbCol +=3, col+=4)
        {
            RgbChannel[rgbCol+0]  = BayerChannel[col+3];
            RgbChannel[rgbCol+1]  = BayerChannel[col+1];
            // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
            RgbChannel[rgbCol+2]  = BayerChannel[col+0];
        }
    };
}
private:
T* BayerChannel;
T* RgbChannel;
int Width;
int Height;
int startRow;
int endRow;
};

これは、並列化されていないバージョンよりも 3.5 倍高速になりました。これまでプロファイラーで見てきたことから、parallel_for のワーク スティーリング アプローチは多くの待機と同期のオーバーヘッドを招くと思います。

Answer 3

確認または実行すること

• Core 2 またはそれ以前のプロセッサを使用していますか? このようなコードで飽和しやすい非常に狭いメモリ バスがあります。対照的に、4 チャネルの Sandy Bridge-E プロセッサでは、メモリ バスを飽和させるために複数のスレッドが必要です(単一のメモリ バウンド スレッドで完全に飽和させることはできません)。
• すべてのメモリ チャネルを設定しましたか? たとえば、デュアル チャネルの CPU を使用しているが、RAM カードが 1 つだけ、または同じチャネルに 2 つインストールされている場合、利用可能な帯域幅の半分が得られます。
• コードのタイミングはどのようになっていますか?
  • Evgeny Panasyuk が提案するように、タイミングはアプリケーション内で行う必要があります。
  • 同じアプリケーション内で複数回実行する必要があります。そうしないと、スレッド プールなどを起動するために 1 回限りのスタートアップ コードのタイミングを計っている可能性があります。
• memset他の人が説明したように、余分なを削除します。
• ogni42 や他の人が示唆しているように、内側のループをアンロールします (私はその解決策の正しさをチェックしませんでしたが、間違っている場合は修正できるはずです)。これは、並列化の主な問題とは直交していますが、とにかく良い考えです。
• パフォーマンス テストを行うときは、マシンがアイドル状態であることを確認してください。

追加のタイミング

Evgeny Panasyuk と ogni42 の提案を最小限の C++03 Win32 実装に統合しました。

#include "stdafx.h"

#include <omp.h>
#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;

const int Width = 3264;
const int Height = 2540*8;

class Timer {
private:
    string name;
    LARGE_INTEGER start;
    LARGE_INTEGER stop;
    LARGE_INTEGER frequency;
public:
    Timer(const char *name) : name(name) {
        QueryPerformanceFrequency(&frequency);
        QueryPerformanceCounter(&start);
    }

    ~Timer() {
        QueryPerformanceCounter(&stop);
        LARGE_INTEGER time;
        time.QuadPart = stop.QuadPart - start.QuadPart;
        double elapsed = ((double)time.QuadPart /(double)frequency.QuadPart);
        printf("%-20s : %5.2f\n", name.c_str(), elapsed);
    }
};

static const int offsets[] = {2,1,1,0};

template <typename T>
void Inner_Orig(const T* BayerChannel, T* RgbChannel, int row)
{
    for (int col = 0, bayerIndex = row * Width;
         col < Width; col++, bayerIndex++)
    {
        int offset = (row % 2)*2 + (col % 2); //0...3
        int rgbIndex = bayerIndex * 3 + offsets[offset];
        RgbChannel[rgbIndex] = BayerChannel[bayerIndex];
    }
}

// adapted from ogni42's answer
template <typename T>
void Inner_Unrolled(const T* BayerChannel, T* RgbChannel, int row)
{
    for (int col = row*Width, rgbCol =row*Width;
         col < row*Width+Width; rgbCol +=3, col+=4)
    {
        RgbChannel[rgbCol+0]  = BayerChannel[col+3];
        RgbChannel[rgbCol+1]  = BayerChannel[col+1];
        // RgbChannel[rgbCol+1] += BayerChannel[col+2]; // this line might be left out if g is used unadjusted
        RgbChannel[rgbCol+2]  = BayerChannel[col+0];
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<float> bayer(Width*Height);
    vector<float> rgb(Width*Height*3);
    for(int i = 0; i < 4; ++i)
    {
        {
            Timer t("serial_orig");
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_dynamic_orig");
            #pragma omp parallel for
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_static_orig");
            #pragma omp parallel for schedule(static)
            for(int row = 0; row < Height; ++row) {
                Inner_Orig<float>(&bayer[0], &rgb[0], row);
            }
        }

        {
            Timer t("serial_unrolled");
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_dynamic_unrolled");
            #pragma omp parallel for
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        {
            Timer t("omp_static_unrolled");
            #pragma omp parallel for schedule(static)
            for(int row = 0; row < Height; ++row) {
                Inner_Unrolled<float>(&bayer[0], &rgb[0], row);
            }
        }
        printf("-----------------------------\n");
    }
    return 0;
}

トリプルチャネル 8 ウェイ ハイパースレッディング Core i7-950 ボックスで見たタイミングは次のとおりです。

serial_orig          :  0.13
omp_dynamic_orig     :  0.10
omp_static_orig      :  0.10
serial_unrolled      :  0.06
omp_dynamic_unrolled :  0.04
omp_static_unrolled  :  0.04

「静的」バージョンは、ループの入り口でスレッド間で作業を均等に分割するようにコンパイラーに指示します。これにより、ワーク スチールやその他の動的負荷分散を試みるオーバーヘッドが回避されます。このコード スニペットでは、ワークロードがスレッド全体で非常に均一であるにもかかわらず、違いはないようです。

Answer 4

私は cuncurrency::parallel_for ではなく tbb::parallel_for を使用していませんが、数値が正しい場合、オーバーヘッドが大きすぎるようです。ただし、テスト時には 10 回以上の反復を実行することを強くお勧めします。また、タイミングを計る前に、できるだけ多くのウォームアップ反復を行うようにしてください。

3 つの異なる方法を使用してコードを正確にテストし、平均 1000 回以上試行しました。

Serial:      14.6 += 1.0  ms
std::async:  13.6 += 1.6  ms
workers:     11.8 += 1.2  ms

最初はシリアル計算です。2 つ目は、std::async への 4 つの呼び出しを使用して行われます。最後は、4 つのジョブを、既に開始されている (ただしスリープ状態の) 4 つのバックグラウンド スレッドに送信することによって行われます。

利益は大きくありませんが、少なくとも利益です。デュアル ハイパー スレッド コア = 4 つの論理コアを備えた 2012 MacBook Pro でテストを行いました。

参考までに、これが私の std::async 並列です。

template<typename Int=int, class Fun>
void std_par_for(Int beg, Int end, const Fun& fun)
{
    auto N = std::thread::hardware_concurrency();
    std::vector<std::future<void>> futures;

    for (Int ti=0; ti<N; ++ti) {
        Int b = ti * (end - beg) / N;
        Int e = (ti+1) * (end - beg) / N;
        if (ti == N-1) { e = end; }

        futures.emplace_back( std::async([&,b,e]() {
            for (Int ix=b; ix<e; ++ix) {
                fun( ix );
            }
        }));
    }

    for (auto&& f : futures) {
        f.wait();
    }
}

Answer 5

forループを「行」数のコアに分散しようとしているためにパフォーマンスが低下している可能性がありますが、これは利用できず、並列処理のオーバーヘッドを伴う順次実行のようになります。

Answer 6

並列 for ループについてはあまり詳しくありませんが、競合はメモリ アクセスにあるようです。スレッドが同じページへのアクセスを重複しているようです。

配列へのアクセスを 4k のチャンクに分割して、ページの境界に合わせることはできますか?