Оптимизировать создание родительской битовой маски из дочерних битовых масок

Question

При условии ввода 64-битной дочерней маски, например:

10000000 01000000 00100000 00010000 00001000 00000100 00000010 00000000

8-битная родительская маска будет:

11111110

Один бит в родительской маске отображается в 8биты в строке дочерней маски, и бит в родительской маске устанавливается в 1, когда один из 8 дочерних битов установлен в 1. Простой алгоритм для вычисления этого будет следующим:

unsigned __int64 childMask = 0x8040201008040200; // The number above in hex
unsigned __int8 parentMask = 0;
for (int i = 0; i < 8; i++)
{
    const unsigned __int8 child = childMask >> (8 * i);
    parentMask |= (child > 0) << i;
}

Мне интересно, есть ли какие-либо оптимизации, чтобы сделать в коде выше.Код будет выполняться на CUDA, где я хотел бы избегать ветвей, когда это возможно.Для ответа, код на C ++ / C будет хорошо.Цикл for можно развернуть, но я бы предпочел оставить это для оптимизации компилятору, давая подсказки, где это необходимо, например, с помощью #pragma unroll.

Answer 1

Возможный подход заключается в использовании __vcmpgtu4 для сравнения байтов, которое возвращает результат в виде упакованных масок, которые можно отредактировать с помощью 0x08040201 (0x80402010 для старшей половины), чтобы превратить их в битыконечный результат, но затем их необходимо суммировать по горизонтали, что, по-видимому, не очень хорошо поддерживается, но это можно сделать с помощью простого старого кода в стиле C.

Например,

unsigned int low = childMask;
unsigned int high = childMask >> 32;
unsigned int lowmask = __vcmpgtu4(low, 0) & 0x08040201;
unsigned int highmask = __vcmpgtu4(high, 0) & 0x80402010;
unsigned int mask = lowmask | highmask;
mask |= mask >> 16;
mask |= mask >> 8;
parentMask = mask & 0xff;