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

Con intrínsecos SSE, puedo hacer esto de manera bastante eficiente con _mm_shuffle_epi8 (), que realiza una búsqueda en la tabla de 16 entradas (recopilar en terminología de computación paralela). Los índices aleatorios se calculan previamente y se buscan 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 ahora es que me gustaría implementar esto también para Altivec SIMD (no pregunte por qué, decisión comercial equivocada). Altivec no tiene un equivalente para _mm_movemask_epi8 (), un ingrediente crítico. Por lo tanto, tendré que encontrar una forma de

emulate _mm_movemask_epi8 () - parece caro, varios turnos y quirófanos

generar directamente los índices aleatorios de manera eficiente -

namely, index i será el índice del elemento i-ésimo válido en los datos no compactados

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, necesito recopilar índices en su lugar. Los índices de recopilación son la función inversa de los índices de dispersión, pero ¿cómo se puede obtener en paralelo? Sé que en los días pioneros de la programación de GPU,convertir dispersiones a recolecta 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 preserva el orden de los elementos permitirá una implementación más eficiente? Puedo renunciar a eso.