manera eficiente de convertir índices de dispersión en índices de reunión?

Question

Estoy tratando de escribir una compactación de flujo (tomar una matriz y deshacerse de los elementos vacíos) con SIMD intrínsecos. Cada iteración del ciclo procesa 8 elementos a la vez (ancho SIMD).

Con SSE intrínsecamente, puedo hacer esto bastante eficientemente con _mm_shuffle_epi8(), que hace una búsqueda de tabla de 16 entradas (reunir en terminología de computación paralela). Los índices de mezcla se precalculan y se mira con una máscara 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]; 
} 

Mi problema es ahora quisiera aplicar esto para Altivec SIMD también (no pregunte por qué - equivocada decisión de negocios). Altivec no tiene un equivalente para _mm_movemask_epi8(), un ingrediente crítico. Por lo tanto, voy a tener que encontrar una manera de cualquiera

1. _mm_movemask_epi8 emular() - parece caro, varios turnos y OR

2. generar directamente los índices de reproducción aleatoria de manera eficiente -

saber , index voy a ser el índice del i-ésimo elemento válido en los datos no comparados

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 

Es simple hacer esto en serie, pero necesito que sea paralelo (SIMD). Parece fácil generar índices de dispersión con una suma de prefijo, pero como ni AltiVec ni SSE tienen una instrucción de dispersión, en su lugar, necesito recopilar índices. Los índices de recopilación son la función inversa de los índices de dispersión, pero ¿cómo puede obtenerse en paralelo? Sé que en los días pioneros de la programación de GPU, converting scatters to gathers era una técnica común, pero ninguno de los 2 métodos descritos parece práctico.

Quizás si no insiste en que la compactación conserva el orden de los elementos, ¿permitirá una implementación más eficiente? Puedo renunciar a eso.

Answer 1

Si desea emular _mm_movemask_epi8 y sólo tiene una máscara de escalar 8 bits de 8 elementos de bytes a continuación, puede hacer algo como esto utilizando 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; 
} 

Esto es 5 instrucciones AltiVec frente a 1 en SSE. Es posible que pueda perder el vec_splat y bajarlo a 4.