Mengurangi integer 8-bit yang dikemas dalam integer 64-bit dengan 1 secara paralel, SWAR tanpa SIMD perangkat keras

Jika saya memiliki integer 64-bit yang saya tafsirkan sebagai array integer 8-bit yang dikemas dengan 8 elemen. Saya perlu mengurangi konstanta 1dari setiap integer yang dikemas sambil menangani overflow tanpa hasil dari satu elemen yang mempengaruhi hasil dari elemen lain.

Saya memiliki kode ini saat ini dan berfungsi tetapi saya membutuhkan solusi yang melakukan pengurangan setiap integer 8-bit yang dikemas secara paralel dan tidak membuat akses memori. Pada x86 saya bisa menggunakan instruksi SIMD seperti psubbitu mengurangi bilangan bulat 8-bit secara paralel tetapi platform yang saya koding tidak mendukung instruksi SIMD. (RISC-V dalam hal ini).

Jadi saya mencoba melakukan SWAR (SIMD dalam register) untuk secara manual membatalkan propagasi carry antara byte a uint64_t, melakukan sesuatu yang setara dengan ini:

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

Saya pikir Anda bisa melakukan ini dengan operator bitwise tapi saya tidak yakin. Saya mencari solusi yang tidak menggunakan instruksi SIMD. Saya mencari solusi dalam C atau C ++ yang cukup portabel atau hanya teori di baliknya sehingga saya dapat mengimplementasikan solusi saya sendiri.

Jika Anda memiliki CPU dengan instruksi SIMD yang efisien, SSE / MMX paddb( _mm_add_epi8) juga dapat digunakan.Jawaban Peter Cordes juga menjelaskan sintaks vektor GNU C (gcc / clang), dan keamanan untuk UB alias ketat. Saya sangat menyarankan untuk meninjau jawaban itu juga.

Melakukannya sendiri dengan uint64_tsepenuhnya portabel, tetapi masih membutuhkan kehati-hatian untuk menghindari masalah penyelarasan dan UB yang ketat saat mengakses uint8_tarray dengan a uint64_t*. Anda meninggalkan bagian itu dari pertanyaan dengan memulai dengan data Anda di uint64_tsudah, tetapi untuk GNU C amay_alias typedef memecahkan masalah (lihat jawaban Peter untuk itu atau memcpy).

Kalau tidak, Anda dapat mengalokasikan / mendeklarasikan data Anda sebagai uint64_tdan mengaksesnya melalui uint8_t*saat Anda ingin masing-masing byte. unsigned char*diizinkan untuk alias apa pun sehingga menghindari masalah untuk kasus spesifik elemen 8-bit. (Jika uint8_tada sama sekali, mungkin aman untuk menganggapnya sebagai unsigned char.)

Perhatikan bahwa ini adalah perubahan dari algoritma yang salah sebelumnya (lihat riwayat revisi).

Ini dimungkinkan tanpa perulangan untuk pengurangan sewenang-wenang, dan menjadi lebih efisien untuk konstanta yang dikenal 1 di setiap byte. Trik utamanya adalah mencegah carry-out dari setiap byte dengan mengatur bit tinggi, lalu mengoreksi hasil pengurangan.

Kami akan sedikit mengoptimalkan teknik pengurangan yang diberikan di sini . Mereka mendefinisikan:

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

dengan Hdidefinisikan sebagai 0x8080808080808080U(yaitu MSBs dari setiap integer yang dikemas). Untuk penurunan, yadalah0x0101010101010101U .

Kita tahu bahwa ysemua MSB-nya sudah jelas, jadi kita bisa melewati salah satu langkah mask (yaitu y & ~Hsama seperti ydalam kasus kami). Perhitungan dilanjutkan sebagai berikut:

1. Kami menetapkan MSB dari setiap komponen x MSB menjadi 1, sehingga pinjaman tidak dapat disebarkan melewati MSB ke komponen berikutnya. Sebut ini input yang disesuaikan.
2. Kami mengurangi 1 dari setiap komponen, dengan mengurangi 0x01010101010101 dari input yang dikoreksi. Ini tidak menyebabkan pinjaman antar-komponen berkat langkah 1. Sebut ini hasil yang disesuaikan.
3. Kita sekarang perlu memperbaiki MSB hasilnya. Kami xor output yang disesuaikan dengan MSB terbalik dari input asli untuk menyelesaikan memperbaiki hasil.

Operasi dapat ditulis sebagai:

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

Lebih disukai, ini digarisbawahi oleh kompiler (gunakan arahan kompiler untuk memaksakan ini), atau ekspresi ditulis sebaris sebagai bagian dari fungsi lain.

Testcases:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Detail kinerja

Inilah rakitan x86_64 untuk satu pemanggilan fungsi. Untuk kinerja yang lebih baik, harus digarisbawahi dengan harapan bahwa konstanta dapat hidup dalam register selama mungkin. Dalam loop ketat di mana konstanta hidup dalam register, penurunan aktual membutuhkan lima instruksi: atau + tidak + dan + tambahkan + xor setelah optimasi. Saya tidak melihat alternatif yang akan mengalahkan optimasi kompiler.

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

Dengan beberapa pengujian IACA dari cuplikan berikut:

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

kita dapat menunjukkan bahwa pada mesin Skylake, melakukan penurunan, xor, dan bandingkan + lompatan dapat dilakukan pada hanya di bawah 5 siklus per iterasi:

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

(Tentu saja, pada x86-64 Anda baru saja memuat atau movqmasuk ke reg XMM paddb, jadi mungkin lebih menarik untuk melihat bagaimana kompilasi untuk ISA seperti RISC-V.)

Untuk RISC-V Anda mungkin menggunakan GCC / dentang.

Fakta menyenangkan: GCC mengetahui beberapa trik bithack SWAR ini (diperlihatkan dalam jawaban lain) dan dapat menggunakannya untuk Anda ketika menyusun kode dengan vektor asli GNU C untuk target tanpa instruksi SIMD perangkat keras. (Tapi dentang untuk RISC-V akan secara naif membuka gulungannya ke operasi skalar, jadi Anda harus melakukannya sendiri jika Anda ingin kinerja yang baik di seluruh kompiler).

Salah satu keuntungan sintaksis vektor asli adalah bahwa ketika menargetkan mesin dengan SIMD perangkat keras, ia akan menggunakannya daripada secara otomatis membuat vektor bithack Anda atau sesuatu yang mengerikan seperti itu.

Ini membuatnya mudah untuk menulis vector -= scalaroperasi; sintaks Just Works, menyiarkan secara implisit alias membentangkan skalar untuk Anda.

Perhatikan juga bahwa uint64_t*beban dari uint8_t array[]UB adalah aliasing yang ketat, jadi berhati-hatilah dengan itu. (Lihat juga Mengapa strib glibc perlu sangat rumit untuk berjalan cepat? Re: membuat SWAR bithacks ketat-alias aman dalam C murni). Anda mungkin ingin sesuatu seperti ini mendeklarasikan uint64_tbahwa Anda dapat mengarahkan penunjuk untuk mengakses objek lain, seperti caranyachar* kerjanya di ISO C / C ++.

gunakan ini untuk mendapatkan data uint8_t menjadi uint64_t untuk digunakan dengan jawaban lain:

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

Cara lain untuk melakukan aliasing-safe load adalah dengan memcpymenjadi uint64_t, yang juga menghilangkan alignof(uint64_t) persyaratan perataan. Tetapi pada ISA tanpa beban yang tidak selaras efisien, gcc / dentang tidak sejajar dan dioptimalkan memcpyketika mereka tidak dapat membuktikan bahwa pointer selaras, yang akan menjadi bencana bagi kinerja.

TL: DR: taruhan terbaik Anda adalah untuk mendeklarasikan data Anda sebagaiuint64_t array[...] atau mengalokasikannya secara dinamis uint64_t, atau lebih disukaialignas(16) uint64_t array[]; Itu memastikan keselarasan ke setidaknya 8 byte, atau 16 jika Anda menentukanalignas .

Karena uint8_thampir pasti unsigned char*, aman untuk mengakses byte uint64_tvia uint8_t*(tetapi tidak sebaliknya untuk array uint8_t). Jadi untuk kasus khusus di mana jenis elemen sempit ini unsigned char, Anda dapat menghindari masalah aliasing ketat karena charkhusus.

Contoh sintaks vektor asli GNU C:

GNU C vektor asli selalu diizinkan untuk alias dengan jenis yang mendasarinya (misalnya int __attribute__((vector_size(16)))bisa dengan aman alias inttetapi tidak floatatau uint8_tatau apa pun.

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

Untuk RISC-V tanpa SIM HW, Anda dapat menggunakannya vector_size(8) untuk mengekspresikan granularity yang dapat Anda gunakan secara efisien, dan melakukan dua kali lebih banyak vektor yang lebih kecil.

Tetapi vector_size(8)mengkompilasi dengan sangat bodoh untuk x86 dengan GCC dan dentang: GCC menggunakan bithacks SWAR dalam register GP-integer, dentang membongkar ke elemen 2-byte untuk mengisi register XMM 16-byte kemudian mengemasnya kembali. (MMX sangat usang sehingga GCC / dentang bahkan tidak repot menggunakannya, setidaknya tidak untuk x86-64.)

Tetapi dengan vector_size (16)( Godbolt ) kita mendapatkan yang diharapkan movdqa/ paddb. (Dengan semua vektor yang dihasilkan oleh pcmpeqd same,same). Dengan-march=skylake kita masih mendapatkan dua ops XMM terpisah dan bukan satu YMM, jadi sayangnya kompiler saat ini juga tidak "auto-vectorize" ops vektor ke dalam vektor yang lebih luas: /

Untuk AArch64, itu tidak terlalu buruk untuk digunakan vector_size(8)( Godbolt ); ARM / AArch64 asli dapat bekerja dalam potongan 8 atau 16 byte dengan datauq register.

Jadi Anda mungkin ingin vector_size(16)mengompilasi jika Anda ingin kinerja portabel di x86, RISC-V, ARM / AArch64, dan POWER . Namun, beberapa SPA lain melakukan SIMD dalam register integer 64-bit, seperti MIPS MSA.

vector_size(8)membuatnya lebih mudah untuk melihat asm (nilai data hanya satu register): Godbolt compiler explorer

# 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

Saya pikir itu ide dasar yang sama dengan jawaban non-looping lainnya; mencegah carry kemudian memperbaiki hasilnya.

Ini adalah 5 instruksi ALU, lebih buruk daripada jawaban atas yang saya pikir. Tapi sepertinya latensi jalur kritis hanya 3 siklus, dengan dua rantai 2 instruksi masing-masing mengarah ke XOR. @Reinstate Monica - jawaban comp - mengkompilasi ke rantai dep 4 siklus (untuk x86). Throughput loop 5 siklus dihambat oleh juga termasuk naifsub di jalur kritis, dan loop tidak bottleneck pada latensi.

Namun, ini tidak berguna dengan dentang. Ia bahkan tidak menambah dan menyimpan dalam urutan yang sama saat dimuat sehingga bahkan tidak melakukan pipelining perangkat lunak yang baik!

# 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

Saya akan menunjukkan bahwa kode yang Anda tulis benar-benar membuat vektor ketika Anda mulai berurusan dengan lebih dari satu uint64_t tunggal.

https://godbolt.org/z/J9DRzd

Anda dapat memastikan pengurangan tidak meluap dan kemudian memperbaiki bit tinggi:

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

Tidak yakin apakah ini yang Anda inginkan tetapi melakukan 8 pengurangan secara paralel satu sama lain:

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

Penjelasan: Bitmask dimulai dengan 1 di masing-masing angka 8-bit. Kami mengatasinya dengan argumen kami. Jika kita memiliki 1 di tempat ini, kita mengurangi 1 dan harus berhenti. Ini dilakukan dengan mengatur bit yang sesuai ke 0 di new_mask. Jika kita memiliki 0, kita mengaturnya ke 1 dan harus melakukan carry, jadi bitnya tetap 1 dan kita menggeser topeng ke kiri. Anda sebaiknya memeriksa sendiri apakah pembuatan topeng baru berfungsi sebagaimana dimaksud, saya kira begitu, tetapi pendapat kedua tidak akan buruk.

PS: Saya benar-benar tidak yakin jika cek mask_cptidak null dalam loop dapat memperlambat program. Tanpa itu, kode akan tetap benar (karena topeng 0 tidak melakukan apa-apa) dan akan lebih mudah bagi kompiler untuk melakukan loop membuka gulungan.

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
} 

Anda dapat melakukannya dengan operasi bitwise menggunakan di atas, dan Anda hanya perlu membagi integer Anda menjadi 8 bagian bit untuk mengirim 8 kali ke fungsi ini. Bagian berikut ini diambil dari Cara membagi angka 64-bit menjadi delapan nilai 8-bit?dengan saya menambahkan fungsi di atas

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

Ini valid C atau C ++ terlepas dari bagaimana seseorang menemukan ini

Tidak akan mencoba untuk membuat kode, tetapi untuk pengurangan dengan 1 Anda dapat mengurangi dengan kelompok 8 1s dan kemudian periksa untuk memastikan bahwa LSB dari hasil telah "terbalik". Setiap LSB yang belum diaktifkan menunjukkan bahwa carry terjadi dari 8 bit yang berdekatan. Seharusnya dimungkinkan untuk menentukan urutan ANDs / ORs / XOR untuk menangani hal ini, tanpa cabang apa pun.

Fokus bekerja pada setiap byte sepenuhnya sendiri, lalu taruh kembali di tempatnya.

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