moyen efficace de convertir les indices de dispersion en indices de collecte?

Question

J'essaye d'écrire un compactage de flux (prendre un tableau et me débarrasser des éléments vides) avec des intrinsèques SIMD. Chaque itération de la boucle traite 8 éléments à la fois (largeur SIMD).

Avec l'intrinsèque SSE, je peux le faire assez efficacement avec _mm_shuffle_epi8(), qui fait une recherche de table de 16 entrées (rassembler dans la terminologie de calcul parallèle). Les index de shuffle sont précalculés et recherchés avec un masque de bits.

for (i = 0; i < n; i += 8) 
{ 
    v8n_Data = _mm_load_si128(&data[i]); 
    mask = _mm_movemask_epi8(&is_valid[i]) & 0xff;  // is_valid is byte array 
    v8n_Compacted = _mm_shuffle_epi8(v16n_ShuffleIndices[mask]); 
    _mm_storeu_si128(&compacted[count], v8n_Compacted); 

    count += bitCount[mask]; 
} 

Mon problème est maintenant je voudrais mettre en œuvre ce pour SIMD AltiVec aussi (ne demandez pas pourquoi - décision d'affaires peu judicieux). Altivec n'a pas d'équivalent pour _mm_movemask_epi8(), un ingrédient critique. Alors, je vais devoir trouver un moyen soit

1. Emuler _mm_movemask_epi8() - semble cher, plusieurs quarts de travail et ORs

2. générer directement les indices de lecture aléatoire efficacement -

savoir , l'indice i sera l'indice du ième élément valable dans les données non compactées

element_valid: 0 0 1 0 1 0 0 1 0 
gather_indices: x x x x x x 6 4 1 
scatter_indices: 3 3 2 2 1 1 1 0 0 

C'est simple de faire ceci en série, mais j'ai besoin qu'il soit parallèle (SIMD). Il semble facile de générer des indices de dispersion avec une somme de préfixes, mais comme AltiVec et SSE n'ont pas d'instruction scatter, j'ai besoin de rassembler des indices. Les indices de regroupement sont la fonction inverse des indices de dispersion, mais comment cela peut-il être obtenu en parallèle? Je sais que dans les jours pionniers de la programmation GPU, converting scatters to gathers était une technique courante, mais aucune de ces 2 méthodes décrites semblent pratiques. Peut-être que si l'on n'insiste pas sur le fait que le compactage préserve l'ordre des éléments, l'implémentation sera peut-être plus efficace? Je peux abandonner ça.

Answer 1

Si vous voulez imiter _mm_movemask_epi8 et vous avez juste besoin d'un masque scalaire 8 bits de 8 éléments d'octets, alors vous pouvez faire quelque chose comme ceci en utilisant AltiVec:

#include <stdio.h> 

int main(void) 
{ 
    const vector unsigned char vShift = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0 }; 
              // constant shift vector 

    vector unsigned char isValid = { 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 
              // sample input 

    vector unsigned char v1 = vec_sl(isValid, vShift); 
              // shift input values 
    vector unsigned int v2 = vec_sum4s(v1, (vector unsigned int)(0)); 
    vector signed int v3 = vec_sum2s((vector signed int)v2, (vector signed int)(0)); 
              // sum shifted values 
    vector signed int v4 = vec_splat(v3, 1); 
    unsigned int mask __attribute__ ((aligned(16))); 
    vec_ste((vector unsigned int)v4, 0, &mask); 
              // store sum in scalar 

    printf("v1 = %vu\n", v1); 
    printf("v2 = %#vlx\n", v2); 
    printf("v3 = %#vlx\n", v3); 
    printf("v4 = %#vlx\n", v4); 
    printf("mask = %#x\n", mask); 

    return 0; 
} 

C'est 5 instructions AltiVec par rapport à 1 SSE. Vous pourriez être en mesure de perdre le vec_splat et le descendre à 4.