Accelerate

[Manuel M T Chakravarty]

Here just an update on the stencil extension.

I implemented support for the stencil combinator in the front-end.  I still need to add it to the interpreter and test it some more.  Then, after merging the many patches in the repo that I didn't pull yet, I will push a stencil patch.  (I hope to get this done tomorrow = Monday.)

There is one change to what we discussed.  Initially, I thought we could define stencils whose dimension are smaller than that of the source array, by using an extent of 1 in every dimension that the stencil shouldn't extent in.  However, it turns out that this is not compatible with the nested tuple syntax that we want to use for stencil patterns. The reason is simply that tuple pattern where one dimension has an extent of one is ambiguous.  For example, if I write

  stencil (l, m, r) = ...

to operate on a 2D array, the extent of the stencil could be (1, 3) or (3, 1).  Syntactically, we simply cannot distinguish the two.

As a result, I just don't see any option other than to require that the number of dimensions of the stencil are equal to those of the source array and to require that the extent of the stencil in every dimension is at least 3.  Hence, if you want a stencil of extent 3 in just one dimension of a 2D array, you need to define

  stencil :: Stencil3x3 -> Float
  stencil (     _
          , (l, m, r)
          ,     _
          )
          = (l + r) / 2 + m

As I mentioned before, it is apparent from the AST that 6 of the stencil positions are not used and the backend can optimise accordingly.

BTW, stencils don't need to be rectangular.  They just need to be symmetric in all dimensions (and none of the tuples can have less than three arguments).

Manuel


Ben Lever:
> Hi Manuel,
> 
> Of course, in the future we would require larger stencils (e.g. 36x36 in AutoMap) to be supported. Is there a penalty for using tuples to specify stencil patterns when the stencil size is large? Had you envisaged an upper limit to stencil size?
> 
> Large tuples are tedious because —in principle— each argument of a tuple could be of a different type.  That capability is not used by stencils (where all arguments are of the element type of the source array).  However, in order to do the reflection of the EDSL, we need a datatype where the type fixes the size of the structure — that is the case for tuples, where the arity of the type matches the arity of the values.  To support larger stencils conveniently, we ideally need a datatype that constrains all elements to be of the same type (like an array) *and* where the size is explicit in the type (like with a tuple) — ie, we want a form of statically sized array.
> 
> Ok - that makes sense.
> 
> 
> I'm sure we can work that out, but it keeps matters simpler if we can do that at a later point (after we have small stencils and sharing efficiently implemented).
> 
> We're happy with that approach - get everything working with tuples first then look at a new data type later that can support larger stencils more effectively.
> 
> 
> Regards,
> 
> Ben Lever
> Senior Researcher Engineer
> National ICT Australia