[macstl-dev] Opinions wanted: tied expressions (multi-valued
expressions and manual loop fusion)
lipovsky at cs.bu.edu
Tue Dec 6 02:03:39 WST 2005
On Mon, 28 Nov 2005, Glen Low wrote:
> Dear All:
> macstl already fuses loops with single expressions i.e.
> e = (a + b) * d;
> where each of a, b, d and e are valarrays or refarrays; macstl
> automatically expands that out into the right loop with the temp a +
> b often just being a register.
> Now the next step is to use C++ tuples (or a derivative we optimize
> for valarray operations) to fuse multiple expressions in PERL/PHP-
> style e.g.
> tie (e, f) = tie ((a + b) * d, g - h);
> Here the loop encompasses setting e and f element-by-element, and
> not: all of e and then all of f.
> Things I have to thrash out with the proposal:
> 1. Should tie only work at the top level or should we allow ties at
> the subexpression level? If so, what impact on performance? e.g.
> tie (e, f) = tie (a * b) + tie (g * h);
What does the above expression represent? I don't understand the right
> 2. How should we spec it so that we don't invalidate multiproc work?
> (one of the other projects that might be sponsored, to get macstl to
> scale for multiprocs transparently.) We should say something like:
> logical parallel sections of the expressions may be evaluated in any
> order (since they might be in a multiproc situation).
I don't have an opinion on that yet. What mutiprocessor architectures do
you mean, Cell? Anything else? Do you want to invoke something like MPI
behind the scene?
> 3. What about dependent expressions e.g.
> tie (e, f) = tie ((a + b) * d, e * h); // f now depends on e
Excellent case!! And very relevant, too. Yes, this should definitely be
tie (f, g) = tie (g * h, (a + b) * d) //e depends on f, an
Should be left without any further analysis on macstl's part. The user is
responsible for correctly ordering statements inside the tie () functor.
> 4. Further to point 3, should we introduce a special "temp"
> placeholder which would work akin to a manual CSE? If so what impact
> on 2? How to implement in C++?
The only reasonable way (that I see) to implement it in C++ is have a bank
of prototyped valarray/refarray tie_temp<float/int/whatever> vectors. For
valarray<int> tie_temp0, tie_temp1, tie_temp2, ...;
valarray<char> tie_temp0, tie_temp1, .... ;
There is a lot of impact on 2, that's why, I think it's best to focus on
on one processor. People can always compile different pieces of code based
on macstl and make them work together on multiprocessor systems manually.
> 5. Do we do automatic or manual tie flattening e.g.
> should tie (tie (a, b, c), d, e, f) become tie (a, b, c, d, e, f)
> automatically or some other function do this?
I think that tie (tie (a, b, c), d, e, f) should automatically. Become tie
(a, b, c, d, e, f).
> 6. How to incorporate multiple output syntax into the proposal. E.g.
> a deinterleave function that deinterleaves 1 stream into 4 might
> logically produce a 4-tuple so that
> tie (a, b, c, d) = deinterleave (e);
> But then what should the syntax be for applying operations between
> the deinterleaved streams i.e. what would be the succinct expression of
> tie (a, b, c, d) = deinterelave (e);
> f = (a * b) + (c * d);
> I suppose if we allowed temp placeholders and tie flattening, then
> tie (a, b, c, d, f) = tie (deinterleave (e), (a * b) + (c *d));
> could be one such syntax.
The latter syntax looks really nice! One note though: is "deinterleave"
the right term for that? Maybe there's something else from, say, set
theory to denote a set containing the same element multiple times.
More information about the macstl-dev