Proof of Condition for Via Placement of Multi-terminal Nets

In this appendix, a proof for necessary condition 1 is provided (Fig. D.1).

Figure D.1 Portion of an interconnect tree.

Condition 1: If r_j > r_j+1, only a type-1 move for v_j can reduce the delay of a tree.

Proof:

Consider Fig. D.1, where the intertier via v_j (the solid square) can be placed in any direction d_e, d_s, and d_n within, respectively the interval $l_{d_{e}}$ $l_{d_{e}}$ , $l_{d_{s}}$ $l_{d_{s}}$ , and $l_{d_{n}}$ $l_{d_{n}}$ . For the tree shown in Fig. D.1 and removing the terms that are independent of v_j, (11.1) is

$\begin{array}{l} T_{w} & = \sum_{v_{i} \in U_{0 j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) \\ + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} (R_{u_{j}} (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + r_{v_{j}} l_{v_{j}} C_{d_{j}} + \frac{r_{v_{j}} c_{v_{j}} l_{v_{j}}^{2}}{2}), \end{array}$ $\begin{array}{l} T_{w} & = \sum_{v_{i} \in U_{0 j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) \\ + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} (R_{u_{j}} (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + r_{v_{j}} l_{v_{j}} C_{d_{j}} + \frac{r_{v_{j}} c_{v_{j}} l_{v_{j}}^{2}}{2}), \end{array}$ (D.1)

(D.1)

where

$C_{d_{j}} = \sum_{\forall k} C_{d v_{j} d_{k}} + c_{j + 1} (l_{d_{e}} + l_{d_{s}} + l_{d_{n}}) .$ $C_{d_{j}} = \sum_{\forall k} C_{d v_{j} d_{k}} + c_{j + 1} (l_{d_{e}} + l_{d_{s}} + l_{d_{n}}) .$ (D.2)

(D.2)

Suppose that a type-2 move is required, shifting v_j by x toward the d_e direction (the dashed square). Expression (11.1) becomes

${T'}_{w} = [\begin{array}{l} (\sum_{v_{i} \in U_{i j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} R_{u_{j}}) (c_{v_{j}} l_{v_{j}} + c_{j} x + C_{d_{j}}) + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} \\ \times [(r_{j} - r_{j + 1}) x C_{d_{j}} + r_{j + 1} l_{d_{e}} (C_{d_{j}} - \frac{1}{2} c_{j + 1} l_{d_{e}}) + r_{j} x (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + \frac{1}{2} (r_{v_{j}} c_{v_{j}} l_{v_{j}}^{2} + r_{j} c_{j} x^{2})] \end{array}] .$ ${T'}_{w} = [\begin{array}{l} (\sum_{v_{i} \in U_{i j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} R_{u_{j}}) (c_{v_{j}} l_{v_{j}} + c_{j} x + C_{d_{j}}) + \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} \\ \times [(r_{j} - r_{j + 1}) x C_{d_{j}} + r_{j + 1} l_{d_{e}} (C_{d_{j}} - \frac{1}{2} c_{j + 1} l_{d_{e}}) + r_{j} x (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + \frac{1}{2} (r_{v_{j}} c_{v_{j}} l_{v_{j}}^{2} + r_{j} c_{j} x^{2})] \end{array}] .$ (D.3)

(D.3)

For a type-2 move to reduce the weighted delay of the tree, shifting v_j should decrease T_w, or, equivalently, $Δ T = {T'}_{w} - T_{w} < 0$ $Δ T = {T'}_{w} - T_{w} < 0$ . Subtracting (D.1) from (D.3) yields

$Δ T = {\begin{array}{l} \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} [r_{j} x (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + R_{u_{j}} c_{j} x + r_{j + 1} l_{d_{e}} (C_{d_{j}} - \frac{c_{j + 1} l_{d_{e}}}{2}) \\ + (r_{j} - r_{j + 1}) x C_{d_{j}} + \frac{r_{j} c_{j} x_{j}^{2}}{2}] + \sum_{v_{i} \in U_{i j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} c_{j} x \end{array}} .$ $Δ T = {\begin{array}{l} \sum_{s_{p} \in P_{s_{p} v_{j}}} w_{s_{p}} [r_{j} x (c_{v_{j}} l_{v_{j}} + C_{d_{j}}) + R_{u_{j}} c_{j} x + r_{j + 1} l_{d_{e}} (C_{d_{j}} - \frac{c_{j + 1} l_{d_{e}}}{2}) \\ + (r_{j} - r_{j + 1}) x C_{d_{j}} + \frac{r_{j} c_{j} x_{j}^{2}}{2}] + \sum_{v_{i} \in U_{i j}} \sum_{s_{p} \in \bar{P_{s_{p} U_{i j}}}} w_{s_{p}} R_{u i j} c_{j} x \end{array}} .$ (D.4)

(D.4)

Since r_j > r_j+1 and $C_{d j} > (c_{j + 1} l_{d_{e}} / 2)$ $C_{d j} > (c_{j + 1} l_{d_{e}} / 2)$ from (D.2), (D.3) is always positive and a type-2 move cannot reduce the delay of a tree.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Appendix D. Proof of Condition for Via Placement of Multi-terminal Nets

Create new playlist

Sign In

Sign Up

Proof of Condition for Via Placement of Multi-terminal Nets

Table of Contents for
Appendix D. Proof of Condition for Via Placement of Multi-terminal Nets