4
$\begingroup$

There is a complete binary tree with its leaves as components of some system enter image description here

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??

$\endgroup$
  • 1
    $\begingroup$ Is the input always a complete binary tree? Also, are the propagation times always integers? $\endgroup$ – TCSGrad May 7 '14 at 20:46
  • $\begingroup$ input is always a complete binary tree so it ask for no. of components in power of 2's and propagation time is integer always $\endgroup$ – sagar May 7 '14 at 20:52
  • $\begingroup$ How do you compute the total costs? $\endgroup$ – Raphael May 8 '14 at 7:28
  • $\begingroup$ The cost of adding delays into the system is given by the total amount of extra delay added to all the edges -Raphael $\endgroup$ – sagar May 8 '14 at 7:47
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ And here's an argument that it's minimal: It's clearly minimal in the 1-layer case. A sub-tree so-balanced may be considered as a single node. This reduces the problem until you have a single node. Lather and rinse to form an inductive proof. $\endgroup$ – Ian May 8 '14 at 6:16
1
$\begingroup$

As the tag suggests, this is a classic greedy algorithm. Some notations:

  • $ancestor(i, c)$ denotes the ancestor on the $i$-th level (root $R$ is at level 0)
  • $delay(c)$ denotes the propagation delay from $R$ to component $c$ (without addition of any delays)
  • $M = \max_{i} {delay(c_i)}$. In this example, $M = 12$ for component $c_4$ (= 4 + 2 + 6)

The idea is to compute the $delay(c_i)$ for all components $c_i$, and then assign the difference of delays between components to edges of the tree. I'm doing this via example:

$delay(c_1) = 8,\ delay(c_2) = 11,\ delay(c_3) = 8,\ delay(c_4) = \mathbf{12}$ $delay(c_5) = 5,\ delay(c_6) = 5,\ delay(c_7) = 7,\ delay(c_8) = 10$

That means, we have to adjust the edges of the tree such that the net propagation delay of each component is 12 (= $M$)

Now, the trick is to adjust the edges starting from the top level.

  • Add a delay of 1 to the left edge of $ancestor(1, c_1)$
  • Add a delay of 3 to the left edge of the parent of $c_1$
  • Add a delay of 4 to the left edge of the parent of $c_3$

After the three delay additions (net cost = 8) to the left subtree, the propagation delay to each component is now 12.

We repeat the same steps on the right sub-tree:

  • Add a delay of 2 to right edge of $R$
  • Add a delay of 5 to the left edge of $ancestor(1, c_5)$
  • Add a delay of 3 to the left edge of parent of $c_7$

Total cost = 8 + 10 = 18 of delays added to the tree, and you can verify that the propagation delay for each component is now 12, the same as $M$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.