[macstl-dev] Opinions wanted: tied expressions (multi-valued expressions and manual loop fusion)

[Ilya Lipovsky]

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 
side.


> 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 
supported. However,

tie (f, g) = tie (g * h, (a + b) * d)		//e depends on f, an 
						//uninitialized array

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 
example

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.

-Ilya