GenericScanKernel semantics misunderstanding or bug?

[yves-surrel]

In GenericScanKernel.scan_expr, I understand a as 'accumulator' (what will be updated during the scan) and b as the 'current' value to update the accumulator with.

I have the following need (oversimplified for this discussion): scan an array, and if the current value is different from some 'error' value '(so, considered as a 'valid' value), just transmit it, otherwise transmit the previous accumulator value plus one.

In the following example,

import numpy as np
import pyopencl as cl
import pyopencl.array as cla
from pyopencl.scan import GenericScanKernel

error_value = 4

ctx = cl.create_some_context()
queue = cl.CommandQueue(ctx)

src = f"""
static int f(int a, int b)
{{
     if(b == {error_value})
         return a + 1;
     else
         return b;
}}
"""

knl = GenericScanKernel(
        ctx, np.int32,
        arguments="__global int *ary, __global int *out",
        input_expr="ary[i]",
        scan_expr="f(a, b)", neutral="100",
        output_statement="""
            out[i] = item;
            """,
            preamble=src)
            
print('i           input                   output')
print('--------------------------------------------------------')
for i in range(-5, 5):
    buf = np.array([i] + [error_value] * 4 + [2,2,2])
    buf_device = cla.to_device(queue, buf.astype('int32'))
    out_device = cla.zeros_like(buf_device)
    knl(buf_device, out_device)
    print(f'{i:2d}', buf, end = '   ')
    print(out_device.get())

I get the following output:

i           input                   output
--------------------------------------------------------
-5 [-5  4  4  4  4  2  2  2]   [-5 -4 -3 -2 -1  2  2  2]
-4 [-4  4  4  4  4  2  2  2]   [-4 -3 -2 -1  0  2  2  2]
-3 [-3  4  4  4  4  2  2  2]   [-3 -2 -1  0  1  2  2  2]
-2 [-2  4  4  4  4  2  2  2]   [-2 -1  0  1  2  2  2  2]
-1 [-1  4  4  4  4  2  2  2]   [-1  0  1  2  3  2  2  2]
 0 [0 4 4 4 4 2 2 2]   [  0   1   2   3 101   2   2   2]
 1 [1 4 4 4 4 2 2 2]   [  1   2   3 101   5   2   2   2]
 2 [2 4 4 4 4 2 2 2]   [  2   3 101   5   6   2   2   2]
 3 [3 4 4 4 4 2 2 2]   [  3 101   5   6   7   2   2   2]
 4 [4 4 4 4 4 2 2 2]   [101   5   6   7   8   2   2   2]

I am OK with lines i = -5 to -1, where things work as expected.

I am OK with the first value (101) of the last line (the accumulator has the value 'neutral', so accumulator + 1 is transmitted). I do not understand the following ones (unless I consider that the first value is actually 4).

For the other lines there is a behaviour that I can summarise as: 'when processing invalid slots, if accumulator + 1 == error_value, item used in output_statement will contain neutral + 1 instead of accumulator + 1'.

Is it a bug or a misunderstanding of scan kernel? It seems related to 'associativity' of the expression not being fulfilled:

def f(a, b):
    if b == error_value:
        return a + 1
    return b

def g(a, b, c):
    return f(f(a, b), c) - f(a, f(b, c))

for a in range(2, 7):
    for b in range(2, 7):
        for c in range(2, 7):
            h = g(a, b, c)
            if h:
                print(a, b, c, h)

returns

2 3 4 1
2 4 4 -1
4 3 4 -1
4 4 4 1
5 3 4 -2
5 4 4 2
6 3 4 -3
6 4 4 3

Do you think there is a way to obtain the correct result ?

In general, is it possible to include tests in scan_expr ? If not, it could be stated in the doc.

[inducer]

Tests are fine, but associativity is a hard requirement of the algorithm. Without it, I do not believe a parallel scan can be gotten to work. Maybe you can factor some of the processing into the "map expression" for each entry?

[yves-surrel]

but associativity is a hard requirement of the algorithm

For sure.