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.