partial reductions

I have a problem :
I must do two “partial” reductions in sequence, and place my results in an array in local memory in sequence.
“partial” reduction because i have a 0 and 1 sequence and i must stop when the 1 are all on the left of the reduction and all the 0 on the right.

problem 1)how i know when i must stop the reduction when there are only one on the left and only zero on the right (there isn’t any new one)

problem 2)I don’t know how many ones and zeros i have, and in the second reduction i must do the same thing but with data and i don’t know where start in the result array in local memory(i must start at the end of ones but what is the method for do this).

for example:

10001110 //first reduction start data
11110000 //first reduction result array in local memory

00000011 //second reduction start data
1111??00 //second reduction, problem:Where i must start to write the new 1 how i can know how many ones i have on the left and overwrite the zeros with the new one?
there isn’t functions like “count” or something other, i must take trace of all the 1 passed and start the second reduction from this in the result array in local memory?


I suspect you’re using the term “reduction” to mean something different to what it normally means in parallel programming. What you’re doing looks more like partitioning.

Are there other data associated with each zero / one? If not, the simplest would seem to be to compute the sum of the data (which counts the number of ones), and then just write out a new sequence with the appropriate number of ones.