Re: [viff-devel] Vedr.: Small VIFF language parser
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. -- Janus Den 15/07/2008 kl. 16.49 skrev Martin Geisler: Janus Dam Nielsen [EMAIL PROTECTED] writes: Hi again, Heres the fruit of half a days work :) Analyzing the expression: sint n = (a * y + (1 - a) * x); Yields the following results: Final result: ((a * y )+ ((1 - a )* x )) cost: 30 (((a * y )+ x )- (x * a )) cost: 30 (((a * y )+ x )- (a * x )) cost: 30 (((a * y )- (a * x ))+ x ) cost: 30 (((y * a )+ x )- (a * x )) cost: 30 (((y * a )+ x )- (x * a )) cost: 30 ((a * y )+ (x - (x * a ))) cost: 30 (((y * a )- (a * x ))+ x ) cost: 30 (((y * a )- (x * a ))+ x ) cost: 30 (((a * y )- (x * a ))+ x ) cost: 30 ((a * (y - x ))+ x ) cost: 20 And lo and behold the last line reveals that the expression a * (y - x )+ x has the lowest cost. That is very cool! :-) From the output above it seems that you have taught your analyzer about the distributive law, that + and * are commutative. What about a - a == 0, and that 0 * a == 0? I don't know if those rules will help -- they might just blow up the search space... :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Vedr.: Small VIFF language parser
Janus Dam Nielsen [EMAIL PROTECTED] 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@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Vedr.: Small VIFF language parser
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 [EMAIL PROTECTED] 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@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Vedr.: Small VIFF language parser
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
Re: [viff-devel] Vedr.: Small VIFF language parser
Janus Dam Nielsen [EMAIL PROTECTED] writes: Hi again, Heres the fruit of half a days work :) Analyzing the expression: sint n = (a * y + (1 - a) * x); Yields the following results: Final result: ((a * y )+ ((1 - a )* x )) cost: 30 (((a * y )+ x )- (x * a )) cost: 30 (((a * y )+ x )- (a * x )) cost: 30 (((a * y )- (a * x ))+ x ) cost: 30 (((y * a )+ x )- (a * x )) cost: 30 (((y * a )+ x )- (x * a )) cost: 30 ((a * y )+ (x - (x * a ))) cost: 30 (((y * a )- (a * x ))+ x ) cost: 30 (((y * a )- (x * a ))+ x ) cost: 30 (((a * y )- (x * a ))+ x ) cost: 30 ((a * (y - x ))+ x ) cost: 20 And lo and behold the last line reveals that the expression a * (y - x )+ x has the lowest cost. That is very cool! :-) From the output above it seems that you have taught your analyzer about the distributive law, that + and * are commutative. What about a - a == 0, and that 0 * a == 0? I don't know if those rules will help -- they might just blow up the search space... :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
