[<<][staapl][>>][..]
Wed Sep 16 10:04:05 CEST 2009

Using associativity

I'd like to use the associativity laws to shorten the critical path
using binary subdivision.  This is only useful for the staged
version.  It would probably be best to hide this behind the `ring^'
interface since it relies on representation.

The naive subdivision won't work: it produces this:
box> (sum (syntax->list #'(a b c d e f g h)))

;; (v8 (+ a b))
;; (v9 (+ c d))
;; (v10 (+ v8 v9))
;; (v11 (+ e f))
;; (v12 (+ g h))
;; (v13 (+ v11 v12))
;; (v14 (+ v10 v13))

which is depth-first.  Breadth-first is probably better, but it uses
more intermediates.  Looks like the trade-offs here are implicit.

Anyway: it is a different problem.  This could be done in two steps:
first make sure the _dependencies_ are a binary tree, then in a second
iteration schedule the operations to allow for pipeline delays.  The
latter can probably be handled by the C compiler.

So: compilation is

    EQUATIONS -> DATAFLOW COMBINATORS -> DATAFLOW SCALAR -> SEQUENTIAL


Actually, once you start combining different forms, because of
specialized mul/add for 0 and 1, the tree of operations gets
unbalanced.  Postponing until the computation is finished and then
re-balancing (based on algebraic laws) might be an interesting
optimization.


Ok.  I've added memoization.  This doesn't do commutative ops though.
Ok, this is now also handled.




[Reply][About]
[<<][staapl][>>][..]