Parallel accumulated sum in OpenCL
What are k and a?  It looks like a is a loop counter variable, in which case it can be renamed to i and moved to the front of the first for loop.  As for k, rename it such that it conveys its purpose.  With the exception of loop counter variables such as i, variables shouldn't be a single character.
Many of the lines in the for loops are difficult to read, especially with all the bit-shifting.  Depending on the type of shift, the optimizing compiler may be able to replace some arithmetic operation with an appropriate bitshift.  But for others, it would help to leave comments to explain what's being done for each complex operation.
This is quite crammed together:


for (; globalPasses&gt;&gt;=1; ++a){
    barrier(CLK_GLOBAL_MEM_FENCE);
    while (*completeBlocks != 0);
    if (lid == 0) atomic_inc(completeBlocks);
    while (*completeBlocks &lt; get_num_groups(0));
    if (lid == 0 &amp;&amp; gid == 0) atomic_xchg(completeBlocks,0);
    k = (gid &gt;&gt; a &lt;&lt; (a+1)) + (1&lt;&lt;a);
    output[k + (lid&amp;((1&lt;&lt;a)-1))] = output[k - 1] + output[k + (gid&amp;((1&lt;&lt;a)-1))];
};



You should isolate the while loops so that it's easy to see that they're busy-waits.  You could also consider using curly braces for the if statements.  Finally, consider adding whitespace between the operators for more readability.

for (; globalPasses &gt;&gt;= 1; ++a) {
    barrier(CLK_GLOBAL_MEM_FENCE);

    while (*completeBlocks != 0);

    if (lid == 0) {
        atomic_inc(completeBlocks);
    }

    while (*completeBlocks &lt; get_num_groups(0));

    if (lid == 0 &amp;&amp; gid == 0) {
        atomic_xchg(completeBlocks, 0);
    }

    k = (gid &gt;&gt; a &lt;&lt; (a + 1)) + (1 &lt;&lt; a);

    output[k + (lid&amp;((1 &lt;&lt; a) - 1))] = 
        output[k - 1] + output[k + (gid&amp;((1 &lt; &lt;a) - 1))];
};