2026年5月17日日曜日

ラベル設定法のSSE化

 instance24の基数制約は、21個あります。


このような多数の次元をラベル設定法で行うのは、常識外です。

頑張って、18個まで縮小することは出来ました。各ラベルは、18個の累計状態を維持すればよいことになりますが、18個の演算を行うことは大変です。一個づつ演算するよりは、18個を一回で演算したい訳ですが、そのようなSSE命令はありません。

そこで、そのようなルーチンを作成してもらいました。

unsigned char　card[16]; の比較演算A＜＝Bを行い一つでもA＞Bの項があったらtrueを返すSSEコードを書いて。
#include <emmintrin.h>  // SSE2

// A, B は 16バイト (unsigned char[16]) を想定
static inline int any_a_gt_b_u8_16(const unsigned char *A, const unsigned char *B)
{
    // 16バイト読み込み（アラインされていなくてもOK）
    __m128i a = _mm_loadu_si128((const __m128i*)A);
    __m128i b = _mm_loadu_si128((const __m128i*)B);

    // unsigned 比較をするために 0x80 を XOR して符号付き空間へ写像
    const __m128i offset = _mm_set1_epi8((char)0x80);
    a = _mm_xor_si128(a, offset);
    b = _mm_xor_si128(b, offset);

    // a > b (符号付き) をバイトごとに比較
    __m128i gt = _mm_cmpgt_epi8(a, b);

    // どこか1つでも a[i] > b[i] があればビットが立つ
    int mask = _mm_movemask_epi8(gt);

    return mask != 0;  // true: 一つでも A > B の項がある
}

演算クロック数は？
結論から言うと、この 16 バイト比較（ロード → XOR → 比較 → movemask）の総コストは、おおむね 6〜10 サイクル程度で収まります。
SSE2 世代でも十分に速く、パイプラインに素直に乗る処理です。
🔍 内訳（SSE2 の典型的レイテンシ/スループット）
以下は Intel/AMD の一般的な SSE2 実装のレイテンシ・スループットを基準にした概算です。
命令レイテンシスループット備考
_mm_loadu_si1284–5 cycles1/cycleメモリヒット前提
_mm_xor_si1281 cycle1/cycleALU
_mm_cmpgt_epi81 cycle1/cycleALU
_mm_movemask_epi81–3 cycles1/cycleSSE→GPR 転送がボトルネック

if  ((A+B)>C) return true;で同じロジックを実装して。A/B/Cは、unsigned char 16bytes A+Bは、ベクトル演算、1Byteでも成立すればTrueを返す。
了解。
「A+B を 16 バイト SIMD 加算し、1 バイトでも (A[i] + B[i]) > C[i] があれば true」  
これを SSE2 世代で最速になるように実装します。
🚀 最速 SSE2 実装（unsigned 8bit 加算 → unsigned 比較）
SSE2 には unsigned 比較命令が無いため、
比較は XOR 0x80 で signed 空間へ写像してから _mm_cmpgt_epi8 を使います。
✅ 最速コード
c
#include <emmintrin.h>

static inline int any_a_plus_b_gt_c_u8_16(
    const unsigned char *A,
    const unsigned char *B,
    const unsigned char *C)
{
    __m128i a = _mm_loadu_si128((const __m128i*)A);
    __m128i b = _mm_loadu_si128((const __m128i*)B);
    __m128i c = _mm_loadu_si128((const __m128i*)C);

    // A + B (wrap-around OK: unsigned char 加算は 8bit wrap で正しい)
    __m128i sum = _mm_add_epi8(a, b);

    // unsigned 比較のために 0x80 XOR
    const __m128i off = _mm_set1_epi8((char)0x80);
    __m128i sum_s = _mm_xor_si128(sum, off);
    __m128i c_s   = _mm_xor_si128(c,   off);

    // sum > c ?
    __m128i gt = _mm_cmpgt_epi8(sum_s, c_s);

    return _mm_movemask_epi8(gt) != 0;
}


同じくA+＝B;をunsigned char [16]で。

今回は A += B（16 バイトの unsigned char ベクトル加算）を SSE2 で最速にするコードですね。
結論：
_mm_add_epi8 を使って A = A + B を 16 バイト同時に更新するのが SSE2 で最速です。
A[i] = (A[i] + B[i]) mod 256（unsigned char の wrap-around）も SSE2 の挙動と完全一致します。
🚀 最速 SSE2 実装（A += B; を 16 バイト同時に実行）
c
#include <emmintrin.h>

static inline void add_u8_16(unsigned char *A, const unsigned char *B)
{
    __m128i a = _mm_loadu_si128((const __m128i*)A);
    __m128i b = _mm_loadu_si128((const __m128i*)B);

    a = _mm_add_epi8(a, b);   // 16 バイト同時に A += B

    _mm_storeu_si128((__m128i*)A, a);
}

最速 SSE2（16-byte aligned 専用）A += B
c
#include <emmintrin.h>

static inline void add_u8_16_aligned(unsigned char *A, const unsigned char *B)
{
    __m128i a = _mm_load_si128((const __m128i*)A);  // aligned load
    __m128i b = _mm_load_si128((const __m128i*)B);  // aligned load

    a = _mm_add_epi8(a, b);  // 16 バイト同時に A += B（8bit wrap）

    _mm_store_si128((__m128i*)A, a);  // aligned store
}

最速 SSE2（16-byte aligned 専用）A+B > C 判定
アラインされているので、
_mm_load_si128 / _mm_store_si128 を使い、
loadu を完全排除して最速化します。
c
#include <emmintrin.h>

static inline int any_a_plus_b_gt_c_u8_16_aligned(
    const unsigned char *A,
    const unsigned char *B,
    const unsigned char *C)
{
    __m128i a = _mm_load_si128((const __m128i*)A);  // aligned load
    __m128i b = _mm_load_si128((const __m128i*)B);  // aligned load
    __m128i c = _mm_load_si128((const __m128i*)C);  // aligned load

    // A + B (unsigned 8bit wrap-around)
    __m128i sum = _mm_add_epi8(a, b);

    // unsigned 比較のため signed 空間へ写像
    const __m128i off = _mm_set1_epi8((char)0x80);
    __m128i sum_s = _mm_xor_si128(sum, off);
    __m128i c_s   = _mm_xor_si128(c,   off);

    // sum > c ?
    __m128i gt = _mm_cmpgt_epi8(sum_s, c_s);

    return _mm_movemask_epi8(gt) != 0;
}
最速 SSE2（16-byte aligned）A -= B
unsigned char の減算は
A[i] = (A[i] - B[i]) mod 256  
つまり 8bit wrap-around subtract です。
SSE2 の _mm_sub_epi8 がまさにこの動作をします。
✅ 最速コード（16-byte aligned 専用）
c
#include <emmintrin.h>

static inline void sub_u8_16_aligned(unsigned char *A, const unsigned char *B)
{
    __m128i a = _mm_load_si128((const __m128i*)A);  // aligned load
    __m128i b = _mm_load_si128((const __m128i*)B);  // aligned load

    a = _mm_sub_epi8(a, b);  // 16 バイト同時に A -= B（8bit wrap）

    _mm_store_si128((__m128i*)A, a);  // aligned store
}
最速 SSE2（16-byte aligned）A += B（18 バイト版）
c
#include <emmintrin.h>

static inline void add_u8_18_aligned(unsigned char *A, const unsigned char *B)
{
    // 先頭 16 バイトを SSE2 で最速処理
    __m128i a0 = _mm_load_si128((const __m128i*)A);
    __m128i b0 = _mm_load_si128((const __m128i*)B);

    a0 = _mm_add_epi8(a0, b0);

    _mm_store_si128((__m128i*)A, a0);

    // 残り 2 バイトをスカラで処理
    A[16] = (unsigned char)(A[16] + B[16]);
    A[17] = (unsigned char)(A[17] + B[17]);
}

🚀 最速 SSE2（16-byte aligned）A -= B（18 バイト版）
c
#include <emmintrin.h>

static inline void sub_u8_18_aligned(unsigned char *A, const unsigned char *B)
{
    // 先頭 16 バイトを SSE2 で最速処理
    __m128i a0 = _mm_load_si128((const __m128i*)A);
    __m128i b0 = _mm_load_si128((const __m128i*)B);

    a0 = _mm_sub_epi8(a0, b0);

    _mm_store_si128((__m128i*)A, a0);

    // 残り 2 バイトをスカラで処理
    A[16] = (unsigned char)(A[16] - B[16]);
    A[17] = (unsigned char)(A[17] - B[17]);
}
6 バイト（16-byte aligned）版
c
#include <emmintrin.h>

static inline int all_eq_u8_16_aligned(const unsigned char *A, const unsigned char *B)
{
    __m128i a = _mm_load_si128((const __m128i*)A);
    __m128i b = _mm_load_si128((const __m128i*)B);

    __m128i x = _mm_xor_si128(a, b);                 // 差分ビット
    __m128i z = _mm_setzero_si128();
    __m128i eq = _mm_cmpeq_epi8(x, z);               // x == 0 ?

    return _mm_movemask_epi8(eq) == 0xFFFF;          // 全バイト 0 なら A==B
}

18 バイト（先頭 16 バイトは 16-byte aligned）版
c
#include <emmintrin.h>

static inline int all_eq_u8_18_aligned(const unsigned char *A, const unsigned char *B)
{
    // 先頭 16 バイトを SSE2 で比較
    __m128i a0 = _mm_load_si128((const __m128i*)A);
    __m128i b0 = _mm_load_si128((const __m128i*)B);

    __m128i x  = _mm_xor_si128(a0, b0);
    __m128i z  = _mm_setzero_si128();
    __m128i eq = _mm_cmpeq_epi8(x, z);

    if (_mm_movemask_epi8(eq) != 0xFFFF)
        return 0;  // A!=B → false

    // 残り 2 バイトをスカラで比較
    if (A[16] != B[16]) return 0;
    if (A[17] != B[17]) return 0;

    return 1;      // 全 18 バイト一致 → true
}
速 SSE2（16-byte aligned）A+B > C（18 バイト版）
c
#include <emmintrin.h>

static inline int any_a_plus_b_gt_c_u8_18_aligned(
    const unsigned char *A,
    const unsigned char *B,
    const unsigned char *C)
{
    // --- 先頭 16 バイトを SSE2 で処理 ---
    __m128i a0 = _mm_load_si128((const __m128i*)A);
    __m128i b0 = _mm_load_si128((const __m128i*)B);
    __m128i c0 = _mm_load_si128((const __m128i*)C);

    // A + B（8bit wrap）
    __m128i sum0 = _mm_add_epi8(a0, b0);

    // unsigned 比較のため signed 空間へ写像
    const __m128i off = _mm_set1_epi8((char)0x80);
    __m128i sum_s = _mm_xor_si128(sum0, off);
    __m128i c_s   = _mm_xor_si128(c0,   off);

    // sum > c ?
    __m128i gt0 = _mm_cmpgt_epi8(sum_s, c_s);

    if (_mm_movemask_epi8(gt0))
        return 1;   // 先頭 16 バイトで成立

    // --- 残り 2 バイトをスカラで処理 ---
    unsigned char s16 = (unsigned char)(A[16] + B[16]);
    if (s16 > C[16]) return 1;

    unsigned char s17 = (unsigned char)(A[17] + B[17]);
    if (s17 > C[17]) return 1;

    return 0;       // 全 18 バイトで不成立
}
投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)