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

77

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.

cam-biały
źródło
5
Czy muszą być 8-bitowe, czy mogą być 7-bitowe?
tadman
Muszą być 8-bitowi przykro :(
cam-biały
12
Techniki tego typu nazywane są SWAR
Harold
1
czy oczekujesz, że bajt zawierający zero zawinie do 0xff?
Alnitak

Odpowiedzi:

75

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

nanofarad
źródło
4
Potrzebuję mojego kodu do działania na maszynach RISC-V, które nie mają (jeszcze) instrukcji SIMD, nie mówiąc już o wsparciu dla MMX
cam-white
2
@ cam-white Rozumiem - to prawdopodobnie najlepsze, co możesz zrobić. Wskoczę na godbolta, by również sprawdzić, czy zespół nie ma RISC. Edit: No RISC-V wsparcie na godbolt :(
nanofaradów
7
Godbolt obsługuje RISC-V, na przykład w ten sposób (E: wygląda na to, że kompilator jest zbyt kreatywny w tworzeniu maski ..)
Harold
4
Więcej informacji o tym, w jaki sposób można zastosować sztuczkę parzystości (zwaną również „wektorem przeniesienia”) w różnych sytuacjach: emulators.com/docs/LazyOverflowDetect_Final.pdf
jpa
4
Dokonałem kolejnej edycji; Wektory macierzyste GNU C faktycznie unikają problemów ze ścisłym aliasingiem; wektor uint8_taliasu jest dozwolony dla aliasu uint8_tdanych. Wywołujący twoją funkcję (którzy muszą pobrać uint8_tdane do a uint64_t) są tymi, którzy muszą się martwić o ścisłe aliasing! Prawdopodobnie więc OP powinien po prostu deklarować / alokować tablice, uint64_tponieważ char*może aliasować cokolwiek w ISO C ++, ale nie odwrotnie.
Peter Cordes
16

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
Peter Cordes
źródło
13

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

https://godbolt.org/z/J9DRzd

robthebloke
źródło
1
Czy możesz wyjaśnić lub podać odniesienie do tego, co się tam dzieje? To wydaje się dość interesujące.
n314159
2
Próbowałem to zrobić bez instrukcji SIMD, ale mimo wszystko to ciekawe :)
cam-white
8
Z drugiej strony ten kod SIMD jest okropny. Kompilator zupełnie nie zrozumiał, co się tutaj dzieje. E: to przykład „tego wyraźnie dokonał kompilator, ponieważ żaden człowiek nie byłby tak głupi”
Harold
1
@PeterCordes: Myślałem bardziej zgodnie z __vector_loop(index, start, past, pad)konstruktem, który implementacja mogłaby traktować jako for(index=start; index<past; index++)[co oznacza, że ​​każda implementacja może przetwarzać kod przy użyciu go, jedynie poprzez zdefiniowanie makra], ale która miałaby luźniejszą semantykę, aby zaprosić kompilator do przetwarzania rzeczy w dowolna potęga wielkości dwóch porcji do pad, przedłużając początek w dół i kończąc w górę, jeśli nie są one wielokrotnościami wielkości porcji. Skutki uboczne w obrębie każdego kawałka byłyby nieistotne, a jeśli breakwystąpi w pętli, inne powtórzenia ...
supercat
1
@PeterCordes: Chociaż restrictjest pomocny (i byłby bardziej pomocny, gdyby Standard rozpoznał koncepcję „przynajmniej potencjalnie opartą na”, a następnie zdefiniował „oparty na” i „przynajmniej potencjalnie oparty na” bezpośrednio, bez głupich i niewykonalnych przypadków narożnych) moja propozycja pozwoliłaby również kompilatorowi na wykonanie większej liczby pętli niż jest to wymagane - co znacznie uprościłoby wektoryzację, ale dla których Standard nie przewiduje.
supercat
11

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;
}
Falk Hüffner
źródło
Myślę, że to działa dla wszystkich 256 możliwych wartości bajtu; Położyłem go na Godbolt (z clangiem RISC-V) godbolt.org/z/DGL9aq, aby przyjrzeć się wynikom stałej propagacji dla różnych danych wejściowych, takich jak 0x0, 0x7f, 0x80 i 0xff (przesunięty na środek liczby). Wygląda dobrze. Myślę, że najwyższa odpowiedź sprowadza się do tego samego, ale wyjaśnia to w bardziej skomplikowany sposób.
Peter Cordes
Tutaj kompilatory mogłyby lepiej konstruować stałe w rejestrach. clang spędza wiele instrukcji konstruując splat(0x01)isplat(0x80) zamiast pobierać jedną z drugiej z przesunięciem. Nawet pisanie go w ten sposób w źródłowym godbolt.org/z/6y9v-u nie powstrzymuje kompilatora przed tworzeniem lepszego kodu; po prostu dokonuje stałej propagacji.
Peter Cordes
Zastanawiam się, dlaczego nie tylko ładuje stałą z pamięci; to właśnie robią kompilatory Alpha (podobna architektura).
Falk Hüffner
Tak robi GCC dla RISC-V stałe obciążenia z pamięci. Wygląda na to, że clang wymaga dostrajania, chyba że spodziewane są błędy w pamięci podręcznej danych i są one drogie w porównaniu z przepływnością instrukcji. (Ta równowaga z pewnością mogła ulec zmianie od wersji Alpha i przypuszczalnie różne implementacje RISC-V są różne. Kompilatory mogłyby również działać znacznie lepiej, gdyby zdały sobie sprawę, że jest to powtarzalny wzorzec, który można przesunąć / LUB rozszerzyć po rozpoczęciu od jednego LUI / add dla 20 + 12 = 32 bity natychmiastowych danych. Wzorzec bitowy AArch64 może nawet wykorzystać je jako bezpośrednie dla AND / OR / XOR, smart decode vs. wybór gęstości)
Peter Cordes
Dodano odpowiedź pokazującą rodzimy wektor SWAR GCC dla RISC-V
Peter Cordes
7

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

n314159
źródło
fornie będzie działać równolegle, czy jesteś mylony for_each?
LTPCGO
3
@LTPCGO Nie, nie jest moim zamiarem zrównoleglenie tego dla pętli, to faktycznie złamałoby algorytm. Ale ten kod działa na różnych liczbach całkowitych 8-bitowych w liczbach całkowitych 64-bitowych równolegle, tj. Wszystkie 8 odejmowania są wykonywane jednocześnie, ale wymagają do 8 kroków.
n314159
Zdaję sobie sprawę, że to, o co prosiłem, mogło być trochę nierozsądne, ale to było bardzo blisko tego, czego potrzebowałem dzięki :)
cam-white
4
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

LTPCGO
źródło
5
Nie jest to jednak równoznaczne z pracą, co jest pytaniem OP.
nickelpro
Tak, @nickelpro ma rację, spowoduje to odejmowanie jeden po drugim, chciałbym odjąć wszystkie 8-bitowe liczby całkowite w tym samym czasie. Doceniam odpowiedź, dziękuję stary
cam-biały
2
@nickelpro, kiedy zacząłem odpowiedź, nie dokonano edycji, w której podano równoległą część pytania, więc nie zauważyłem jej przed przesłaniem, odejdzie na wypadek, gdyby był przydatny dla innych, ponieważ przynajmniej odpowiada część do wykonywania operacji bitowych i można by ją uruchomić równolegle, wykorzystując for_each(std::execution::par_unseq,...zamiast whiles
LTPCGO
2
To moje złe, zadałem pytanie, a potem zdałem sobie sprawę, że nie powiedziałem, że musi być równolegle, więc edytowane
cam-biały
2

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

Hot Licks
źródło
To może zadziałać, ale rozważ przypadek, w którym przeniesienie rozprzestrzenia się przez całą grupę 8 bitów do drugiej. Strategia w dobrych odpowiedziach (ustawianie MSB lub czegoś w pierwszej kolejności), aby zapewnić, że przenoszenie się nie rozprzestrzenia, jest prawdopodobnie co najmniej tak wydajna, jak to mogłoby być. Bieżącym celem do pokonania (tj. Dobre nie zapętlone odpowiedzi bez rozgałęzień) jest 5 instrukcji ALU RISC-V asm z równoległością na poziomie instrukcji, co sprawia, że ​​ścieżka krytyczna ma tylko 3 cykle i wykorzystuje dwie stałe 64-bitowe.
Peter Cordes
0

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;
   }
nonock
źródło