Maybe this is too naive of an approach, but just from looking at the approximate width of the tree (~2), it seems like we could get a roughly 2x speedup from parallelizing the work. Is there an algorithm we could perform on the dependency tree to get a more accurate answer?
truenorthwest
For calculating the speedup improvement, we should be able to compare the before and after number of clocks needed to execute all of the instructions. In this case, we go from 10 to 5 clocks (assuming we can support at least 3 simultaneous instructions), so a 2x exact speedup.
Maybe this is too naive of an approach, but just from looking at the approximate width of the tree (~2), it seems like we could get a roughly 2x speedup from parallelizing the work. Is there an algorithm we could perform on the dependency tree to get a more accurate answer?
For calculating the speedup improvement, we should be able to compare the before and after number of clocks needed to execute all of the instructions. In this case, we go from 10 to 5 clocks (assuming we can support at least 3 simultaneous instructions), so a 2x exact speedup.
Here is an algorithm that might address your question: https://cs.stackexchange.com/questions/2524/getting-parallel-items-in-dependency-resolution/2525#2525, which could give you the answer if we assume each task take same time, and that there is no limit on number of instructions that can be parallelized.