эффективный способ преобразования индексов рассеяния в индексы сбора? - PullRequest
Новая
       65

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

7 голосов
/ 07 июня 2011

Я пытаюсь записать сжатие потока (взять массив и избавиться от пустых элементов) с использованием встроенных 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 преобразование скаттеров в группы было обычной техникой, но ни один из этих двух описанных методов не кажется практичным.

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

1 Ответ

5 голосов
/ 08 июня 2011

Если вы хотите эмулировать _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.

...