# No subject

Thu Jun 10 07:12:33 EDT 2010

on specifies a kind of permutation.  In data-parallel programming, permutat=
ions are big and inefficient sledge hammers that should be avoided where po=
ssible (and be replaced with more structured operations).  In fact, I get t=
he distinct feeling that we should characterise more precisely what a stenc=
il actually is.  What are a stencil's properties and constraints?  (I do me=
an the actual stencil, not the operation that applies the stencil to an ent=
ire source array, which we slightly confusingly call 'stencil' at the momen=
t.)

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.  S=
o, we do have the full Haskell language to characterise stencils.  Before t=
rying to characterise stencils in Haskell, let me list a few constraints th=
at I believe stencils meet:

* A stencil is always drawn from a neighbourhood of locations in the source=
array =97 ie, from a sub-hypercube of the same dimensionality as the sourc=
e array.
* The focal point of a stencil is not necessarily the middle of that neighb=
ourhood.  (It would be easier of it always were the middle, but I guess tha=
t would be too narrow =97 correct me if I'm wrong.)
* As the 5-point stencil shows, some points from the neighbourhood may be i=
gnored.

Is that right?

I agree with your list of stencil constraints and you are also correct abou=
t the second point regarding the focal point of the stencil. I would also a=
dd that a stencil specify how to deal with boundary conditions.

Are you imagining the need for a new Accelerate type that characterises ste=
ncils?

Regards,

Ben Lever
Senior Researcher Engineer
National ICT Australia

NICTA l Locked Bag 9013 l Alexandria NSW 1435
T + 612 8306 0742 | F +612 9376 2027
www.nicta.com.au<http://www.nicta.com.au/> l ben.lever at nicta.com.au<mailto:=
rami.mukhtar at nicta.com.au>