[Libre-soc-dev] SVP64 parallel map-reduce idea
Jacob Lifshay
programmerjake at gmail.com
Sun Jun 13 18:29:40 BST 2021
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
More information about the Libre-soc-dev
mailing list