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
      \    /

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
      \    /

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.