AccelerateHS / AccelerateHS/accelerate

Fusion can't always see through tuples

Abierto
#268 4 comentarios 0 reacciones 0 asignados Ver en GitHub
Lenguaje dominante
Haskell
Estrellas
1k
Forks
135
Métricas de merge de PR
Sin PR fusionados en 30 d

Descripción

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)

Guía de contribución

No hay ninguna guía de contribución indexada para este repositorio

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.