Accelerate

[Manuel M T Chakravarty]

>> From a parallel programming point of view, the stencil specification function specifies a kind of permutation.  In data-parallel programming, permutations are big and inefficient sledge hammers that should be avoided where possible (and be replaced with more structured operations).  In fact, I get the distinct feeling that we should characterise more precisely what a stencil actually is.  What are a stencil's properties and constraints?  (I do mean the actual stencil, not the operation that applies the stencil to an entire source array, which we slightly confusingly call 'stencil' at the moment.)
>> 
>> A stencil is static; ie, it is not computed by the code running on the GPU, but determined by the Haskell program embedding the Accelerate program.  So, we do have the full Haskell language to characterise stencils.  Before trying to characterise stencils in Haskell, let me list a few constraints that I believe stencils meet:
>> 
>> * A stencil is always drawn from a neighbourhood of locations in the source array — ie, from a sub-hypercube of the same dimensionality as the source array.
>> * The focal point of a stencil is not necessarily the middle of that neighbourhood.  (It would be easier of it always were the middle, but I guess that would be too narrow — correct me if I'm wrong.)
>> * As the 5-point stencil shows, some points from the neighbourhood may be ignored.
>> 
>> Is that right?
>> 
> I agree with your list of stencil constraints and you are also correct about the second point regarding the focal point of the stencil. I would also add that a stencil specify how to deal with boundary conditions.

Yes, we also need a specification of the boundary conditions.  So, what are the different ways in which we should be able to deal with boundary conditions?  Here some possibilities:

* Clamp access to the extent of the source array: if we want to access i+1 in an array whose highest index is i, we take the value at index i.
* Wrap around: if we want to access i+1 in an array whose highest index is i, we take the value at index 0.
* Constant: out of bounds access, results in a predetermined constant (maybe different constants at different boundaries).

Is that all?  AFAIK one standard way to deal with boundary conditions is to have a boundary array and all out-of-bounds stencil access just refers to that array.

What do you think?

> Are you imagining the need for a new Accelerate type that characterises stencils?

I think that a new type (one that you cannot wrap in Exp) might provide a precise description of a stencil, which would enable far reaching code optimisations without the need to analyse the dynamic behaviour of code, such as the stencil specification function.  The latter should be possible, but it might turn out to be quite tricky.  To recover the form of a stencil from a specification function, you need to analyse the index computations of the specification function.  If they are non-linear, it can quickly get complicated.

In other words, instead of specifying a stencil function and using code analysis to recover its essential properties, I would prefer to directly specify those properties (such as the extent of the neighbourhood).  As a benefit, I believe code generation and optimisation will be simpler.

As stencil properties are static (ie, they are the same for every execution of one particular stencil), this new type to describe stencils needs not be among the types that we can wrap in an Exp.  It can be any Haskell type.  (I'm trying to come up with a suitable type.  At the moment, I'm just trying to understand what the exact requirements are.)

Manuel