64비트 정수로 패킹된8비트 정수를 1씩 병렬로 빼서 하드웨어 SIMD를 사용하지 않음SWAR

64비트 정수로 패킹된8비트 정수를 1씩 병렬로 빼서 하드웨어 SIMD를 사용하지 않음SWAR

64비트 정수의 경우 8개의 요소가 포함된 8비트 정수의 배열로 해석됩니다.를 .1한 요소가 다른 요소의 결과에 영향을 미치지 않고 오버플로우를 처리하는 동안 각 팩된 정수에서 추출할 수 있습니다.

현재 이 코드가 있고 작동하지만 각 패킹된 8비트 정수를 병렬로 빼서 메모리에 액세스하지 않는 솔루션이 필요합니다.에서는 x86의 SIMD 할 수 .psubb패킹된 8비트 정수를 병렬로 빼지만 코드화할 플랫폼은 SIMD 명령을 지원하지 않습니다(이 경우 RISC-V).

그래서 SWAR(레지스터 내의 SIMD)를 실행하여 바이트 간 전파를 수동으로 취소하려고 합니다.uint64_t하다

uint64_t sub(uint64_t arg) {
    uint8_t* packed = (uint8_t*) &arg;

    for (size_t i = 0; i < sizeof(uint64_t); ++i) {
        packed[i] -= 1;
    }

    return arg;
}

비트 연산자로도 할 수 있을 것 같은데 잘 모르겠어요.SIMD 명령을 사용하지 않는 솔루션을 찾고 있습니다.독자적인 솔루션을 실장할 수 있도록, 휴대성이 뛰어난 솔루션이나 그 이면에 있는 이론의 솔루션을 찾고 있습니다.

인 SIMD는 SIMD를 CPU로 사용합니다.paddb )_mm_add_epi8)도 사용할 수 있습니다.Peter Cordes의 답변은 또한 GNU C(gcc/clang) 벡터 구문과 엄밀한 에일리어싱 UB에 대한 안전성에 대해서도 설명합니다.저는 그 답변도 재검토할 것을 강력히 권장합니다.

하는 것uint64_t는 완전하지만, UB에 할 때 문제와 한 에일리어싱 위해 합니다.uint8_t으로 배열하다uint64_t* 요.데이터부터 시작해서uint64_t경우 GNU C의 경우may_aliastypedef를 하십시오).memcpy를 참조해 주세요.

않으면 할 수 .uint64_t을 할 수 있습니다.uint8_t*각 바이트를 원하는 경우. unsigned char*는 8비트 요소의에 대한 를 회피하기 를 지정할 수 8」의 경우는, 「 」를 참조해 주세요).uint8_tunsigned char

---

이는 이전의 잘못된 알고리즘에서 변경된 것입니다(리비전 내역 참조).

이는 임의 감산에 대한 루프 없이 가능하며 각 바이트에서처럼 알려진 상수에 대해 더 효율적입니다.주요 요령은 하이 비트를 설정하여 각 바이트에서 반출을 방지한 다음 감산 결과를 수정하는 것입니다.

여기서 설명하는 뺄셈 기술을 약간 최적화합니다.정의:

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

와 함께H로서 정의되다0x8080808080808080U(즉, 각 패킹된 정수의 MSB).감소를 위해,y이0x0101010101010101U.

우리는 그것을 알고 있습니다.y에는 모든 MSB가 클리어되어 있기 때문에 마스크 단계 중 하나를 건너뛸 수 있습니다(즉,y & ~H와 같다y(우리의 경우)계산은 다음과 같이 진행됩니다.

1. 각 컴포넌트의 MSB를 설정합니다.x차입이 MSB를 통해 다음 컴포넌트로 전파되지 않도록 합니다.이것을 조정된 입력이라고 부릅니다.
2. 각 성분에서 1을 빼서0x01010101010101를 참조해 주세요.스텝 1에 의한 컴포넌트간 차입은 발생하지 않습니다.이것을 조정된 출력이라고 부릅니다.
3. 이제 결과의 MSB를 수정해야 합니다.조정된 출력을 원래 입력의 반전된 MSB로 xor하여 결과 수정을 마칩니다.

조작은 다음과 같이 기술할 수 있습니다.

#define U64MASK 0x0101010101010101U
#define MSBON 0x8080808080808080U
uint64_t decEach(uint64_t i){
      return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON);
}

바람직하게는 컴파일러에 의해 삽입되거나(컴파일러 지시어를 사용하여 강제), 다른 함수의 일부로서 표현식이 인라인으로 작성됩니다.

테스트 케이스:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

퍼포먼스 상세

이것은 함수의 단일 호출을 위한 x86_64 어셈블리입니다.성능을 향상시키려면 상수가 레지스터에 가능한 한 오래 존재할 수 있다는 희망으로 이 값을 표시해야 합니다.상수가 레지스터에 존재하는 타이트 루프에서 실제 감소는 최적화 후 또는 +not+and+add+xor의 5가지 명령을 따릅니다.컴파일러의 최적화를 능가하는 대안이 없습니다.

uint64t[rax] decEach(rcx):
    movabs  rcx, -9187201950435737472
    mov     rdx, rdi
    or      rdx, rcx
    movabs  rax, -72340172838076673
    add     rax, rdx
    and     rdi, rcx
    xor     rdi, rcx
    xor     rax, rdi
    ret

다음 스니펫의 일부 IACA 테스트:

// Repeat the SWAR dec in a loop as a microbenchmark
uint64_t perftest(uint64_t dummyArg){
    uint64_t dummyCounter = 0;
    uint64_t i = 0x74656a6d27080100U; // another dummy value.
    while(i ^ dummyArg) {
        IACA_START
        uint64_t naive = i - U64MASK;
        i = naive + ((i ^ naive ^ U64MASK) & U64MASK);
        dummyCounter++;
    }
    IACA_END
    return dummyCounter;
}

Skylake 머신에서는 감소, xor 및 compare+jump를 반복당 5사이클 미만으로 실행할 수 있음을 알 수 있습니다.

Throughput Analysis Report
--------------------------
Block Throughput: 4.96 Cycles       Throughput Bottleneck: Backend
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.5     0.0  |  1.5  |  0.0     0.0  |  0.0     0.0  |  0.0  |  1.5  |  1.5  |  0.0  |
--------------------------------------------------------------------------------------------------

(물론 x86-64에서는 로딩만 하면 됩니다.movqXMM 레그에 포함시키다paddb따라서 RISC-V와 같은 ISA를 컴파일하는 방법을 살펴보는 것이 더 흥미로울 수 있습니다.)

RISC-V 에서는, GCC/Clang 를 사용하고 있을 가능성이 있습니다.

재미있는 사실: GCC는 이러한 SWAR bitack의 트릭(다른 답변에 나타나 있음)을 알고 있으며 하드웨어 SIMD 명령 없이 타깃의 GNU C 네이티브 벡터를 사용하여 코드를 컴파일할 때 사용할 수 있습니다(그러나 RISC-V는 스칼라 조작에 순진하게 전개되므로 컴파일러 전체에서 뛰어난 퍼포먼스를 필요로 하는 경우는, 스스로 실시할 필요가 있습니다).

네이티브 벡터 구문의 장점 중 하나는 하드웨어 SIMD를 탑재한 머신을 타겟으로 할 때 바이택이나 기타 끔찍한 것을 자동 벡터화하는 대신 그것을 사용할 수 있다는 것입니다.

쉽게 쓸 수 있습니다.vector -= scalar동작: Just Works라는 구문을 사용하여 암묵적으로 스칼라를 브로드캐스트합니다.

---

또, A는uint64_t*로부터의 부하uint8_t array[]는 엄밀한 에일리어싱의 UB이므로 주의해 주십시오.('glibc의 strlen'이 이렇게 복잡할 필요가 있는 이유'도 참조).re: SWAW bathacks를 순수 C로 엄밀한 에일리어싱으로 안전하게 한다).당신은 이런 것을 선언하기를 원할 수 있습니다.uint64_t포인터 캐스트를 통해 다른 오브젝트에 액세스 할 수 있습니다.예를 들어,char*ISO C/C++로 동작합니다.

uint8_t 데이터를 uint64_t로 가져와 다른 응답과 함께 사용할 수 있습니다.

// GNU C: gcc/clang/ICC but not MSVC
typedef uint64_t  aliasing_u64 __attribute__((may_alias));  // still requires alignment
typedef uint64_t  aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

에일리어스 안전 로드를 실행하는 다른 방법은memcpy에uint64_t이 명령어를 사용하면alignof(uint64_t)의 얼라인먼트 요건.그러나 효율적인 비정렬 부하가 없는 ISA에서는 gcc/clang이 인라인화되지 않고 최적화됩니다.memcpy포인터가 정렬되어 있다는 것을 증명하지 못하면 퍼포먼스에 악영향을 미칩니다.

TL: DR: 데이터를 다음과 같이 선언하거나 동적으로 할당하는 것이 최선의 방법입니다.uint64_t또는 8바이트 이상으로 정렬이 보증됩니다(지정된 경우 16바이트).alignas.

부터uint8_t거의 확실하다unsigned char*, 의 바이트에 안전하게 액세스 할 수 있습니다.uint64_t경유로uint8_t*(uint8_t 어레이의 경우는 그 반대도 아닙니다).그래서 이 특별한 경우에 좁은 요소 유형은unsigned char, 엄밀한 에일리어싱의 문제를 회피할 수 있습니다.char특별합니다.

---

GNU C 네이티브벡터 구문의 예:

GNU C 네이티브 벡터는 항상 기본 유형으로 별칭을 지정할 수 있습니다(예:int __attribute__((vector_size(16)))에일리어스를 붙일 수 있다.int하지만 아니다float또는uint8_t다른 것도요.

#include <stdint.h>
#include <stddef.h>

// assumes array is 16-byte aligned
void dec_mem_gnu(uint8_t *array) {
    typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias));
    v16u8 *vecs = (v16u8*) array;
    vecs[0] -= 1;
    vecs[1] -= 1;   // can be done in a loop.
}

하드웨어 SIMD가 없는 RISC-V의 경우vector_size(8)효율적으로 사용할 수 있는 세밀한 표현과 두 배의 작은 벡터를 수행할 수 있습니다.

그렇지만vector_size(8)GCC와 clang을 모두 사용하여 x86에 대해 매우 어리석게 컴파일: GCC는 GP-integer 레지스터에서 SWAR bitacks를 사용하고, 2바이트 요소로 압축 해제하여 16바이트 XMM 레지스터를 채웁니다. (MMX는 구식이므로 적어도 x8664에서는 사용하지 않습니다.)

단,vector_size (16)(Godbolt) 예상대로movdqa/paddb. (모두 1개의 벡터가 생성되어 있는 경우,pcmpeqd same,same)와 함께-march=skylake아직 1개의 YMM 대신 2개의 XMM ops가 있기 때문에 불행히도 현재의 컴파일러는 벡터 ops를 더 넓은 벡터로 "자동 벡터화"하지 않습니다./

AArch64는 사용하기에 나쁘지 않다.vector_size(8)(Godbolt); ARM/AARCH64는 기본적으로 8바이트 또는 16바이트 청크로 동작합니다.d또는q레지스터를 클릭합니다.

따라서 x86, RISC-V, ARM/AArch64 및 POWER를 통한 휴대용 성능을 원하는 경우 를 사용하여 컴파일할 수 있습니다.그러나 MIPS MSA와 같이 64비트 정수 레지스터 내에서 SIMD를 수행하는 ISA도 있습니다.

vector_size(8)를 사용하면 asm을 쉽게 볼 수 있습니다(데이터의 레지스터 값은 1개뿐입니다).Godbolt 컴파일러 탐색기

# GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector

dec_mem_gnu(unsigned char*):
        lui     a4,%hi(.LC1)           # generate address for static constants.
        ld      a5,0(a0)                 # a5 = load from function arg
        ld      a3,%lo(.LC1)(a4)       # a3 = 0x7F7F7F7F7F7F7F7F
        lui     a2,%hi(.LC0)
        ld      a2,%lo(.LC0)(a2)       # a2 = 0x8080808080808080
                             # above here can be hoisted out of loops
        not     a4,a5                  # nx = ~x
        and     a5,a5,a3               # x &= 0x7f... clear high bit
        and     a4,a4,a2               # nx = (~x) & 0x80... inverse high bit isolated
        add     a5,a5,a3               # x += 0x7f...   (128-1)
        xor     a5,a4,a5               # x ^= nx  restore high bit or something.

        sd      a5,0(a0)               # store the result
        ret

다른 비루프 답변과 같은 기본적인 생각이라고 생각합니다.실행 방지 후 결과를 수정하는 것입니다.

이것은 5개의 ALU 명령으로, 내가 생각하는 상위 답변보다 더 나쁘다.단, 크리티컬 패스 레이텐시는 각각2개의 명령 체인이 XOR로 이어지는 3사이클밖에 되지 않습니다.@Reinstate Monica - -- --의 답변은 4사이클의 디프체인(x86의 경우)으로 컴파일됩니다.5사이클 루프의 throughput은 naigent를 포함하여 병목현상을 일으킵니다.sub루프가 지연에 병목현상을 일으킵니다.

하지만, 이것은 쨍그랑 소리와 함께서는 쓸모가 없습니다.로드한 순서대로 추가 및 저장하지도 않고 소프트웨어 파이프라인 작업도 제대로 하지 않습니다.

# RISC-V clang (trunk) -O3
dec_mem_gnu(unsigned char*):
        lb      a6, 7(a0)
        lb      a7, 6(a0)
        lb      t0, 5(a0)
...
        addi    t1, a5, -1
        addi    t2, a1, -1
        addi    t3, a2, -1
...
        sb      a2, 7(a0)
        sb      a1, 6(a0)
        sb      a5, 5(a0)
...
        ret

당신이 작성한 코드는 실제로 당신이 여러 uint64_t를 다루기 시작하면 벡터화된다는 것을 지적하고 싶습니다.

https://godbolt.org/z/J9DRzd

감산이 오버플로하지 않는지 확인한 다음 높은 비트를 수정할 수 있습니다.

uint64_t sub(uint64_t arg) {
    uint64_t x1 = arg | 0x80808080808080;
    uint64_t x2 = ~arg & 0x80808080808080;
    // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction
    return (x1 - 0x101010101010101) ^ x2;
}

이것이 원하는 것인지 확실하지 않지만 8개의 감산을 동시에 수행합니다.

#include <cstdint>

constexpr uint64_t mask = 0x0101010101010101;

uint64_t sub(uint64_t arg) {
    uint64_t mask_cp = mask;
    for(auto i = 0; i < 8 && mask_cp; ++i) {
        uint64_t new_mask = (arg & mask_cp) ^ mask_cp;
        arg = arg ^ mask_cp;
        mask_cp = new_mask << 1;
    }
    return arg;
}

설명:비트 마스크는 8비트 번호 각각1로 시작합니다.우리는 우리의 논쟁으로 그것을 확장한다.여기에 1이 있으면 1을 빼서 멈춰야 합니다.이를 수행하려면 new_mask에서 대응하는 비트를 0으로 설정합니다.0일 경우 1로 설정하고 반송해야 하므로 비트는 1을 유지하고 마스크를 왼쪽으로 이동합니다.새로운 마스크의 제작이 의도한 대로 작동하는지 직접 확인해 보는 게 좋을 것 같은데, 다른 의견도 나쁘지 않을 거야.

PS: 체크 온이 아닌지는 잘 모르겠습니다.mask_cp루프가 null이 아닐 경우 프로그램이 느려질 수 있습니다.이 기능이 없으면 코드는 여전히 올바르고(0 마스크는 아무것도 하지 않기 때문에) 컴파일러가 루프 롤링을 실행하는 것이 훨씬 쉬워집니다.

int subtractone(int x) 
{
    int f = 1; 

    // Flip all the set bits until we find a 1 at position y
    while (!(x & f)) { 
        x = x^f; 
        f <<= 1; 
    } 

    return x^f; // return answer but remember to flip the 1 at y
} 

위의 방법으로 비트 연산을 수행할 수 있으며, 정수를 8비트 조각으로 나누면 이 함수에 8번 보낼 수 있습니다.다음 부분은 "64비트 숫자를 8비트 값으로 분할하는 방법"에서 따왔습니다.위의 기능을 추가하여

uint64_t v= _64bitVariable;
uint8_t i=0,parts[8]={0};
do parts[i++] = subtractone(v&0xFF); while (v>>=8);

이것은, 다른 사람이 이것을 어떻게 발견했는가에 관계없이, 유효한 C 또는 C++입니다.

코드를 생각해내는 것은 아니지만, 1만큼 감소하면 8개의 1s 그룹만큼 감소하여 결과의 LSB가 "flip"되었는지 확인할 수 있습니다.LSB가 토글되지 않은 경우는 인접한8비트에서 반송이 발생했음을 나타냅니다.이를 처리하기 위해 브랜치 없이 일련의 AND/OR/XOR를 계산할 수 있어야 합니다.

각 바이트에만 집중한 후 원래 위치로 되돌립니다.

uint64_t sub(uint64_t arg) {
   uint64_t res = 0;

   for (int i = 0; i < 64; i+=8) 
     res += ((arg >> i) - 1 & 0xFFU) << i;

    return res;
   }

언급URL : https://stackoverflow.com/questions/59637731/subtracting-packed-8-bit-integers-in-an-64-bit-integer-by-1-in-parallel-swar-wi