Эффективный способ преобразования индексов рассеяния в индексы сбора?

Question

Я пытаюсь написать сжатие потока (взять массив и избавиться от пустых элементов) с внутренними SIMD. Каждая итерация цикла обрабатывает 8 элементов одновременно (ширина SIMD).

Благодаря встроенным функциям SSE я могу сделать это довольно эффективно с помощью функции _mm_shuffle_epi8 (), которая выполняет поиск в таблице из 16 записей (собрана в терминологии параллельных вычислений). Индексы тасования предварительно вычисляются и отображаются с немного битовой маской.

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

Моя проблема в том, что теперь я хотел бы реализовать это и для Altivec SIMD (не спрашивайте, почему - ошибочное деловое решение). У Altivec нет эквивалента для _mm_movemask_epi8 (), критического ингредиента. Итак, мне нужно будет найти способ либо

1. подражать _mm_movemask_epi8 () - кажется дорогим, несколько смен и операционных

2. напрямую генерировать индексы тасования -

а именно, индекс i будет индексом i-го действительного элемента в некомпактированных данных

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

Это просто сделать поочередно, но мне нужно, чтобы это было параллельно (SIMD). Кажется, легко генерировать индексы разброса с префиксной суммой, но поскольку ни в AltiVec, ни в SSE нет инструкции разброса, мне нужно вместо этого собирать индексы. Индексы сбора являются обратной функцией индексов рассеяния, но как это можно получить параллельно? Я знаю, что в первые дни программирования на GPU преобразование скаттеров в собрания было обычной техникой, но ни один из этих двух описанных методов не кажется практичным.

Может, если не настаивать на том, что сжатие сохраняет порядок элементов, то это позволит более эффективно его реализовать? Я могу отказаться от этого.

Answer 1

Если вы хотите подражать _mm_movemask_epi8 и вам просто нужна 8-битная скалярная маска из 8-байтовых элементов, тогда вы можете сделать что-то подобное, используя 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;
}

Это 5 инструкций AltiVec против 1 в SSE. Вы можете потерять vec_splat и опусти до 4.