10

私は巨大なvector<vector<int>>（18M x 128）を持っています。頻繁に、このベクトルの 2 行を取り、この関数でそれらを比較したいと思います。

    int getDiff(int indx1, int indx2) {
    int result = 0;
    int pplus, pminus, tmp;

    for (int k = 0; k < 128; k += 2) {
        pplus = nodeL[indx2][k] - nodeL[indx1][k];
        pminus = nodeL[indx1][k + 1] - nodeL[indx2][k + 1];

        tmp = max(pplus, pminus);
        if (tmp > result) {
            result = tmp;
        }
    }
    return result;
}

ご覧のとおり、この関数は 2 つの行ベクトルをループして減算を行い、最後に最大値を返します。この機能は100万回使うので、SSE命令で高速化できないかと思っていました。Ubuntu 12.04 と gcc を使用しています。

もちろんマイクロ最適化ですが、SSEについて何も知らないので、助けていただけると助かります。前もって感謝します

基準：

    int nofTestCases = 10000000;

    vector<int> nodeIds(nofTestCases);
    vector<int> goalNodeIds(nofTestCases);
    vector<int> results(nofTestCases);

    for (int l = 0; l < nofTestCases; l++) {
        nodeIds[l] = randomNodeID(18000000);
        goalNodeIds[l] = randomNodeID(18000000);
    }



    double time, result;

    time = timestamp();
    for (int l = 0; l < nofTestCases; l++) {
        results[l] = getDiff2(nodeIds[l], goalNodeIds[l]);
    }
    result = timestamp() - time;
    cout << result / nofTestCases << "s" << endl;

    time = timestamp();
    for (int l = 0; l < nofTestCases; l++) {
        results[l] = getDiff(nodeIds[l], goalNodeIds[l]);
    }
    result = timestamp() - time;
    cout << result / nofTestCases << "s" << endl;

どこ

int randomNodeID(int n) {
    return (int) (rand() / (double) (RAND_MAX + 1.0) * n);
}

/** Returns a timestamp ('now') in seconds (incl. a fractional part). */
inline double timestamp() {
    struct timeval tp;
    gettimeofday(&tp, NULL);
    return double(tp.tv_sec) + tp.tv_usec / 1000000.;
}
4

4 に答える 4

7

FWIW 純粋な SSE バージョン (SSE4.1) をまとめました。これは、Core i7 で元のスカラー コードよりも約 20% 高速に実行されるようです。

#include <smmintrin.h>

int getDiff_SSE(int indx1, int indx2)
{
    int result[4] __attribute__ ((aligned(16))) = { 0 };

    const int * const p1 = &nodeL[indx1][0];
    const int * const p2 = &nodeL[indx2][0];

    const __m128i vke = _mm_set_epi32(0, -1, 0, -1);
    const __m128i vko = _mm_set_epi32(-1, 0, -1, 0);

    __m128i vresult = _mm_set1_epi32(0);

    for (int k = 0; k < 128; k += 4)
    {
        __m128i v1, v2, vmax;

        v1 = _mm_loadu_si128((__m128i *)&p1[k]);
        v2 = _mm_loadu_si128((__m128i *)&p2[k]);
        v1 = _mm_xor_si128(v1, vke);
        v2 = _mm_xor_si128(v2, vko);
        v1 = _mm_sub_epi32(v1, vke);
        v2 = _mm_sub_epi32(v2, vko);
        vmax = _mm_add_epi32(v1, v2);
        vresult = _mm_max_epi32(vresult, vmax);
    }
    _mm_store_si128((__m128i *)result, vresult);
    return max(max(max(result[0], result[1]), result[2]), result[3]);
}
于 2013-07-23T07:14:58.990 に答える
3

これにはおそらく、コンパイラーに SSE を使用させることができます。コードは速くなりますか？おそらくそうではありません。その理由は、計算に比べてメモリアクセスが多いためです。CPU はメモリよりもはるかに高速であり、上記の単純な実装では、システム バスを介してデータが到着するのを待っているときに、CPU が既に停止しています。CPU を高速化すると、待機時間が増えるだけです。

nodeL の宣言はパフォーマンスに影響を与える可能性があるため、データの効率的なコンテナーを選択することが重要です。

最適化に利点があるしきい値があります。それは、メモリ読み取り間の計算が増えるときです。つまり、メモリ読み取り間の時間がはるかに長くなります。これが発生するポイントは、ハードウェアに大きく依存します。

ただし、並列で実行できるメモリ制約のないタスクがある場合は、コードを最適化して、データを待機している間 CPU をビジー状態に保つことができます。

于 2013-07-22T16:00:14.960 に答える
3

注目すべき点がいくつかあります。1 つは、やり取りするデータの量です。それは些細な計算よりも大きな問題を引き起こします。

ここのライブラリを使用してSSE命令（AVX）を使用して書き直そうとしました

私のシステムの元のコードは 11.5 秒で実行されました Neil Kirk の最適化により、10.5 秒に短縮されました

編集:頭の中でではなく、デバッガーでコードをテストしました!

int getDiff(std::vector<std::vector<int>>& nodeL,int row1, int row2) {
    Vec4i result(0);
    const std::vector<int>& nodetemp1 = nodeL[row1];
const std::vector<int>& nodetemp2 = nodeL[row2];

Vec8i mask(-1,0,-1,0,-1,0,-1,0);
for (int k = 0; k < 128; k += 8) {
    Vec8i nodeA(nodetemp1[k],nodetemp1[k+1],nodetemp1[k+2],nodetemp1[k+3],nodetemp1[k+4],nodetemp1[k+5],nodetemp1[k+6],nodetemp1[k+7]);
    Vec8i nodeB(nodetemp2[k],nodetemp2[k+1],nodetemp2[k+2],nodetemp2[k+3],nodetemp2[k+4],nodetemp2[k+5],nodetemp2[k+6],nodetemp2[k+7]);
    Vec8i tmp = select(mask,nodeB-nodeA,nodeA-nodeB);
    Vec4i tmp_a(tmp[0],tmp[2],tmp[4],tmp[6]);
    Vec4i tmp_b(tmp[1],tmp[3],tmp[5],tmp[7]);
    Vec4i max_tmp = max(tmp_a,tmp_b);
    result = select(max_tmp > result,max_tmp,result);
}
return horizontal_add(result);

}

分岐がないため、最大 9.5 秒まで高速化されますが、それでもデータが最大の影響を及ぼします。

さらに高速化したい場合は、データ構造を 2D のもの (ala std::vector) ではなく単一の配列/ベクトルに変更してみてください。これにより、キャッシュの負荷が軽減されます。

編集 私は何かを考えました-カスタムアロケーターを追加して、2 * 18Mベクトルを連続したメモリブロックに確実に割り当てることができます。これにより、データ構造を維持しながらすばやく処理できます。ただし、確実にプロファイリングする必要があります

編集 2: 頭の中ではなく、デバッガーでコードをテストしました! 申し訳ありませんアレックス、これはより良いはずです。コンパイラができることよりも速いかどうかはわかりません。問題はメモリ アクセスであると私はまだ主張しているので、単一配列のアプローチを試してみます。ただし、これを試してください。

于 2013-07-22T19:26:22.347 に答える