# Minimize the depth of a tree of computation

Assume you have a binary tree of additions, where each two nodes are added together until the root is the sum of all the nodes. For example:

   3   2  1   3
\ /    \ /
5      4
\    /
9


To minimize the depth of this tree is easy: I can just run DSW on it for instance. The reason I can do this is because the addition operator is commutative.

Now what happens if each node has a different operation? *, /, + or -? How can I find an optimal minimal depth of that computation tree? An example tree is shown below:

   3 * 2  1 - 3
\ /    \ /
6  /  -2
\    /
-3


What I have come up with so far is to check if each subtree consists of commutative operations only, and then I can move nodes around in that specific subtree. However, this is a very crude 1st order heuristic.

Is there work detailing how we can refactor equations in such a way that we can reduce the depth of a computation graph? This would allow for more parallelization of the code required to compute this tree.

Motivation: In my specific case, I am actually not doing this for software. I am building custom hardware to evaluate the arithmetic computation. So one of my optimization objectives is to reduce the hardware tree depth so that I reduce the latency of my pipeline computation.

• Do you need the refactoring of the tree to itself be parallelizable? – D.W. Jan 26 '16 at 5:37
• No, no. Just so I can implement the arithmetic operations in parallel when evaluating the tree itself. – mohsaied Jan 26 '16 at 15:39