Сумма префикса SIMD на процессоре Intel
Мне нужно реализовать алгоритм суммирования префиксов, и он должен быть максимально быстрым. Пример:
[3, 1, 7, 0, 4, 1, 6, 3]
should give
[3, 4, 11, 11, 15, 16, 22, 25]
Есть ли способ сделать это с помощью инструкции процессора SSE / mmx / SIMD?
Моя первая идея - рекурсивно суммировать каждую пару параллельно, пока вся сумма не будет вычислена, как показано ниже!
//in parallel do
for (int i = 0; i<z.length; i++){
z[i] = x[i<<1] + x[(i<<1)+1];
}
Чтобы сделать алгоритм немного более понятным & quot; z & quot; это не окончательный вывод
но вместо этого используется для вычисления выхода
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];
}