Fri Mar 30 16:01:57 EDT 2007

grid processing

the possible optimizations depend tremendously on the amount of
information available on the individual processors, so the idea is
to keep the primitive set really simple, and look at their

* associative    (n-ary op consisting of n-1 binary ops)
* commutative    (binary op)
* linear/linear1

+   l a c
*   l a c
/   l1

the typical structure to look at is a one dimensional FIR filter,
since this can be extended to 2D (space) and 3D (space+time)

(* gain
   (+ x
      (n x 0 -1)
      (n x 0 +1)))

let's analize. 1 and 3 are constants, so (/ 1 3) can be
evaluated. x is used in a 'n' expression, which we use to denote
membership of a grid. let's make all parameters into grids

(* (gain)
   (+ (x 0)
      (x -1)
      (x +1)))

so (gain) is a 0D grid, (x 0) is a 1D grid (x 0 0) is a 2D grid etc..

composite operations can be specified, for example

(processor (a b)
  (+ (a) (b 0) (b 1)))

this means all parameters need to be declared, since we need to know
the order. the syntax i'm using here requires ordered parameter
lists. i prefer this over keywords, since it is more compact, and we
need to fill in all inputs anyway (no explicit defaults).

another ineresting operation on an expression is to compute it's
reverse: an expression represents a dependency graph, which can be
inverted. however this is only iteresting for multiple inputs, which
we won't use yet: apply explicit subexpression elimination and graphic

ok, so we need parameter names.

another interesting operation is fanin: how many times is a single
value used? this is important for memory management
(linearization). note that linearization and operation sequencing is
almost equivalent to translation to forth.

maybe it's time to go for the first iteration binder. we map a single
function to an explicit iterator. i.e.

(+ (a 0) (a 1))

it has a single 1D grid input, and produces a single grid. ah!
something i forgot: what's the output type? a grid of dimensionality
equal to the maximum of the input grids.

so, an n-dimensional grid is placed on the same notational level as an
n-ary procedure.

ok. the above can be transformed to the loop body

(+ (index a (+ 0 i)) (index a (+ 1 i)))

where a runs over the line. the rest is border values:

(+ left (index a 0))
(+ (index a w) right)

so the idea is to make the loop body and the 2 borders.

implementation (see ip.ss)

     implicit  ->  explicit
     (a 0          (a ([I 0]  0)
        1             ([I 1]  1)
       -1)            ([I 2] -1))
            loop depth ---X