Могу ли я использовать SIMD для сортировки / категоризации сегментов? - PullRequest
Новая
       26

Могу ли я использовать SIMD для сортировки / категоризации сегментов?

0 голосов
/ 18 сентября 2018

Мне любопытно, что такое SIMD, и мне интересно, может ли он справиться с этим вариантом использования.

Допустим, у меня есть массив из 2048 целых чисел, например [0x018A, 0x004B, 0x01C0, 0x0234, 0x0098, 0x0343, 0x0222, 0x0301, 0x0398, 0x0087, 0x0167, 0x0389, 0x03F2, 0x0034, 0x0345, ...]

Обратите внимание, как все они начинаются с 0x00, 0x01, 0x02 или 0x03.Я хочу разбить их на 4 массива:

  • Один для всех целых чисел, начиная с 0x00
  • Один для всех целых чисел, начиная с 0x01
  • Один для всехцелые числа, начинающиеся с 0x02
  • Один для всех целых чисел, начинающихся с 0x03

Я думаю, у меня был бы такой код: 

int main() {
   uint16_t in[2048] = ...;

   // 4 arrays, one for each category
   uint16_t out[4][2048];

   // Pointers to the next available slot in each of the arrays
   uint16_t *nextOut[4] = { out[0], out[1], out[2], out[3] };

   for (uint16_t *nextIn = in; nextIn < 2048; nextIn += 4) {

       (*** magic simd instructions here ***)

       // Equivalent non-simd code:
       uint16_t categories[4];
       for (int i = 0; i < 4; i++) {
           categories[i] = nextIn[i] & 0xFF00;
       }
       for (int i = 0; i < 4; i++) {
           uint16_t category = categories[i];
           *nextOut[category] = nextIn[i];
           nextOut[category]++;
       }
   }
   // Now I have my categoried arrays!
}

Я полагаю, что мой первыйВнутренний цикл не требует SIMD, это может быть просто инструкция (x & 0xFF00FF00FF00FF00), но мне интересно, сможем ли мы превратить этот второй внутренний цикл в инструкцию SIMD.

Есть ли какая-нибудь инструкция SIMD для этого "категоризировать «действие, которое я делаю?»

Инструкции «вставить» кажутся несколько многообещающими, но я слишком зелен, чтобы понять описания на https://software.intel.com/en-us/node/695331.

Если нет, точто-нибудь близко?

Спасибо!

1 Ответ

0 голосов
/ 19 сентября 2018

Вы можете сделать это с SIMD, но как быстро это будет зависеть от того, какие именно наборы инструкций у вас есть, и насколько вы умны в своей реализации.

Один из подходов состоит в том, чтобы взять массив и «просеять» его, чтобы выделить элементы, которые принадлежат разным сегментам.Например, возьмите 32 байта из вашего массива, который будет иметь 16 16-битных элементов.Используйте некоторые инструкции cmpgt, чтобы получить маску, в которой определяется, попадает ли каждый элемент в корзину 00 + 01 или 02 + 03.Затем используйте какую-либо операцию «сжатия» или «фильтрации», чтобы переместить все маскированные элементы непрерывно в один конец регистра, а затем то же самое для немаскированных элементов.

Затем повторите это еще раз, чтобы отсортировать 00 из 01 и 02 из 03.

С AVX2 вы можете начать с этого вопроса для вдохновения в операции «компресс».С AVX512 вы можете использовать инструкцию vcompress, чтобы помочь: он выполняет именно эту операцию, но только с 32-битной или 64-битной гранулярностью, поэтому вам нужно будет выполнить пару по крайней мере для каждого вектора.

Вы также можете попробовать вертикальный подход, при котором вы загружаете N векторов, а затем переключаетесь между ними, чтобы 0-й вектор имел наименьшие элементы и т. Д. На этом этапе вы можете использовать более оптимизированный алгоритм для этапа сжатия (например, еслиВы сортируете по вертикали достаточно векторов, векторы на концах могут полностью начинаться с 0x00 и т. д.)

Наконец, вы также можете рассмотреть возможность организации ваших данных по-другому, либо в источнике, либо в качестве этапа предварительной обработки.: выделение байта категории, который всегда равен 0-3, из байта полезной нагрузки.Многие этапы обработки должны выполняться только на одном или другом, так что вы можете потенциально повысить эффективность, разделив их таким образом.Например, вы можете выполнить операцию сравнения на 32 байтах всех категорий, а затем выполнить операцию сжатия на 32 байтах полезной нагрузки (по крайней мере, на последнем этапе, где каждая категория уникальна).

Это привело бы к массивам байтовых элементов, а не 16-битных элементов, где байт "категории" неявен.Вы сократили размер данных вдвое, что может ускорить все остальное, что вы хотите сделать с данными в будущем.

Если вы не можете создать исходные данные в этом формате, вы можете использоватьbucketing как возможность удалить байт тега, когда вы помещаете полезную нагрузку в правильное ведро, так что вывод равен uint8_t out[4][2048];.Если вы делаете SIMD-левый пакет с байтовым перемешиванием pshufb, как описано в комментариях, вы можете выбрать вектор управления перемешиванием, который упаковывает только байты полезной нагрузки в младшую половину.

(до AVX512BWВ x86 SIMD нет тасования слов с переменным управлением, только байт или двойное слово, поэтому вам уже понадобился тасование байтов, которое может так же легко отделить полезные данные от тегов одновременно с упаковкой байтов полезных данных в нижнюю часть.)

...