[viff-devel] Vedr.: Small VIFF language parser

[Janus Dam Nielsen]

> I have another thing to consider: the height of the resulting
> arithmetic circuit.
Good idea.


> If there are several possibilities for expressing the formula and each
> has the same number of multiplications, then one should go for the one
> with the least height: so (a*b) * (c*d) instead of ((a*b) * c) * d.

This is more like an ordering problem. We want (a*b) and (c*d) to  
happen before the multiplication of the result so they can occur in  
parallel and we don't wast clock cycles.


> You might even want to prefer a formula with more multiplications if
> it lowers the height of the tree -- but I cannot come up with a good
> example of such a situation :-)
>
Given the huge execution time for an execution, I would expect this  
to be the case only in cases where you have extremely large left or  
right hanging expressions where the choice is only between one  
multiplication more or less.
If the choice comes to removing two multiplication then I think it is  
preferable to not removing them.

--
Janus


Den 17/07/2008 kl. 14.08 skrev Martin Geisler:

> Janus Dam Nielsen <jdn at brics.dk> writes:
>
>> If there are any other ideas for optimizations you would like to see
>> in a compiler for VIFF then now is the time to come forward.
>
> I have another thing to consider: the height of the resulting
> arithmetic circuit.
>
> If there are several possibilities for expressing the formula and each
> has the same number of multiplications, then one should go for the one
> with the least height: so (a*b) * (c*d) instead of ((a*b) * c) * d.
>
> You might even want to prefer a formula with more multiplications if
> it lowers the height of the tree -- but I cannot come up with a good
> example of such a situation :-)
>
> -- 
> Martin Geisler
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk