Accelerate

[Manuel M T Chakravarty]

Hi Ben,

> Thanks! As it turned out, to get things going I ended up putting this support in for 9-tuples myself. Whilst we've overlapped, it turned out to be a useful exercise for me as what I discovered, and what I hadn't realised, was that stencil patterns are hard-wired into Accelerate. That is, the 3x3, 5x5, 9x9, etc types are defined in Accelerate, and need to be due to defining typeclass instances, etc , and they are the only patterns available to the user. Is that correct?

Yes and no.  The patterns themselves are not hardwired.  What is hardwired are the arities of the tuples that can be used in stencils (3, 5, 7 & 9-tuple at the moment) and also the number of dimensions that stencil arrays can have.  I think I should be able to avoid the latter, though.  However, you can combine these tuples however you like.  For example, we can have a stencil like this:

  funnyStencil (             (x1_1, x1_2, x1_3)
               ,       (x2_1, x2_2, x2_3, x2_4, x2_5)
               , (x3_1, x3_2, x3_3, x3_4, x3_5, x3_6, x3_7)
               ,       (x4_1, x4_2, x4_3, x4_4, x4_5)
               ,             (x5_1, x5_2, x5_3)
               ) = ...

> Previously I had imagined that stencil patterns could be defined outside Accelerate  - 3x3, 5x5, etc were predefined to give the user a head-start. As a result, because Accelerate is a meta-programming framework, I had imagined it would be possible to write functions that build and return stencil functions. For example, the ability to write a convolution function that takes the convolution kernel as its input and calls stencil, creating the required stencil function based on the size and values of the kernel.

You should be able to write stencil functions that build and return stencil functions.  It may be a bit tricky (involving type classes) as we use native Haskell pattern matching (and not a facility in the embedded language) for pattern matching in the stencil — this does make it *much* nice to write stencil's manually, though.  In the worst case, there is always Template Haskell (a meta-programming facility for Haskell), with which we can even generate vanilla Haskell code.  So, generating stencil functions is surely possible.

You are saying that a convolution function would take a convolution kernel as its input.  How would you want to represent that kernel?

>  Because Accelerate doesn't allow arbitrary stencil patterns, a convolution function wouldn't be able to support arbitrarily-sized kernels (unless it somehow rounded-up to the biggest pattern, but even that might not exist).

The stencils cannot be arbitrarily size with the current interface — that is correct.  Even the Glasgow Haskell Compiler has an upper limit on the size of tuples it supports.  So, there is always going to be some size limit.

> Is my understanding correct? Maybe there is a way too implement a function such as convolution ...
> 
> This is not an immediate problem, but maybe it can be discussed again when we investigate larger stencil patterns in the future. For example, in one of our use cases (36x36 stencil), it would be ideal if the stencil function could be generated, where the generation is driven by data specifying which coordinates within the stencil bounding box are to be analysed.

In principle, I think, we can scale the current approach up to 36x36 stencils and use a code generator for the stencil code, but it may be a bit awkward.  So, we may want to have a look at whether we'd like an alternative interface for large stencils.  However, I'm worried that if we use arrays instead of tuples to describe the stencil, it'll get harder to identify unused stencil positions in the backend, so it depends a bit on what kind of convolution functions we are looking at.

Cheers,
Manuel