2

ちょうど頭に浮かんだ質問で、ここで答えを見たことがないと思います。バイナリ加算アルゴリズムにかかる時間は、オペランドのサイズに比例しますか?

明らかに、 と を追加する1101011010101010101101010と10110100101010010101よりも時間がかかります1 + 1が、私の質問はより小さな値に言及しています。ごくわずかな違い、違いがない、理論上の違いはありますか?

このような初歩的な計算では、どの時点でより効率的な計算方法を検討し始めるべきでしょうか? ie: 巨大なべき乗を計算するための大きな指数での 2 乗によるべき乗。

4

3 に答える 3

0

上記の回答には多少同意できません。それは文脈に大きく依存します。

単純な整数演算 (ループ カウンターなど) の場合、64 ビット マシンでは、64 ビットの汎用レジスタ (RSI/RCX/など) を使用して計算が行われます。その場合、8bit 追加でも 64bit 追加でも速度に差はありません。

ただし、整数の配列を処理していて、コンパイラがコードを適切に最適化できたと仮定すると、はい、小さい方が高速です(ただし、あなたが考える理由ではありません)。

AVX2 命令セットでは、4 つの整数加算命令にアクセスできます。

__m256i _mm256_add_epi8 (__m256i a, __m256i b); // 32 x 8bit
__m256i _mm256_add_epi16(__m256i a, __m256i b); // 16 x 16bit
__m256i _mm256_add_epi32(__m256i a, __m256i b); // 8 x 32bit
__m256i _mm256_add_epi64(__m256i a, __m256i b); // 4 x 64bit

それらのすべてが一度に 256 ビットで動作することに気付くでしょう。つまり、8 ビット整数を使用している場合は 32 回の加算を処理できるのに対し、64 ビットを使用している場合は 4 回の整数加算を処理できます。(前述のように、十分な精度があることを確認する必要があります)。それらはすべて、計算に同じ数のクロック サイクル (1clk) を要します。

小さいデータ型を使用すると、主に CPU キャッシュの使用率が向上し、メモリの読み取り/書き込み回数が減少するという他の効果もあります。

ただし、ビットごとの計算に関する元の質問に戻ります。新しい AVX-512 命令セットが登場する前は、それほどばかげているとは思われなかったかもしれません。ただし、新しい命令セットには 3 項論理命令が含まれています。この命令を使用すると、任意のビット長の数値の 512 回の加算をかなり簡単に計算できます。

inline __m512i add(__m512i x, __m512i x, __m512i carry_in)
{
  return _mm512_ternarylogic_epi32(carry_in, y, x, 0x96);
}
inline __m512i adc(__m512i x, __m512i x, __m512i carry_in)
{
  return _mm512_ternarylogic_epi32(carry_in, y, x, 0xE8);
}

__m512i A[NUM_BITS];
__m512i B[NUM_BITS];
__m512i RESULT[NUM_BITS];
__m512i CARRY = _mm512_setzero_ps();

for(int i = 0; i < NUM_BITS; ++i)
{
  RESULT[i] = add(A[i], B[i], CARRY);
  CARRY = adc(A[i], B[i], CARRY);
}

この特定の例 (正直なところ、実際の使用はおそらく非常に限られています!) では、512 回の加算を実行するのにかかる時間は、実際には NUM_BITS に正比例します。

于 2017-06-20T09:04:59.033 に答える