Proof:
Consider Fig. D.1, where the intertier via vj (the solid square) can be placed in any direction de, ds, and dn within, respectively the interval lde, lds, and ldn. For the tree shown in Fig. D.1 and removing the terms that are independent of vj, (11.1) is
Tw=∑vi∈U0j∑sp∈PspUij¯¯¯¯¯¯¯¯¯wspRuij(cvjlvj+Cdj)+∑sp∈Pspvjwsp(Ruj(cvjlvj+Cdj)+rvjlvjCdj+rvjcvjl2vj2), (D.1)
(D.1)
where
Cdj=∑∀kCdvjdk+cj+1(lde+lds+ldn). (D.2)
(D.2)
Suppose that a type-2 move is required, shifting vj by x toward the de direction (the dashed square). Expression (11.1) becomes
T'w=⎡⎣⎢(∑vi∈Uij∑sp∈PspUij¯¯¯¯¯¯¯¯¯wspRuij+∑sp∈PspvjwspRuj)(cvjlvj+cjx+Cdj)+∑sp∈Pspvjwsp×[(rj−rj+1)xCdj+rj+1lde(Cdj−12cj+1lde)+rjx(cvjlvj+Cdj)+12(rvjcvjl2vj+rjcjx2)]⎤⎦⎥. (D.3)
(D.3)
For a type-2 move to reduce the weighted delay of the tree, shifting vj should decrease Tw, or, equivalently, ΔT=T'w−Tw<0. Subtracting (D.1) from (D.3) yields
ΔT=⎧⎩⎨⎪⎪⎪⎪⎪⎪∑sp∈Pspvjwsp[rjx(cvjlvj+Cdj)+Rujcjx+rj+1lde(Cdj−cj+1lde2)+(rj−rj+1)xCdj+rjcjx2j2]+∑vi∈Uij∑sp∈PspUij¯¯¯¯¯¯¯¯¯wspRuijcjx⎫⎭⎬⎪⎪⎪⎪⎪⎪. (D.4)
(D.4)
Since rj > rj+1 and Cdj>(cj+1lde/2) from (D.2), (D.3) is always positive and a type-2 move cannot reduce the delay of a tree.