Odejmowanie spakowanych 8-bitowych liczb całkowitych w 64-bitowej liczbie całkowitej przez 1 równolegle, SWAR bez sprzętowej karty SIMD

Jeśli mam 64-bitową liczbę całkowitą, którą interpretuję jako tablicę spakowanych 8-bitowych liczb całkowitych z 8 elementami. Muszę odjąć stałą 1od każdej spakowanej liczby całkowitej podczas obsługi przelewu bez wpływu jednego elementu na wynik innego elementu.

Mam ten kod w tej chwili i działa, ale potrzebuję rozwiązania, które odejmuje każdą zapakowaną 8-bitową liczbę całkowitą równolegle i nie zapewnia dostępu do pamięci. Na x86 mogłem używać instrukcji SIMD, takich jak psubbto, odejmując równolegle zapakowane 8-bitowe liczby całkowite, ale platforma, na której koduję, nie obsługuje instrukcji SIMD. (RISC-V w tym przypadku).

Więc próbuję wykonać SWAR (SIMD w rejestrze), aby ręcznie anulować propagację przenoszenia między bajtami a uint64_t, robiąc coś równoważnego z tym:

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;
}

Myślę, że można to zrobić za pomocą bitowych operatorów, ale nie jestem pewien. Szukam rozwiązania, które nie korzysta z instrukcji SIMD. Szukam rozwiązania w C lub C ++, które jest dość przenośne, lub po prostu teoria za nim, aby móc wdrożyć własne rozwiązanie.

Jeśli masz procesor z wydajnymi instrukcjami SIMD, SSE / MMX paddb( _mm_add_epi8) jest również opłacalne. Odpowiedź Petera Cordesa opisuje także składnię wektorową GNU C (gcc / clang) oraz bezpieczeństwo dla UB z dokładnym aliasingiem. Gorąco zachęcam również do przejrzenia tej odpowiedzi.

Robienie tego samemu uint64_tjest w pełni przenośne, ale nadal wymaga ostrożności, aby uniknąć problemów z wyrównaniem i ścisłego aliasingu UB podczas uzyskiwania dostępu do uint8_ttablicy za pomocą uint64_t*. Zostawiłeś tę część pytania, zaczynając od danych uint64_tjuż w, ale w GNU C may_aliastypedef rozwiązuje problem (zobacz odpowiedź Piotra na to lub memcpy).

W przeciwnym razie możesz przydzielić / zadeklarować swoje dane jako uint64_ti uzyskać do nich dostęp, uint8_t*gdy chcesz mieć poszczególne bajty. unsigned char*wolno aliasować wszystko, aby uniknąć problemu w konkretnym przypadku elementów 8-bitowych. (Jeśli uint8_tw ogóle istnieje, prawdopodobnie można bezpiecznie założyć, że jest unsigned char.)

Zauważ, że jest to zmiana w stosunku do wcześniejszego niepoprawnego algorytmu (patrz historia zmian).

Jest to możliwe bez pętli dla arbitralnego odejmowania i staje się bardziej efektywne dla znanej stałej, jak 1w każdym bajcie. Główną sztuczką jest zapobieganie wykonywaniu każdego bajtu przez ustawienie wysokiego bitu, a następnie poprawianie wyniku odejmowania.

Zamierzamy nieznacznie zoptymalizować podaną tutaj technikę odejmowania . Określają:

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

ze Hzdefiniowanym jako 0x8080808080808080U(tj. MSB dla każdej spakowanej liczby całkowitej). Dla dekrementacji yjest 0x0101010101010101U.

Wiemy, że ywszystkie MSB są czyste, więc możemy pominąć jeden z kroków maski (tzn. y & ~HJest taki sam jak yw naszym przypadku). Obliczenia przebiegają w następujący sposób:

1. Ustawiamy MSB każdego składnika xna 1, aby pożyczka nie mogła się rozchodzić za MSB do następnego składnika. Nazwij to dostosowanym wejściem.
2. Odejmujemy 1 od każdego składnika, odejmując 0x01010101010101od skorygowanego wejścia. Nie powoduje to pożyczek między komponentami dzięki krokowi 1. Nazwij to dostosowaną mocą wyjściową.
3. Musimy teraz poprawić MSB wyniku. Xor dostosowujemy moc wyjściową z odwróconymi MSB oryginalnego wejścia, aby zakończyć ustalanie wyniku.

Operację można zapisać jako:

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

Najlepiej jest to podkreślone przez kompilator ( aby wymusić to za pomocą dyrektyw kompilatora ), lub wyrażenie jest zapisywane jako część innej funkcji.

Przypadki testowe:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Szczegóły wydajności

Oto zestaw x86_64 dla pojedynczego wywołania funkcji. Aby uzyskać lepszą wydajność, należy podkreślić, że stałe mogą żyć w rejestrze tak długo, jak to możliwe. W ciasnej pętli, w której stałe żyją w rejestrze, faktyczne zmniejszenie wymaga pięciu instrukcji: lub + nie + i + dodaj + xor po optymalizacji. Nie widzę alternatyw, które przeszłyby optymalizację kompilatora.

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

Z niektórymi testami IACA następującego fragmentu kodu:

// 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;
}

możemy pokazać, że na maszynie Skylake wykonywanie dekrementacji, xor i porównaj + skok można wykonać przy prawie 5 cyklach na iterację:

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  |
--------------------------------------------------------------------------------------------------

(Oczywiście na x86-64 po prostu ładowałbyś lub movqdo regułu XMM dla paddb, więc bardziej interesujące może być spojrzenie na to, jak się kompiluje dla ISA, takiego jak RISC-V.)

W przypadku RISC-V prawdopodobnie używasz GCC / clang.

Ciekawostka: GCC zna niektóre z tych sztuczek SWAR (pokazanych w innych odpowiedziach) i może ich użyć podczas kompilacji kodu z wektorami natywnymi GNU C dla celów bez instrukcji sprzętowych SIMD. (Ale kliknięcie na RISC-V po prostu naiwnie rozwinie go do operacji skalarnych, więc musisz to zrobić sam, jeśli chcesz dobrej wydajności pomiędzy kompilatorami).

Jedną z zalet natywnej składni wektorowej jest to, że atakując maszynę ze sprzętową kartą SIMD, użyje jej zamiast automatycznie wektoryzacji twojego bithacka lub czegoś okropnego.

Ułatwia pisanie vector -= scalaroperacji; składnia Just Works, niejawnie transmituje dla ciebie aka splatting skalar.

Zauważ też, że uint64_t*obciążenie z uint8_t array[]UB ściśle aliasinguje, więc bądź ostrożny z tym. (Zobacz także Dlaczego strli glibc musi być tak skomplikowane, aby działało szybko? Re: uczynienie binarnych SWAR rygorystycznym aliasingiem bezpiecznym w czystym C). Możesz chcieć, aby coś takiego zadeklarowało uint64_t, że możesz rzutować wskaźnik, aby uzyskać dostęp do innych obiektów, na przykład jak char*działa w ISO C / C ++.

użyj tych, aby przenieść dane uint8_t do uint64_t do użycia z innymi odpowiedziami:

// 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)));

Innym sposobem wykonania bezpiecznych dla aliasingu ładunków jest użycie znaku „ memcpya” uint64_t, który również usuwa alignof(uint64_twymóg wyrównania. Ale w ISA bez wydajnych nierównomiernych obciążeń, gcc / clang nie inline i optymalizują, memcpygdy nie mogą udowodnić, że wskaźnik jest wyrównany, co byłoby katastrofalne dla wydajności.

TL: DR: najlepiej jest zadeklarować dane jako ciuint64_t array[...] lub przeznaczyć je dynamicznie uint64_t, a najlepiejalignas(16) uint64_t array[]; , który zapewnia dostosowanie do co najmniej 8 bajtów lub 16 jeśli podasz alignas.

Ponieważ uint8_tjest prawie na pewno unsigned char*bezpieczny dostęp do bajtów uint64_tvia uint8_t*(ale nie odwrotnie w przypadku tablicy uint8_t). Dlatego w tym szczególnym przypadku, w którym występuje wąski element unsigned char, możesz ominąć problem ścisłego aliasingu, ponieważ charjest on wyjątkowy.

Przykład natywnej składni wektorowej GNU C:

GNU C rodzimych wektory są zawsze wolno alias z ich podstawowego typu (np int __attribute__((vector_size(16)))może bezpiecznie alias intale nie floatlub uint8_tczy cokolwiek innego.

#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.
}

W przypadku RISC-V bez żadnego HW SIMD, możesz użyć vector_size(8)do wyrażenia tylko szczegółowości, której możesz efektywnie użyć, i zrobić dwa razy więcej mniejszych wektorów.

Ale vector_size(8)kompiluje się bardzo głupio dla x86 zarówno z GCC, jak i clang: GCC używa bitów SWAR w rejestrach liczb całkowitych GP, clang rozpakowuje się do elementów 2-bajtowych, aby wypełnić 16-bajtowy rejestr XMM, a następnie przepakowuje. (MMX jest tak przestarzały, że GCC / clang nawet nie zawraca sobie nim głowy, przynajmniej nie dla x86-64.)

Ale z vector_size (16)( Godbolt ) otrzymujemy oczekiwany movdqa/ paddb. (Z wektorem wszystkich jedynek wygenerowanym przez pcmpeqd same,same). W -march=skylakedalszym ciągu otrzymujemy dwa oddzielne operacje XMM zamiast jednego YMM, więc niestety obecne kompilatory również nie „automatycznie wektorują” operacje wektorowe w szersze wektory: /

W przypadku AArch64 korzystanie z niego nie jest takie złe vector_size(8)( Godbolt ); ARM / AArch64 może natywnie pracować w 8 lub 16-bajtowych porcjach z rejestrami dlub q.

Prawdopodobnie chcesz vector_size(16)się faktycznie skompilować, jeśli chcesz mieć przenośną wydajność w procesorach x86, RISC-V, ARM / AArch64 i POWER . Jednak niektóre inne ISA wykonują SIMD w 64-bitowych rejestrach liczb całkowitych, jak myślę MIPS MSA.

vector_size(8)ułatwia spojrzenie na asm (dane o wartości tylko jednego rejestru): eksplorator kompilatora 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

Myślę, że to ten sam podstawowy pomysł, co inne nie zapętlone odpowiedzi; zapobiegając przenoszeniu, a następnie ustalając wynik.

To jest 5 instrukcji ALU, gorsze niż najlepsza odpowiedź, jak sądzę. Wygląda jednak na to, że opóźnienie ścieżki krytycznej to tylko 3 cykle, z dwoma łańcuchami po 2 instrukcje prowadzące do XOR. @Reinstate Monica - ζ - odpowiedź kompiluje się do 4-cyklowego łańcucha dep (dla x86). Przepływ w pętli 5-cyklowej jest wąski, ponieważ obejmuje naiwność subna ścieżce krytycznej, a pętla powoduje wąskie gardło w przypadku opóźnienia.

Jest to jednak bezużyteczne w przypadku clang. Nawet nie dodaje i nie zapisuje w tej samej kolejności, w jakiej został załadowany, więc nawet nie robi dobrego potoku oprogramowania!

# 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

Zwracam uwagę, że kod, który napisałeś, wektoryzuje, gdy zaczniesz zajmować się więcej niż jednym uint64_t.

https://godbolt.org/z/J9DRzd

Możesz upewnić się, że odejmowanie się nie przepełni, a następnie naprawić wysoki bit:

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;
}

Nie jestem pewien, czy tego właśnie chcesz, ale wykonuje 8 odejmowań równolegle względem siebie:

#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;
}

Objaśnienie: Maska bitów zaczyna się od 1 w każdej z 8-bitowych liczb. Popieramy to naszym argumentem. Gdybyśmy mieli 1 w tym miejscu, odjęliśmy 1 i musimy przestać. Odbywa się to poprzez ustawienie odpowiedniego bitu na 0 w new_mask. Gdybyśmy mieli 0, ustawiamy ją na 1 i musimy wykonać przeniesienie, więc bit pozostaje 1 i przesuwamy maskę w lewo. Lepiej sam sprawdź, czy generowanie nowej maski działa zgodnie z planem, tak myślę, ale druga opinia nie byłaby zła.

PS: Właściwie nie jestem pewien, czy sprawdzenie, czy mask_cpnie ma wartości zerowej w pętli, może spowolnić program. Bez tego kod nadal byłby poprawny (ponieważ maska ​​0 po prostu nic nie robi) i kompilatorowi łatwiej byłoby rozwinąć pętlę.

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
} 

Możesz to zrobić za pomocą operacji bitowych, korzystając z powyższego, i po prostu musisz podzielić liczbę całkowitą na 8 bitów, aby wysłać 8 razy do tej funkcji. Poniższa część została zaczerpnięta z Jak podzielić liczbę 64-bitową na osiem wartości 8-bitowych? ze mną dodając powyższą funkcję

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

Jest to poprawne C lub C ++, niezależnie od tego, jak ktoś to zauważy

Nie próbując wymyślić kodu, ale dla zmniejszenia o 1 możesz zmniejszyć o grupę 8 1, a następnie sprawdzić, czy LSB wyników „przerzuciły się”. Każdy LSB, który nie przełączył się, wskazuje, że przeniesienie nastąpiło z sąsiednich 8 bitów. Aby to obsłużyć, powinno być możliwe wypracowanie sekwencji AND / ORs / XOR bez żadnych rozgałęzień.

Skoncentruj pracę na każdym bajcie całkowicie sam, a następnie umieść go z powrotem tam, gdzie był.

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;
   }