Оптимизация сжатия массива

Question

Допустим, у меня есть массив k = [1 2 0 0 5 4 0]

Я могу вычислить маску следующим образом m = k > 0 = [1 1 0 0 1 1 0]

Использование только маски m и следующих операций

1. Сдвиг влево / вправо
2. И / или
3. Добавить / Вычесть / Умножение

Я могу сжать k в следующее [1 2 5 4]

Вот как я сейчас это делаю (псевдокод MATLAB):

function out = compact( in )
    d = in
    for i = 1:size(in, 2) %do (# of items in in) passes
        m = d > 0
        %shift left, pad w/ 0 on right
        ml = [m(2:end) 0] % shift
        dl = [d(2:end) 0] % shift

        %if the data originally has a gap, fill it in w/ the 
        %left shifted one
        use = (m == 0) & (ml == 1) %2 comparison  

        d = use .* dl + ~use .* d

        %zero out elements that have been moved to the left
        use_r = [0 use(1:end-1)]
        d = d .* ~use_r
    end

    out = d(1 : size(find(in > 0), 2)) %truncate the end
end

Интуиция

На каждой итерации мы сдвигаем маску влево и сравниваем маску. Мы устанавливаем индекс для данных, сдвинутых влево, если мы обнаружим, что после этого сдвига индекс, который изначально был недействительным (mask [i] = 0), теперь действителен (mask [i] = 1).

Вопрос

Приведенный выше алгоритм имеет O (N * (3 сдвига + 2 сравнения + AND + add + 3 умножения)). Есть ли способ повысить его эффективность?

Answer 1

В исходном псевдокоде оптимизировать особо нечего.Здесь я вижу несколько небольших улучшений: цикл

• может выполнять на одну итерацию меньше (т. Е. Размер-1),
• , если 'use' равно нулю, вы можете прервать цикл раньше,
• use = (m == 0) & (ml == 1), вероятно, может быть упрощено до use = ~m & ml,
• , если ~ считается отдельной операцией, было бы лучше использовать инвертированную форму: use = m | ~ml, d = ~use .* dl + use .* d, use_r = [1 use(1:end-1)], d = d .*use_r

Но можно изобрести лучшие алгоритмы.А выбор алгоритма зависит от используемых ресурсов процессора:

• Load-Store Unit, т.е. применять алгоритм непосредственно к словам памяти.Здесь ничего нельзя сделать, пока производители микросхем не добавят высокопараллельные инструкции SCATTER в свои наборы инструкций.
• регистры SSE, то есть алгоритмы, работающие со всеми 16 байтами регистров.Алгоритмы, такие как предложенный псевдокод, здесь не могут помочь, потому что у нас уже есть различные инструкции перемешивания / перестановки, которые делают работу лучше.Использование различных команд сравнения с PMOVMSKB, группирование результата по 4 битам и применение различных команд тасования под переключателем / регистром (как описано LastCoder) - лучшее, что мы можем сделать.
• Регистры SSE / AVX с последними наборами команд позволяютлучший подход.Мы можем напрямую использовать результат PMOVMSKB, преобразовав его в управляющий регистр для чего-то вроде PSHUFB.
• Целочисленные регистры, т.е. регистры GPR или работающие одновременно над несколькими частями DWORD / QWORD регистров SSE / AVX (что позволяетвыполнить несколько независимых уплотнений).Предложенный псевдокод, применяемый к целочисленным регистрам, позволяет компактировать двоичные подмножества любой длины (от 2 до 20 бит).Вот мой алгоритм, который, вероятно, будет работать лучше.

C ++, 64 бита, ширина подмножества = 8:

typedef unsigned long long ull;
const ull h = 0x8080808080808080;
const ull l = 0x0101010101010101;
const ull end = 0xffffffffffffffff;

// uncompacted bytes
ull x = 0x0100802300887700;

// set hi bit for zero bytes (see D.Knuth, volume 4)
ull m = h & ~(x | ((x|h) - l));

// bitmask for nonzero bytes
m = ~(m | (m - (m>>7)));

// tail zero bytes need no special treatment
m |= (m - 1);

while (m != end)
{
  ull tailm = m ^ (m + 1); // bytes to be processed
  ull tailx = x & tailm; // get the bytes
  tailm |= (tailm << 8); // shift 1 byte at a time
  m |= tailm; // all processed bytes are masked
  x = (x ^ tailx) | (tailx << 8); // actual byte shift
}

Answer 2

Так что вам нужно выяснить, стоит ли дополнительный параллелизм, сдвиг / перетасовка накладных расходов для такой простой задачи.

for(int inIdx = 0, outIdx = 0; inIdx < inLength; inIdx++) {
 if(mask[inIdx] == 1) {
  out[outIdx] = in[inIdx];
  outIdx++;
 }
}

Если вы хотите пойти по параллельному SIMD-маршруту, лучше всего использовать SWITCH CASE со всеми возможными перестановками следующих 4 битов маски. Почему не 8? поскольку инструкция PSHUFD может перетасовываться только на XMMX m128, а не на YMMX m256.

Итак, вы делаете 16 дел:

• [1 1 1 1], [1 1 1 0], [1 1 0 0], [1 0 0 0], [0 0 0 0] не требуется никакого специального сдвига / перемешивания, просто скопируйте введите на выход MOVDQU и увеличьте выходной указатель соответственно на 4, 3, 2, 1, 0.
• [0 1 1 1], [0 0 1 1], [0 1 1 0], [0 0 0 1], [0 1 0 0], [0 0 1 0], вам просто нужно использовать PSRLx (сдвиг вправо логически) и увеличить выходной указатель на 3, 2, 2, 1, 1, 1 соответственно
• [1 0 0 1], [1 0 1 0], [0 1 0 1], [1 0 1 1], [1 1 0 1] вы используете PSHUFD для упаковки своего ввода, затем увеличиваете свой выходной указатель на 2, 2, 2, 3, 3 соответственно.

Таким образом, каждый случай будет минимальным количеством обработки (от 1 до 2 инструкций SIMD и 1 добавление указателя вывода). Окружающий цикл операторов case будет обрабатывать добавление постоянного указателя ввода (на 4) и MOVDQA для загрузки ввода.

Answer 3

Исходный код перемещает элемент массива только один шаг за раз.Это может быть улучшено.Можно сгруппировать элементы массива и сдвинуть их на 2 ^ k шагов одновременно.

Первая часть этого алгоритма вычисляет, на сколько шагов должен быть сдвинут каждый элемент.Вторая часть перемещает элементы - сначала на один шаг, затем на 2, затем на 4 и т. Д. Это работает правильно, и элементы не смешиваются, потому что после каждого сдвига достаточно места для выполнения сдвига в 2 раза больше.

Matlab,код не проверен:

function out = compact( in )
    m = in <= 0
    for i = 1:size(in, 2)-1
        m = [0 m(1:end-1)]
        s = s + m
    end

    d = in
    shift = 1
    for j = 1:ceil(log2(size(in, 2)))
        s1 = rem(s, 2)
        s = (s - s1) / 2
        d = (d .* ~s1) + ([d(1+shift:end) zeros(1,shift)] .* [s1(1+shift:end) zeros(1,shift)])
        shift = shift*2
    end
    out = d
end

Сложность алгоритма выше: O (N * (1 смещение + 1 сложение) + log (N) * (1 бэр + 2 добавление + 3 муль + 2 смена)).

Answer 4

Читая комментарии ниже исходного вопроса, в реальной задаче массив содержит 32-разрядные числа с плавающей запятой, а маска - (одно?) 32-разрядное целое число, поэтому я не понимаю, почему сдвиги и т. Д. Должны использоваться для сжатия массива. Простой алгоритм сжатия (в C) будет выглядеть примерно так:

float array[8];
unsigned int mask = ...;
int a = 0, b = 0;
while (mask) {
  if (mask & 1) { array[a++] = array[b]; }
  b++;
  mask >>= 1;
}
/* Size of compacted array is 'a' */
/* Optionally clear the rest: */
while (a < 8) array[a++] = 0.0;

Незначительные вариации могут быть связаны с битовым порядком маски, но единственные операции ALU, которые необходимы, - это обновление переменных индекса, смещение и AND маски. Поскольку исходный массив имеет ширину не менее 256 бит, ни один обычный ЦП не может сдвигать весь массив побитовым образом.

Answer 5

Предполагается, что вы хотите хранить только положительные целые числа из массива с минимальными шагами в C ++, это пример кода:

int j = 0;
int arraysize = (sizeof k)/4;
int store[arraysize];
for(int i = 0; i<arraysize; i++)
{
    if(k[i] > 0)
    {
        store[j] = k[i];
        j++;
    }
}

Или вы можете напрямую использовать элементы k [] , если не хотите использовать цикл for.