QWORD shuffle secvențiale 7-biți la alinierea byte cu SIMD SSE ... AVX

Aș dori să știu dacă următoarele sunt posibile în oricare dintre familiile SIMD de instrucțiuni.

Am o intrare qword cu 63 biți semnificativi (niciodată negativi). Fiecare secvențial 7 biți, pornind de la LSB, este aliniat la un octet, cu o căptușeală stângă de 1 (cu excepția celui mai semnificativ octet diferit de zero). Pentru a ilustra, voi folosi scrisori din motive de claritate.

Rezultatul este numai octeții semnificativi, deci 0 - 9 în dimensiune, care este convertit într-o matrice octet.

In:         0|kjihgfe|dcbaZYX|WVUTSRQ|PONMLKJ|IHGFEDC|BAzyxwv|utsrqpo|nmlkjih|gfedcba
Out: 0kjihgfe|1dcbaZYX|1WVUTSRQ|1PONMLKJ|1IHGFEDC|1BAzyxwv|1utsrqpo|1nmlkjih|1gfedcba

Dimensiune = 9

In:  00|nmlkjih|gfedcba
Out: |0nmlkjih|1gfedcba

Dimensiunea = 2

Înțeleg că umplutura este separată. Alinierea în mișcare este întrebarea mea. Este posibil?

EDIT 2

Aici este codul meu actualizat. Beneficiază de o durată de susținere de 46 M/sec pentru introducerea în lungime aleatorie pe un singur fir Core 2 Duo 2 GHz, 64 biți.

private static int DecodeIS8(long j, ref byte[] result)
{
    if (j <= 0)
    {
        return 0;
    }

    int size;

   //neater code: gives something to break out of
    while (true)
    {
        result[0] = (byte)((j & 0x7F) | 0x80);
        size = 0;
        j >>= 7;

        if (j == 0) break;

        result[1] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[2] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[3] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[4] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[5] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[6] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[7] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[8] = (byte)j;

        return 9;
    }

    result[size] ^= 0x80;

    return size + 1;
}
3
Este cu siguranță posibil, dar va fi urât. Veți avea nevoie de o grămadă de operațiuni de schimbare și mascare. Esti 100% sigur ca aceasta este o strangere de performanta?
adăugat autor Paul R, sursa
Singura modalitate de a fi sigur este codarea unei versiuni scalare și a unei versiuni SIMD și compararea acestora. Dacă nu faceți alte operațiuni SIMD împreună cu această despachetare, atunci bănuiți că nu veți câștiga prea mult.
adăugat autor Paul R, sursa
Ce CPU și compilator folosiți? S-ar putea să găsiți că un compilator decent (de exemplu, Intel ICC sau chiar doar gcc) vă va oferi mai multă ameliorare decât să mergeți la SIMD pentru acest lucru.
adăugat autor Paul R, sursa
Păcat că nu faci asta pe POWER/PowerPC - AltiVec are 128 biți. Dar cred că ar putea fi încă posibilă cu SSE în mai puține instrucțiuni decât în ​​codul dvs. scalar - noroc, oricum!
adăugat autor Paul R, sursa
Nu ai menționat dacă faci alte operații SIMD pe aceste date. Dacă încărcați doar datele stocate din memorie și stocați datele neambalate în memorie, este puțin probabil ca SIMD să vă ajute. Voi începe prin optimizarea cât mai mult posibil a codului scalar existent înainte de a examina SIMD.
adăugat autor Paul R, sursa
Se pare că în jur de 50 de instrucțiuni aritmetice/logice, astfel încât să fie în concordanță cu transferul pe care îl obțineți.
adăugat autor Paul R, sursa
Asta pare un pic lent - în jur de 50 de ceasuri pe decod - mă așteptam ca codul scalar să poată fi optimizat pentru a funcționa considerabil mai repede decât asta.
adăugat autor Paul R, sursa
OK - presupunem că costul de eroare a ramificației atunci când lungimea de intrare este aleatorie ar depăși procesarea suplimentară, dar evident nu.
adăugat autor Paul R, sursa
Sugestie: Aș lua codul în întrebarea dvs. de mai sus ca punct de plecare, scap de toate lucrurile de returnare timpurie și condiționalități (adică a face it branchless) - procesul de ieșire 9 octeți de fiecare dată fără sucursale și apoi scrie doar numărul corect de octeți la sfârșit.
adăugat autor Paul R, sursa
E o întrebare de cercetare. Este un cod care trebuie să fie cât mai rapid posibil, deoarece o mulțime de alte coduri îl numește. Cu alte cuvinte, este foarte, foarte important. Întrebarea este, va fi mai rapid?
adăugat autor IamIC, sursa
Având în vedere costul aferent metodei, aș spune că da. Nu cred că o să strâng mai mult din asta ... dacă AVX2 nu are o soluție. Se pare că ar fi posibil. Multumesc Paul :)
adăugat autor IamIC, sursa
Ți-am luat sugestia și i-am pus în aplicare într-un mod care a grăbit lucrurile. Am postat actualizarea.
adăugat autor IamIC, sursa
Pentru intrările de lungime pur aleatoare (1 - 8 octeți semnificativi), sugeratul dvs. este doar puțin mai lent decât originalul. Pentru numere mari, ar fi mai rapid, iar pentru numere mici, ar fi mai lent. În C, s-ar accelera din cauza comenzii bit-scan-left pentru a obține MSB. În acest caz, ar putea fi câștigătorul.
adăugat autor IamIC, sursa
Paul, mulțumesc pentru sugestie, pe care o voi încerca, dar vă pot garanta că va fi mai lent din același motiv pentru care masina de împușcare a biților este mai lentă: ramificarea permite procesorului să proceseze numai numărul necesar de octeți. Vă voi spune cum se dovedește. Multumesc pentru ajutor :)
adăugat autor IamIC, sursa
De asemenea, considerați că trebuie să amestecați rezultatul în matricea octeților. Probabil că a luat jumătate din timp.
adăugat autor IamIC, sursa
Petrecut 1.5 ore scrise ca o operație binară hiper-complexă. Este o înțelegere lentă prin comparație. 50 de ceasuri nu este așa de rău dacă vă gândiți la câte operațiuni reale au loc.
adăugat autor IamIC, sursa
Lucrez la asta ;)
adăugat autor IamIC, sursa
@PaulR, nu există alte operații SIMD pe date. Aceasta este o funcție pur scalară. Cred că l-am optimizat cât pot. Sunt aproape 41 M decodificați/sec de intrări de lungime pur aleatoare. Când codul era în linie, era 55 M.
adăugat autor IamIC, sursa
Această pagină ( software.intel.com/en-us/blogs/2011/06/13/… ) indică "multe permute multe", dar nu spune prea multe despre asta.
adăugat autor IamIC, sursa
CPU = i7, GCC (pentru moment). Nu sunt sigur că compilatorul va face mult cu codul pe care l-am postat.
adăugat autor IamIC, sursa
O să trebuiască să o testez. SIMD este foarte nou pentru mine, motiv pentru care nu am încercat deja. Această sarcină arată ca ceva pe care l-ar folosi SIMD, așa că am postat întrebarea aici pentru a obține opinia celor care au experiență în acest domeniu.
adăugat autor IamIC, sursa

1 răspunsuri

Da, este posibil să folosiți instrucțiunea pmullw MMX/SSE (funcție intrinsecă: _mm_mullo_pi16 ) pentru a face schimburi pe elemente.

Ideea de bază este să extrageți elemente alternante pe 7 biți cu o instrucțiune AND și să efectuați codul pmullw pentru a muta elementele în loc. Acest lucru va duce la îndeplinirea sarcinii pentru jumătate din elemente, astfel că procesul va trebui repetat cu câteva schimbări suplimentare.

#include 
#include 
#include 

__m64 f(__m64 input) {
    static const __m64 mask = (__m64) 0xfe03f80fe03f80UL;
    static const __m64 multiplier = (__m64) 0x0080002000080002UL;

    __m64 t0 = _mm_and_si64 (input, mask);
    __m64 t1 = _mm_and_si64 (_mm_srli_si64 (input, 7), mask);

    t0 = _mm_mullo_pi16 (t0, multiplier);
    t1 = _mm_mullo_pi16 (t1, multiplier);

    __m64 res =  _mm_or_si64 (t0, _mm_slli_si64 (t1, 8));
    /* set most significant bits, except for in most significant byte */
    return _mm_or_si64 (res, (__m64) 0x0080808080808080UL);
}

int main(int argc, char *argv[])
{
    int i;
    typedef union {
            __m64 m64;
            unsigned char _8x8[8];
    } type_t;

    /* 0x7f7e7c7870608080 = {127, 63, 31, 15, 7, 3, 2, 1, 0} */
    type_t res0 = { .m64 = f((__m64) 0x7f7e7c7870608080UL) };

    for (i = 0; i < 8; i++) {
            printf("%3u ", res0._8x8[i]);
    }
    puts("");

    return 0;
}

Masca extrage elemente alternante pe 7 biți. multiplicatorul este o constantă care ne permite să specificăm schimbările pe elemente. Este derivat din analizarea intrării mascate:

00000000|dcbaZYX0|000000PO|NMLKJ000|0000BAzy|xwv00000|00nmlkji|h0000000

și realizând acest lucru

00000000|dcbaZYX0 needs to be shifted by 7 (or multiplied by 2^7, 128, 0x0080)
000000PO|NMLKJ000 needs to be shifted by 5 (or multiplied by 2^5,  32, 0x0020)
0000BAzy|xwv00000 needs to be shifted by 3 (or multiplied by 2^3,   8, 0x0008)
00nmlkji|h0000000 needs to be shifted by 1 (or multiplied by 2^1,   2, 0x0002)

Această funcție scrie 8 octeți la un moment dat (în loc de 9-octeți, cele 9 elemente pe 7 biți le-ar despacheta), deci va trebui să avansați indicatorul de sursă cu numai 7 octeți după fiecare repetare. Din acest motiv, o conversie la SSE2 este un pic mai complicată.

Nu cred că este posibil să folosiți o altă mască și multiplicator pentru t1 pentru a evita schimbările, deoarece elementele t1 vor trece peste limitele de 16 biți, care va împiedica lucrul pmullw . Dar este posibil să se optimizeze cumva.

Nu am evaluat acest lucru, dar bănuiesc că este mult mai rapid decât versiunea scalară. Dacă faceți o evaluare, trimiteți rezultatele. Aș fi foarte interesat să le văd.

În ansamblu, algoritmul are 2 treceri, 2 oră, 2 șiruri și două multiplicări (și câteva mișcări) pentru a genera 8 octeți.

6
adăugat
Foarte frumos! Știam că este posibil. Mulțumesc. Cred că un bsl este necesar pentru a detecta MSB, astfel încât să setați corect biții înalți pentru fiecare octet.
adăugat autor IamIC, sursa
Puteți salva un insn folosind un cod PANDN pentru a inversa masca, în loc să schimbați datele pentru a alinia cu masca și apoi înapoi (cu un bit mai mult)? Sau poate doar prin a avea două măști diferite și doi multiplicatori diferiți. (Poate că merită doar dacă buclă este foarte fierbinte și/sau rulează pe tampoane mari.) Idee foarte bună de a combina intrarea în două jumătăți, permițând mul să schimbe lucrurile fără a păși pe elementele vecine.
adăugat autor Peter Cordes, sursa