Сумма префиксов SIMD на процессоре Intel

Мне нужно реализовать алгоритм суммирования префиксов, и он должен быть максимально быстрым.
Пример:

[3, 1,  7,  0,  4,  1,  6,  3]

должно дать:

[3, 4, 11, 11, 15, 16, 22, 25]

Есть ли способ сделать это с помощью инструкции процессора SSE SIMD?

Моя первая идея состоит в том, чтобы суммировать каждую пару параллельно рекурсивно, пока вся сумма не будет вычислена, как показано ниже!

//in parallel do 
for (int i = 0; i < z.length; i++) {
    z[i] = x[i << 1] + x[(i << 1) + 1];
}

Чтобы сделать алгоритм более понятным, zне является конечным результатом, а используется для его вычисления.

int[] w = computePrefixSum(z);
for (int i = 1; i < ouput.length; i++) {
    ouput[i] = (i % 2 == 0) ? (x[i] + ouput[i - 1]) :  w[(i - 1) >> 1];
}
20
задан Peter Cordes 26 November 2019 в 02:23
поделиться