How to (f)map over rows of a matrix (or other subslices of a higher-rank shape)?

[Wiebe-Marten Wijnja]

Hello everyone!

I am trying to get a more thorough understanding of how to write code with Accelerate.

One thing I am having trouble figuring out, is how to run code in parallel on each of the rows of a matrix

(e.g. rather than performing an operation in parallel for each element, we perform a (possibly sequential) operation on each whole row in parallel).

How is something like this done?

Things I have tried so far:

- `map :: (Shape sh, Elt a, Elt b) => (Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b) ` works element-wise, so we cannot use it, but we would like something similar to this.

- I've looked into the `lens-accelerate` library but it seems (I am not very well-versed in the dialect of lenses ^_^') to be focused more on working with tuples.

- I've tried the following hackish 'solution':

(use indices) |> A.map (\index -> A.slice (use mat) (lift (Z :. index :. All)) |> (A.!! 0)) |> PTX.run

which (un?)surprisingly raises a nested data paralellism error at runtime.

Thank you,

~Marten / Qqwy

[Tom Smeding]

If you'd want to do a parallel operation on each row, that won't work due to the no-nested-parallelism restriction that you found already. :)

Performing sequential operations on substructures is something that I've had trouble with doing too; while `fold` and `scan` can reduce the inner dimension of an array, I don't know if you can perform more complicated operations.

About lens-accelerate: I haven't really used the library, but I can say that simply because it will need to produce something that is expressible in the Accelerate core language, the fact that you can't express it with native Accelerate operations (if that's indeed the case) would imply that lens-accelerate also doesn't allow you to do that.

- Tom

[Wiebe-Marten Wijnja]

Thanks for your reply.

It's quite curious and something to definitely keep in mind when developing 'building blocks' for a larger program,
because if you have a function that e.g. works on an `Acc (Vector a) -> Acc (Vector b)` then it is not possible to lift it to higher-rank arrays.
Instead, you have to think from the get-go how you'll set everything up based on `fold`s and `scan`s, which is restricted further by the fact that the accumulator needs to have the same type as the current element.

After being puzzled by this I looked in the internals of accelerate-llvm (specifically: https://github.com/AccelerateHS/accelerate-llvm/blob/master/accelerate-llvm-ptx/src/Data/Array/Accelerate/LLVM/PTX/CodeGen/Scan.hs)
and found out that this is closely related to the stated requirement that the accumulation operation needs to be associative because an algorithm to do a parallel prefix scan is used.

Now for `fold` there is the alternative `sfold` that just runs sequentially along the innermost dimension. However, I don't believe something similar exists currently for `scan` in Accumulate.
This is a bit of a bummer because if you e.g. have a large enough matrix to let each thread work on its own row, then there's no need for the extra overhead that the parallel scan incurs.

As a side note, such an `sscan` would not have the same requirement to keep the type of the accumulator the same, which give extra flexibility to the programmer.
Alas, implementing it myself with LLVM/CUDA-bindings is currently out of my league.

I do know that in the Accelerate internals there is a mkScanS (c.f. https://github.com/AccelerateHS/accelerate-llvm/blob/0f92cd6ad324f87378bffbb9b74bbd0722cee417/accelerate-llvm-native/src/Data/Array/Accelerate/LLVM/Native/CodeGen/Scan.hs#L241) but when it is used exactly or how to trigger its usage from user-level code, I do not know.

~Marten

--
You received this message because you are subscribed to the Google Groups "Accelerate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to accelerate-hask...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/accelerate-haskell/1beccf41-d7be-459b-a078-a456b68ccca6%40googlegroups.com.