AccelerateHS / AccelerateHS/accelerate

Fusion can't always see through tuples

Ouverte
#268 4 commentaires 0 réactions 0 personnes assignées Voir sur GitHub
Langage dominant
Haskell
Étoiles
1k
Forks
135
Métriques de merge des PR
Aucune PR mergée en 30 j

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)

Guide de contribution

Aucun guide de contribution indexé pour ce dépôt

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.