[Libre-soc-dev] SVP64 parallel map-reduce idea

[Jacob Lifshay]

On Sat, Jun 12, 2021, 07:25 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
wrote:

> https://en.m.wikipedia.org/wiki/Prefix_sum
>
> i was expecting the answer to be 307. i went, "thaaat's not a straight
> aaaadd" :)
>
> prefix sum. pascal triangle.  i love it.  the scalar version can be
> mapreduce, parallel version prefix sum.
>

Note that the algorithm I wrote is *not* a prefix-sum, it can just be used
to do part of a prefix-sum calculation.

>
> ok, so this is really nice.
>
> next step, an algorithm is needed which can specify srcstep and
> dststep,  fitting on top of a regfile rather than an abstract
> temporary array.
>

That temporary array is intended to be the destination vector.

>
> i.e. the code should start:
>
> int regfile[128]
>
> def prefixsum(dstreg, src1reg, src2reg, VL, operation_to_call)
>    int srcstep=0
>    int dststep=0
>
> and reference items in regfile by computing the indices (rather than
> having a temporary array).
>
> it would also i think be really valuable to have the output result
> array *guaranteed* to comprise the intermediate cumulative sums as
> well.
>

iirc, computing a prefix-sum *quickly* requires more operations than a
reduction requires, the algorithm I wrote only does those operations
necessary for a reduction.

Jacob