9

与えられた配列：

int canvas[10][10];
int addon[10][10];

すべての値が0〜100の範囲である場合、C ++でこれらの2つの配列を追加して、キャンバスの各セルがそれ自体にアドオンの対応するセル値を加えたものに等しくなるようにする最も速い方法は何ですか？

IE、私は次のようなことを達成したいと思います：

canvas += another;

したがって、canvas [0] [0]=3およびaddon[0][0] = 2の場合、canvas [0] [0] = 5

私はナップザックタイプの問題をブルートフォースする非常に単純なプログラムを書いているので、ここではスピードが不可欠であり、何千万もの組み合わせがあります。

そして、ちょっとした追加の質問として（助けてくれればありがとう！）、canvasの値のいずれかが100を超えているかどうかをチェックする最も速い方法は何でしょうか？ ループが遅い！

4

6 に答える 6

9

Nehalem (Core i7) でかなりうまく機能するはずの SSE4 実装を次に示します。

#include <limits.h>
#include <emmintrin.h>
#include <smmintrin.h>

static inline int canvas_add(int canvas[10][10], int addon[10][10])
{
    __m128i * cp = (__m128i *)&canvas[0][0];
    const __m128i * ap = (__m128i *)&addon[0][0];
    const __m128i vlimit = _mm_set1_epi32(100);
    __m128i vmax = _mm_set1_epi32(INT_MIN);
    __m128i vcmp;
    int cmp;
    int i;

    for (i = 0; i < 10 * 10; i += 4)
    {
        __m128i vc = _mm_loadu_si128(cp);
        __m128i va = _mm_loadu_si128(ap);

        vc = _mm_add_epi32(vc, va);
        vmax = _mm_max_epi32(vmax, vc);   // SSE4 *

        _mm_storeu_si128(cp, vc);

        cp++;
        ap++;
    }
    vcmp = _mm_cmpgt_epi32(vmax, vlimit); // SSE4 *
    cmp = _mm_testz_si128(vcmp, vcmp);    // SSE4 *
    return cmp == 0;
}

gcc -msse4.1 ...特定の開発環境で、または同等のものをコンパイルします。

SSE4 を使用しない古い CPU (およびはるかにコストのかかるミスアラインされたロード/ストアがある) の場合、(a) SSE2/SSE3 組み込み関数の適切な組み合わせを使用して SSE4 操作 (*上記のマークが付いている) を置き換える必要があり、理想的には (b) makeデータが 16 バイト アラインされていることを確認し、アラインされたロード/ストア ( _mm_load_si128/ _mm_store_si128) を_mm_loadu_si128/の代わりに使用します_mm_storeu_si128。

于 2010-06-03T08:19:52.420 に答える
3

標準 C または C++ で行う最善の方法は、それを 100 個の数値の 1 次元配列として再キャストし、それらをループに追加することです。(単一の添字は、コンパイラーがそれを最適化できない限り、二重の添字よりも少し少ない処理を使用します。影響がある場合、影響がどれだけあるかを知る唯一の方法は、テストすることです。)

確かに、1 つの単純な C++ 命令 ( canvas += addon;) を追加するクラスを作成できますが、それでは何も高速化されません。単純な C++ 命令が上記のループに展開されるだけです。

それを高速化するには、低レベルの処理に入る必要があります。最新の多くの CPU には、使用できる可能性のあるこのような処理を行うための追加の命令があります。Cudaのようなものを使用して GPU でこのようなものを実行できるかもしれません。操作を並列にして複数のコアで実行することもできますが、このような小さなインスタンスでは、CPU でキャッシュがどのように機能するかを知る必要があります。

別の方法としては、アルゴリズムを改善するか (ナップザック タイプの問題では、何らかの方法で動的計画法を使用できる可能性があります。これ以上の情報がなくても、それをお伝えすることはできません)、またはパフォーマンスを受け入れることです。10 x 10 の配列に対する数千万回の演算は、数値に対する数千億回の演算に変わります。これは、以前ほど威圧的ではありません。もちろん、あなたの使用シナリオやパフォーマンス要件はわかりません。

于 2010-06-02T16:37:56.017 に答える
3

C++ だけでは、ループよりも高速なことはできません。プラットフォーム固有のベクトル命令を使用する必要があります。つまり、アセンブリ言語レベルまで下げる必要があります。ただし、これを実行しようとする C++ ライブラリがいくつかあるため、高レベルで記述し、コンパイラで対象とするアーキテクチャに適した低レベルのSIMD作業をライブラリに任せることができます。

MacSTLは、検討したいライブラリです。元々は Macintosh 専用のライブラリでしたが、現在はクロスプラットフォームです。詳細については、ホームページを参照してください。

于 2010-06-02T16:22:36.760 に答える
2

これが代替案です。

すべての値が 0 から 100 の間にあることが 100% 確実な場合は、型を int から uint8_t に変更できます。次に、オーバーフローを心配することなく、 uint32_t を使用して一度に 4 つの要素を一緒に追加できます。

あれは ...

uint8_t  array1[10][10];
uint8_t  array2[10][10];
uint8_t  dest[10][10];
uint32_t *pArr1 = (uint32_t *) &array1[0][0];
uint32_t *pArr2 = (uint32_t *) &array2[0][0];
uint32_t *pDest = (uint32_t *) &dest[0][0];

int  i;

for (i = 0; i < sizeof (dest) / sizeof (uint32_t); i++) {
    pDest[i] = pArr1[i] + pArr2[i];
}

これは最も洗練されたものではないかもしれませんが、アーキテクチャ固有のコードに行かないようにするのに役立ちます。さらに、これを行う場合は、何をしているのか、その理由についてコメントすることを強くお勧めします.

于 2010-06-08T14:39:18.807 に答える
2

2 つの部分: まず、2 次元配列 [10][10] を単一の配列 [100] と見なします。C++ のレイアウト ルールでは、これを許可する必要があります。次に、 Intel の SSE など、何らかの形式のSIMD 命令を実装する組み込み関数についてコンパイラを確認します。たとえば、Microsoft はセットを提供しています。SSEには、最大値をチェックするための指示があり、必要に応じて最大値にクランプすることさえあると思います。

于 2010-06-02T16:21:25.890 に答える
1

CUDA をチェックアウトする必要があります。この種の問題はCUDA のすぐそばにあります。大規模並列プロセッサのプログラミングの本をお勧めします。

ただし、これには CUDA 対応のハードウェアが必要であり、CUDA は開発環境でセットアップするのに少し手間がかかるため、これが実際にどれほど重要かによって異なります。

幸運を！

于 2010-08-14T12:01:07.083 に答える