AccelerateHS / AccelerateHS/accelerate

Fusion can't always see through tuples

Open
#268 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
1k
Forks
135
PR merge metrics
No merged PRs in 30d

Description

The current fusion system doesn't always work very well in the presence of array level tuples. For example:

```
> import Data.Array.Accelerate as A
> let a = lift ( A.fill (index1 10) 1.0, A.fill (index1 10) 2.0 ) :: Acc (Vector Float, Vector Float)
> A.zipWith (+) (A.afst a) (A.asnd a)
let a0 = (generate (Z :. 10) (\x0 -> 1.0),generate (Z :. 10) (\x0 -> 2.0)) in
let a1 = #1 a0 in
let a2 = #0 a0
in generate (intersect (shape a1) (shape a2)) (\x0 -> (a1!x0) + (a2!x0))
```

We have two needlessly manifest arrays here. The current fusion system is not able to see that while `a` is referenced twice, each of its components are really only used once, so are able to be embedded and fused.

I think the simplest way to solve this, in a lot of cases anyway, is to have a pass before fusion that turns terms of the form

```
let t = (a, b, ...)
in ... #0 t ... #1 t ...
```

into

```
let t0 = a
t1 = b
...
in ... t0 ... t1 ...
```

i.e.Let bound tuples are expanded into multiple bindings. I'm pretty certain this normal form has a name, but I can't think what it is (anyone know?).

This problem is of particular pain with the vectoriser, where we represent nested arrays as a tuple of segment descriptors and a vector of elements, so lots of stuff that could easily be fused isn't. For this reason, I was going to go ahead and implement this in the streaming branch, but I thought I should check with you @tmcdonell first because you might have had thoughts on this before?

(ping @fmma)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.