Ich muss einen Präfixsummenalgorithmus implementieren und müsste so schnell wie möglich sein. Ex:

[3, 1,  7,  0,  4,  1,  6,  3]
should give
[3, 4, 11, 11, 15, 16, 22, 25]

Gibt es eine Möglichkeit, dies mit der SSE / mmx / SIMD-CPU-Anweisung zu tun?

Meine erste Idee ist, jedes Paar rekursiv parallel zu summieren, bis alle Summen wie folgt berechnet wurden!

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

Um den Algorithmus ein wenig klarer zu machen, ist "z" nicht die endgültige Ausgabe

sondern verwendet, um die Ausgabe zu berechnen

        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];
        }