In chip design, a timing diagram shows the delays that result as signals propaga

Question

In chip design, a timing diagram shows the delays that result as signals propagate through the circuit. Below is a simple example of such a circuit where we are concerned with the time it takes a signal to propagate from the root to the leaves. The weight of an edge represents its length and we will assume that the time it takes a signal to reach a leaf from the root is proportional to the sum of the edge lengths between those nodes.

First, we want every path from the root to the leaves to have exactly the same distance. In such a case the circuit would have what we call zero skew. Moreover, we would like a zero skew circuit where the total edge length is minimized (which minimizes the excess wire added to create zero skew). The total edge length is the sum of the all of the lengths of all the edges in the graph.

Assume you are given a complete binary tree with n nodes and each edge(u, v) has an associated length, len(u, v). I want you to give a dynamic programming algorithm that increases the length of certain edges so that the resulting tree has zero skew and the total edge length is minimized. Give the running time of your algorithm and justify why it produces a zero skew tree with minimum total edge length.

Explanation / Answer

For a tree to have zero skew, its two subtrees must both have zero skew. The algorithm works bottom up: for every tree, run the algorithm recursively on its two subtrees. On the lowest level, a node has leaves a and b. Increase arg min(i{a,b}) l(i), such that l(a) = l(b). If the two subtrees A and B with the edges e(A) and e(B) pointing to
them have zero skew, increase arg min(i{A,B}) h(i) + le(i), where h(T) is the length of the root-to-tree path of tree T. In both cases, increase the edge by the absolute difference (between A and B) of the sum of the complete height of the subtree plus the length of the edge pointing to the subtree.

Pseudocode:

The psuedocode shows the function zeroSkew whose input is the node T (root of the tree). We denote the child nodes of T with A and B. lT;A is the length of the edge between T and its child node A. We consider a node with only one child node to be zero skew. Such a child node must be a leaf, because the binary tree is complete.

if T has no children then
return 0
else if T has only one child A then
return zeroSkew(A) + l(T(A))
end if
h(A) = zeroSkew(A)

h(B) = zeroSkew(B)

diff = h(A) + l(T(A)) - h(B) - l(T(B))

if diff < 0 then
l(T(A)) = l(T(A)) - diff
else if diff > 0 then
l(T(B)) = l(T(A)) + diff
end if
return h(A) + l(T(A))

Here we did a constant amount of computation for every node. Therefore, the runtime for
the algorithm in O(n), where n is the number of nodes in the tree.

The resulting tree has a minimal complete length, i.e. there is no other way of changing the lengths such that T has zero skew, since we are only allowed to increase the length of a node and because every subtree must have zero skew. Therefore, the best way to reduce the skew to zero is to work bottom up and to always increase the length of at most one of T's subtrees.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.