patternMinor
Minimizing Cost by minimizing delay
Viewed 0 times
costdelayminimizing
Problem
There is a complete binary tree with its leaves as components of some system
The values from one node to another gives propagation time for a signal to propagate from one junction to another
For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires.
The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.
For example, one way to remove
clock skew from the tree to the right
would be to increase each edge so that it
has delay 6. This has cost 44.
Second way is to raise the costs
of all edges in the bottom layer to 6, all
edges in the middle layer to 5, and all
edges in the top layer to 4. This has cost
36.
One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the root
Is there any other way to get the best solution for minmizing cost to add delay??
The values from one node to another gives propagation time for a signal to propagate from one junction to another
For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires.
The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.
For example, one way to remove
clock skew from the tree to the right
would be to increase each edge so that it
has delay 6. This has cost 44.
Second way is to raise the costs
of all edges in the bottom layer to 6, all
edges in the middle layer to 5, and all
edges in the top layer to 4. This has cost
36.
One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the root
Is there any other way to get the best solution for minmizing cost to add delay??
Solution
You can do a lot better than a total delay of 36. In fact you can get a total delay of half that. The idea is to recursively adjust the delays from bottom up.
In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8.
At the start, the component delays, reading from the left are:
8, 11, 8, 12, 5, 5, 7, 10
In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.
After the first adjustments, the component delays are now
11, 11, 12, 12, 5, 5, 10, 10
Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.
After the second adjustments the delays are
12, 12, 12, 12, 10, 10, 10, 10
Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync.
So finally, the component delays are
12, 12, 12, 12, 12, 12, 12, 12
We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.
It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.
In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8.
At the start, the component delays, reading from the left are:
8, 11, 8, 12, 5, 5, 7, 10
In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.
After the first adjustments, the component delays are now
11, 11, 12, 12, 5, 5, 10, 10
Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.
After the second adjustments the delays are
12, 12, 12, 12, 10, 10, 10, 10
Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync.
So finally, the component delays are
12, 12, 12, 12, 12, 12, 12, 12
We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.
It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.
Context
StackExchange Computer Science Q#24503, answer score: 3
Revisions (0)
No revisions yet.