Calculating integral images / cumulative add

[John Rose]

On Jan 4, 2021, at 5:51 PM, Stefan Reich <stefan.reich.maker.of.eye at googlemail.com> wrote:
> 
> Oh I just saw this in the presentation
> <http://cr.openjdk.java.net/~jrose/pres/201907-Vectors.pdf <http://cr.openjdk.java.net/~jrose/pres/201907-Vectors.pdf>>:
> 
>  ▪ Segmented scan (reduce with partials and mask-driven reset)
> 
> That's probably what I want... so it's not there yet?

You can do a lot of really nice algorithms, including parsing
and nested parallelism, with good segmented scan primitives.
(I learned this from Guy Steele in the Connection Machine days.)

I hope the V-API will support this some day, but IMO we need
some good use cases (like yours) to motivate the work, plus some
pathfinding.  Also, to be honest, the SIMD hardware today is
not yet up to the standards of the Connection Machine of the
‘80s, with respect to those use cases.  (The other thing today’s
HW is missing, compared to the CM, is reverse permutations,
AKA sorting networks, AKA parallel deposit.  Scatter is the
current approximation, but it doesn’t handle collisions well.)

One step at a time…  For pathfinding, I suggest building the
primitives you need (using binary tree decomposition) on top
of the existing stuff.  It won’t be as fast w/o JIT support, and
your patience will be tried sorely by the lack of support for
OO abstraction over vector computations.  (Function
abstraction is likely to work better.)  I think that’s a direct
route to exploring the opportunities here.

— John