4

私のプログラムで最も計算量の多い関数を最適化するための助けが必要です。現在、基本 (非 SSE) バージョンの方が大幅に高速 (最大 3 倍) であることがわかりました。したがって、これを修正するためにあなたの助けを求めます。

この関数は、符号なし整数ベクトルでサブセットを検索し、存在するかどうかを報告します。便宜上、関連するコード スニペットのみを含めました。

まずはベーシックなバリエーション。blocks_が の適切なサブセットであるかどうかを確認しますx.blocks_。(厳密には同じではありません。) これらはビットマップ、別名ビット ベクトルまたはビットセットです。

//Check for self comparison
    if (this == &x)
            return false;

//A subset is equal to or smaller.
    if (no_bits_ > x.no_bits_)
            return false;

    int i;

    bool equal = false;

//Pointers should not change.  
    const unsigned int *tptr = blocks_;
    const unsigned int *xptr = x.blocks_;

    
    for (i = 0; i < no_blocks_; i++, tptr++, xptr++) {
            if ((*tptr & *xptr) != *tptr)
                    return false;
            if (*tptr != *xptr)
                    equal = true;
    }

    return equal;

次に、残念ながら私の期待どおりに機能しない SSE バリアントが登場します。これらのスニペットはどちらも同じものを探す必要があります。

    //starting pointers.        
    const __m128i* start = (__m128i*)&blocks_;
    const __m128i* xstart = (__m128i*)&x.blocks_;
    
    __m128i block;
    __m128i xblock;

    //Unsigned ints are 32 bits, meaning 4 can fit in a register.
    for (i = 0; i < no_blocks_; i+=4) {

            block = _mm_load_si128(start + i);
            xblock = _mm_load_si128(xstart + i);

                    //Equivalent to  (block & xblock) != block
                    if (_mm_movemask_epi8(_mm_cmpeq_epi32(_mm_and_si128(block, xblock), block)) != 0xffff)
                            return false;

                    //Equivalent to block != xblock
                    if (_mm_movemask_epi8(_mm_cmpeq_epi32(block, xblock)) != 0xffff)
                            equal = true;
    }
    return equal;

SSE バージョンのパフォーマンスを改善する方法について何か提案はありますか? 私は何か間違ったことをしていますか？それとも、これは最適化を別の場所で行うべきケースですか?

の残りの計算をまだ追加していませんがno_blocks_ % 4 != 0、パフォーマンスが向上するまで追加する目的はほとんどなく、この時点でコードが乱雑になるだけです。

4

2 に答える 2

4

ここには 3 つの可能性があります。

まず、データが広範な比較に適していない可能性があります。最初の数ブロック以内である可能性が高い場合(*tptr & *xptr) != *tptrは、プレーンな C++ バージョンがほぼ確実に高速になります。その場合、SSE は同じことを達成するために、より多くのコードとデータを実行します。

次に、SSE コードが間違っている可能性があります。ここでは完全に明確ではありません。no_blocks_2 つのサンプル間で が同一の場合start + i、最初のサンプルの 32 ビット要素ではなく、128 ビット要素にインデックス付けするという望ましくない動作が発生している可能性があります。

第 3 に、SSEは、命令をパイプライン化できる場合に非常に気に入っています。これは非常に短いループであるため、取得できない可能性があります。一度に複数の SSE ブロックを処理することで、分岐を大幅に減らすことができます。

これは、一度に 2 つの SSE ブロックを処理する未テストの簡単なショットです。block != xblock状態をループの外に保ち、最後にのみテストすることで、ブランチを完全に削除したことに注意してください。合計すると、これにより 1.3 ブランチあたりintから 0.25 ブランチに移動します。

bool equal(unsigned const *a, unsigned const *b, unsigned count)
{
    __m128i eq1 = _mm_setzero_si128();
    __m128i eq2 = _mm_setzero_si128();

    for (unsigned i = 0; i != count; i += 8)
    {
        __m128i xa1 = _mm_load_si128((__m128i const*)(a + i));
        __m128i xb1 = _mm_load_si128((__m128i const*)(b + i));

        eq1 = _mm_or_si128(eq1, _mm_xor_si128(xa1, xb1));
        xa1 = _mm_cmpeq_epi32(xa1, _mm_and_si128(xa1, xb1));

        __m128i xa2 = _mm_load_si128((__m128i const*)(a + i + 4));
        __m128i xb2 = _mm_load_si128((__m128i const*)(b + i + 4));

        eq2 = _mm_or_si128(eq2, _mm_xor_si128(xa2, xb2));
        xa2 = _mm_cmpeq_epi32(xa2, _mm_and_si128(xa2, xb2));

        if (_mm_movemask_epi8(_mm_packs_epi32(xa1, xa2)) != 0xFFFF)
            return false;
    }

    return _mm_movemask_epi8(_mm_or_si128(eq1, eq2)) != 0;
}

十分なデータがあり、最初の数 SSE ブロック内で失敗する可能性が低い場合、このようなものは少なくとも SSE よりもいくらか高速になるはずです。

于 2013-07-03T15:54:19.317 に答える