Janus Dam Nielsen <[EMAIL PROTECTED]> writes: >> 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.
Yep, that is the goal! Maybe this is what you meant by "ordering problem", but when you look at this kind of scheduling problem, then I imagine that it has strong parallels to the job done by a normal compiler targeting a normal CPU. There you have a fixed number of pipelines which allow you to do a limited set of operations in parallel. And I imagine that a good compiler will be able to schedule a * b * c * d with a*b in one pipeline and c*d in another. >> 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. Right, if the hanging expressions are add/sub, then they shouldn't count when calculating the height of the tree. If we only count multiplications, then the height of the tree corresponds to network round-trips, and those are what we want to minimize. -- Martin Geisler _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
