3.3.1. Gate Sizing¶

The gate sizing problem determines the scale factors for the gates on an \(n\)-stage path in order to minimize its delay. Figure 3.3 shows a generic path with \(n\) gates in series and load capacitance \(C_L.\) In stage \(i,\) \(1 \le i \le n,\) logic gate \(i\) has input capacitance \(C_i,\) logical effort \(g_i,\) electrical effort \(h_i,\) and parasitic delay \(p_i.\)

Figure 3.3: Generic \(n\)-stage path with \(n\) gates in series and capacitive load \(C_L.\)

The path delay of the \(n\)-stage path is the sum of the stage delays \(d_i\):

The path logical effort of the \(n\)-stage path is

the path electrical effort is

and the path parasitic delay is

Our goal is to minimize path delay \(D = \sum_{i=1}^n (g_i h_i) + P\) under the constraint of a constant path electrical effort \(H = C_L/C_1.\) Observe that constant \(H\) implies that path effort \(F = G H\) is constant, because all logical efforts \(g_i\) and, hence, \(G\) are constant. We invoke the Theorem of Arithmetic and Geometric Means to minimize path effort \(F = \sum_{i=1}^n f_i = \sum_{i=1}^n g_i h_i.\) Given a constant geometric mean \(\sqrt[n]{G H} = \sqrt[n]{f_1 f_2 \cdots f_n},\) the arithmetic mean of the stage efforts is minimized, and is equal to the geometric mean if all stage efforts are equal:

Therefore, the minimum path effort is

Since path parasitic delay \(P\) is constant for a given path, we conclude that the path delay of an \(n\)-stage path assumes its minimum

if and only if all stages bear the same effort \(\hat{f},\) equal to the \(n^{th}\) root of path effort \(F\):

Example 3.4: Delay of Logic Path

Consider a circuit for \(Y = A B + D.\) The AND gate is implemented with a NAND gate followed by an inverter, and the OR gate is implemented with a NOR gate followed by an inverter. The NAND gate shall be sized like a matched NAND gate and the load driven by output \(Y\) shall be \(C_L = 600\) capacitive units. Perform gate sizing to minimize the delay of the path.

We observe that the paths \(A \rightarrow Y\) and \(B \rightarrow Y\) are equal, whereas path \(D \rightarrow Y\) passes through the NOR gate and the NOR inverter only. Thus, we assume that the path of interest is \(A \rightarrow Y,\) because it incurs the largest delay. Path \(B \rightarrow Y\) has the same delay, and the delay of \(D \rightarrow Y\) is smaller.

Our plan is to determine the minimum path delay, and then derive the gate sizes from the associated stage effort. To simplify the notation, we enumerate the gates on the path: the NAND gate is gate 1, the inverter gate 2, the NOR gate is gate 3, and the second inverter is gate 4. The path consists of \(n=4\) gates. Therefore, the minimum path delay is

\[\hat{D} = 4 F^\frac{1}{4} + P\,.\]

To determine path effort \(F = G H,\) we need to determine path logical effort \(G\) and path electrical effort \(H.\) The path electrical effort is the ratio of load capacitance \(C_L\) and input capacitance \(C_{in}(A).\) The input capacitance of the matched NAND gate is \(C_1 = C_{in}(A) = 4\) units, cf. Figure 1.48. Thus, we find

\[H = \frac{C_L}{C_1} = \frac{600}{4} = 150\,.\]

The path logical effort is the product of the gate logical efforts:

\[\begin{eqnarray*} G &=& g_1 \cdot g_2 \cdot g_3 \cdot g_4 \\ &=& g_{nand} \cdot g_{inv} \cdot g_{nor} \cdot g_{inv} \\ &=& \frac{4}{3} \cdot 1 \cdot \frac{5}{3} \cdot 1 \\ &=& \frac{20}{9}\,. \end{eqnarray*}\]

Thus, the path effort is \(F = G H = 1000/3 = 333.3.\) Together with path parasitic delay

\[\begin{eqnarray*} P &=& p_1 + p_2 + p_3 + p_4 \\ &=& p_{nand} + p_{inv} + p_{nor} + p_{inv} \\ &=& 2 + 1 + 2 + 1 \\ &=& 6\,, \end{eqnarray*}\]

we obtain a minimum path delay of \(\hat{D} = 4 \cdot 333.3^{1/4} + 6 = 23.1\) units.

To achieve minimum path delay, all four stages must bear the same stage effort \(\hat{f} = F^{1/4} = 4.27.\) This constraint enables us to determine the gate sizes. The NAND gate in the first stage is a matched gate with scale factor \(\gamma_1 = 1,\) as required by the problem formulation. The stage effort of the NAND gate is

\[f_1 = g_{nand} h_1 = \frac{4}{3}\,\frac{C_2}{C_1} = \frac{C_2}{3}\,,\]

because the matched NAND gate has input capacitance \(C_1 = 4.\) For minimum path delay, the stage effort must be \(f_1 = \hat{f},\) such that \(C_2 = 3\,\hat{f}.\) Thus, the scale factor for the stage-2 inverter must be

\[\gamma_2 = \frac{C_2}{C_{inv}} = \frac{C_2}{3} = \hat{f} = 4.27\,,\]

because the reference inverter has input capacitance \(C_{inv} = 3.\) The stage effort of the inverter is

\[f_2 = g_{inv} h_2 = 1 \cdot \frac{C_3}{C_2} = \frac{C_3}{3 \hat{f}}\,.\]

Since minimum path delay requires \(f_2 = \hat{f},\) the input capacitance of the NOR gate is \(C_3 = 3 \hat{f}^2.\) Because the matched NOR gate has input capacitance \(C_{in}(nor) = 3 g_{nor},\) the scale factor of the NOR gate in stage 3 must be

\[\gamma_3 = \frac{C_3}{3 g_{nor}} = \frac{3 \hat{f}^2}{3 \cdot 5/3} = \frac{3}{5} 4.27^2 = 10.94\,.\]

The stage effort of the NOR gate is

\[f_3 = g_{nor} h_3 = \frac{5}{3} \frac{C_4}{C_3} = \frac{5}{9 \hat{f}^2} C_4\,.\]

Because the NOR gate must bear stage effort \(f_3 = \hat{f},\) we obtain the input capacitance of the stage-4 inverter, \(C_4 = (9/5) \hat{f}^3.\) The scale factor of the stage-4 inverter must be

\[\gamma_4 = \frac{C_4}{3 g_{inv}} = \frac{3}{5} \hat{f}^3 = 46.7\,.\]

Like all other gates, the stage-4 inverter must bear stage effort \(\hat{f}.\) Because \(f_4 = g_{inv} h_4 = C_L/C_4,\) we can check our arithmetic:

\[\begin{eqnarray*} \frac{C_L}{C_4} &\stackrel{!}{=}& \hat{f} \\ \Leftrightarrow\qquad C_L &=& \frac{9}{5} \hat{f}^4 = \frac{9}{5} 4.27^4 = 598.4\,, \end{eqnarray*}\]

which is equal to 600 within the accuracy of the arithmetic precision. Had we used additional fractional digits for the value of \(\hat{f},\) e.g. \(\hat{f} = 4.273,\) we would have obtained a more accurate arithmetic result.

Note that the scale factors do not form a geometric progression as for inverter chains with minimum path delay, see Example 3.3, because the logic path includes logical efforts. However, we may recognize the sequence as a geometric progression, weighted with logical efforts:

\[\gamma_1 = \hat{f}^0\,,\quad\gamma_2 = \hat{f}^1\,,\quad\gamma_3 = \frac{3}{5} \hat{f}^2\,,\quad\gamma_4 = \frac{3}{5} \hat{f}^3\,.\]

We would have arrived at the same scale factors by working backwards through the path, starting with the stage-4 inverter. We leave it as an exercise to double check that these scale factors yield the minimum path delay by first computing the individual stage delays \(d_i = g_i h_i + p_i,\) and then taking their sum \(\hat{D} = \sum_{i=1}^4 d_i.\)

Example 3.5: Inverter Path Length

We wish to drive a load capacitance of 1200 units, either with (a) a single buffer or (b) two back-to-back buffers. In both circuits the stage-1 inverter shall be a reference inverter. The remaining inverters may be sized for minimum delay.

Intuitively, we may prefer the shorter 2-stage path of option (a), expecting that two inverters have a smaller path delay than four. This is not always the case, however.

In Example 3.3 we minimize the delay of the 4-stage path in option (b). The smallest possible delay of the 4-inverter chain is \(\hat{D}_4 = 21.9\) delay units. The inverter pair of option (a) constitutes a 2-stage path. According to Equation (2), the minimum path delay with load \(C_L = 1200\) and input capacitance \(C_1 = 3,\) i.e. \(F = H = C_L/C_1 = 400,\) is

\[\begin{eqnarray*} \hat{D}_2 &=& n F^\frac{1}{n} + n \\ &=& 2 \sqrt{400} + 2 \\ &=& 42 \end{eqnarray*}\]

delay units. We find that the minimum delay of the 2-stage path \(\hat{D}_2 = 42\) is almost two times larger than the minimum delay of the 4-stage path \(\hat{D}_4 = 21.9.\) The next section on path sizing offers the background that puts this result into perspective.

3.6

Minimize the delay of the 3-stage path using the method of logical effort.

1. Compute minimum path delay \(\hat{D}.\)
2. Compute the scale factors \(\gamma_{nand}\) and \(\gamma_{nor}.\)

3.3.2. Path Sizing¶

The path sizing problem determines the best number of stages for a path in order to minimize its delay. As a concrete example, consider the inverter chain with \(n\) inverters and load \(C_L\) shown in Figure 3.4.

Figure 3.4: An \(n\)-stage inverter chain.

Given the number of stages \(n\) and path electrical effort \(H=C_L/C_1,\) we can minimize the path delay through gate sizing. According to Equation (2), the minimum path delay of a chain with \(n\) inverters is

Figure 3.5 plots the minimum path delay as a function of the number of stages \(n\) for fixed path electrical effort \(H = 400.\) Note that the minimum path delay \(\hat{D}(n)\) assumes the minimum \(\hat{D}(n^\star) = 21.57\) for a number of stages \(n^\star = 5.\) Whereas gate sizing enables us to find a local minimum of the path delay for a given number of stages \(n,\) finding the global minimum of the path delay requires optimizing the number of stages \(n.\)

Given path electrical effort \(H,\) we determine the best number of stages \(n^\star\) by minimizing \(\hat{D}(n).\) We determine the minimum using calculus by deriving \(\hat{D}\) w.r.t. \(n\) for fixed \(H\):

Function \(\hat{D}(n)\) has a minimum where its derivative is zero. Call the best stage effort \(f^\star = H^{1/n^\star}\) the stage effort with path electrical effort \(H\) when using the best number of stages \(n^\star.\) This is the stage effort where \(\hat{D}(n)\) is minimal, i.e. where derivative \(d \hat{D}/d n\) equals zero:

We have arrived at an equation for best stage effort \(f^\star\) that has no closed-form solution. However, we can compute \(f^\star\) numerically, for example with Newton’s method for finding zeros. In case of Equation (3), we want to find \(x\) such that function \(g(x)= x (\ln x - 1) - 1\) is zero. With derivative \(g'(x) = \ln x,\) we obtain the Newton iteration with iteration index \(i\):

Iterating with a suitable starting value, e.g. \(x_0 = 4,\) produces result \(x \approx 3.59.\) Thus, Equation (3) holds for best stage effort

which enables us to derive the best number of stages

because \(H = {f^\star}^{n^\star}\) by definition and \(\ln H = n^\star \ln f^\star.\)

This result is very useful. First, since each inverter on the path must bear best stage effort \(f^\star = 3.59,\) we know how to derive the scale factors for sizing each of the inverters in geometric progression. Second, given a path with electrical effort \(H,\) we find the best number of stages by taking the logarithm of \(H\) to base 3.59. Table 3.1 lists path efforts and the corresponding best number of stages. The numbers are rounded for ease of reading. For more accurate numerical results, use the path sizing calculator below the table. Table 3.1 is suited to look up the best number of stages for a given path effort \(F,\) which equals the path electrical effort \(H\) in an inverter chain with \(G=1.\) For example, using one stage is best for path efforts \(F\) up to 5.8. For efforts in range \(5.8 \le F \le 22.3,\) a 2-stage design is best, and so on. Path effort \(F=400\) of Example 3.5 lies between 300 and 1090, where \(n^\star = 5\) stages yield the fastest inverter chain.

Table 3.1 also includes the minimum path delay \(\hat{D}(n^\star)\) for the given path efforts. For example, given \(F=300,\) a 4-stage path yields \(\hat{D}(4) = 4 \sqrt[4]{300} + 4 = 20.6,\) as does a 5-stage path, \(\hat{D}(5) = 5 \sqrt[5]{300}+ 5 = 20.6.\) Furthermore, the right-most column lists the corresponding stage efforts \(\hat{f} = F^{1/n^\star}.\) For example, consider 5-stage inverter chains, which yield the smallest delay for path efforts in range \(300 \le F \le 1090.\) At the lower end, for \(F=300,\) the stage effort with minimum delay is \(\hat{f} = \sqrt[5]{300} = 3.1\) delay units, and at the upper end for \(F=1090,\) the stage effort is \(\hat{f} = \sqrt[5]{1090} = 4.1\) delay units. The best stage effort \(f^\star = 3.59\) of a 5-stage inverter chain produces the minimum delay for path effort \(F = {f^\star}^5 = 596.\)

Example 3.8: Path Sizing of Logic Circuit

Consider the circuit in Example 3.4 with a larger capacitive load of \(C_L = 3240\) units. We can increase the path length of a circuit by inserting buffers (inverter pairs) between its output and the load. Perform path sizing and determine the minimum path delay of the circuit.

Path \(A \rightarrow Y\) of the circuit in Example 3.4 has a matched NAND gate with input capacitance \(C_1 = 4\) in stage 1. Therefore, the path must bear electrical effort \(H = C_L/C_1 = 810.\) Since an inverter has logical effort \(g_{inv}=1,\) the circuit has path electrical effort \(G = g_{nand} \cdot g_{nor} = 20/9,\) no matter how many inverters we insert on the path. Since the path electrical effort is also independent of the number of additional inverter stages, the extended path must bear path effort \(F = G H = 1800.\) The path sizing calculator prescribes using 6 stages, or inserting two inverters at output \(Y.\)

The minimum delay of path \(A \rightarrow Y\) is \(\hat{D} = 6 F^{1/6} + P = 6 \cdot 1800^{1/6} + 8 = 28.927,\) which exceeds the minimum delay of a 6-stage inverter chain, given by the path sizing calculator, by 2 parasitic delay units due to the NAND and NOR gates.

3.7

Minimize the delay of the inverter chain by path sizing.

1. Compute \(\hat{f}\) of the 3-stage inverter chain.
2. Determine the best number of stages \(n^\star.\)
3. Compute the minimum path delay \(\hat{D}\) of the path-sized inverter chain.

3.5.1. Fork Delay¶

We study \(n\)-forks with an \(n\)-stage leg and an \((n-1)\)-stage leg as shown in Figure 3.8, strictly speaking for \(n \ge 2.\) We assume that the on-path electrical efforts for the legs are given as \(H_1\) for leg 1 and \(H_2\) for leg 2. We express the load capacitances of the legs as a function of fork input capacitance \(C_{in}.\) Leg 1 is the \(n\)-stage leg. The stage-1 inverter of leg 1 has input capacitance \(C_1\) and load capacitance \(C_{L,1} = H_1 C_{in}.\) Leg 2 is the \(n-1\)-stage leg. Its stage-1 inverter has input capacitance \(C_2,\) and the load capacitance is \(C_{L,2} = H_2 C_{in}.\) From the perspective of the fork input, the legs present a parallel composition of input capacitances, so that

Since a fork branches into two legs, the path effort of leg 1 is

and of leg 2

If we replace the fork with an equivalent circuit, the equivalent circuit has input capacitance \(C_{in}\) and output capacitance \(C_L = C_{L,1} + C_{L,2} = (H_1 + H_2) C_{in}.\) Thus, the electrical effort of the entire fork or its equivalent circuit is \(H = C_L/C_{in} = H_1 + H_2.\)

Figure 3.8: An \(n\)-fork with input capacitance \(C_{in} = C_1 + C_2\) and load capacitance \(C_L = (H_1 + H_2) C_{in}.\)

To keep things simple, we begin our study of forks by assuming that the capacitive loads of both legs are equal, i.e. \(C_{L,1} = C_{L,2} = H_l C_{in},\) where leg electrical effort \(H_l = H_1 = H_2.\) Thus, the total load of the fork is \(C_L = 2 H_l C_{in}.\) The path efforts of the legs, \(F_1 = H_l C_{in}/C_1\) and \(F_2 = H_l C_{in}/C_2,\) may differ, depending on the choice of leg input capacitances \(C_1\) and \(C_2.\) In fact, since the lengths of the legs differ by one stage, the longer leg 1 can support a larger path effort than the shorter leg 2. Given equal load capacitances, we may increase the path effort of leg 1 by reducing \(C_1.\) If we require a constant input capacitance \(C_{in},\) decreasing \(C_1\) must be balanced by increasing \(C_2.\) A shift of input capacitance between the two legs corresponds to a proportional shift in the division of the drive current between the legs. Experiment 3.5 allows you to vary the input capacitances \(C_1\) and \(C_2\) of the legs, and observe the effect on the fork delay.

The key observation for minimizing the fork delay in Experiment 3.5 is that the allocation of input capacitance \(C_{in}\) to leg input capacitances \(C_1\) and \(C_2\) matters. Of course, this fact applies to any branching circuit, not only to forks. In case of a fork with equal loads, the correlation between the input capacitances when keeping \(C_{in} = C_1 + C_2\) constant enables us gain additional insight into the the cause of the fork delay. The delay of an \(n\)-stage inverter chain is minimal, if each stage bears the same effort \(\hat{f} = \sqrt[n]{H}.\) Each leg of a fork is an inverter chain. If we size the inverters to minimize the leg delays, we obtain minimum delay \(\hat{D}_1(n) = n \sqrt[n]{F_1} + n\) for leg 1, and minimum delay \(\hat{D}_2(n-1) = (n-1) \sqrt[n-1]{F_2} + (n-1)\) for leg 2. We may be satisfied with a delay of the fork that is the maximum of the independently minimized leg delays, \(\max(\hat{D}_1, \hat{D}_2).\) However, we can do better by recognizing that the minimum fork delay occurs if the leg delays are equal. If they are not, we can reduce the larger leg delay at the expense of increasing the smaller delay of the other leg.

Figure 3.9: Minimize the delay of a 3-fork by shifting path efforts between the legs.

Figure 3.9 illustrates the idea for a 3-fork with leg electrical effort \(H_l = H_1 = H_2 = 25\) and input capacitance \(C_{in} = 12.\) In this case, the load capacitances are \(C_{L,1} = C_{L,2} = 300.\) First, assume that the legs present equal loads of \(C_1 = C_2 = C_{in}/2 = 6\) capacitive units each. Then, both legs bear equal path efforts \(F_1 = F_2 = 50.\) The plot shows the minimum path delays \(\hat{D}_1(3)\) of the 3-stage leg and \(\hat{D}_2(2)\) of the 2-stage leg as a function of path effort \(F.\) For \(F = 50,\) 3-stage leg 1 has minimum delay \(\hat{D}_1(3) = 14.05,\) and is faster than 2-stage leg 2 with minimum delay \(\hat{D}_2(2) = 16.14.\) The fork delay is dominated by leg 2. We can minimize the fork delay by reducing path effort \(F_2\) of leg 2 at the expense of increasing path effort \(F_1\) of leg 1 to honor the constraint \(C_{in} = C_1 + C_2.\) When reducing \(F_2 = C_{L,2}/C_2\) by increasing input capacitance \(C_2\) of leg 2, we reduce \(C_1\) by the same amount. In turn, the reduction of \(C_1\) increases \(F_1 = C_{L,1}/C_1\) and, consequently, leg delay \(\hat{D}_1(3).\) The fork delay is minimal when the leg delays are equal, \(\hat{D}_1(3) = \hat{D}_2(2).\) In Figure 3.9 this occurs when \(F_1 = 62.5\) and \(F_2 = 41.6.\) The corresponding input capacitances are \(C_1 = 4.8\) for leg 1 and \(C_2 = 7.2\) for leg 2. As a result the minimum fork delay amounts to \(14.9\) delay units.

We can determine the leg input capacitances for minimum fork delay by formalizing the idea of shifting input capacitance between the legs. To that end, we introduce skew factor \(\boldsymbol{\alpha}\) in range \(0 < \alpha < 1,\) and express the leg input capacitances as fractions of the fork input capacitance:

such that \(C_1 + C_2 = C_{in}.\) Now, the path efforts are correlated through skew factor \(\alpha.\) For leg 1 we have \(F_1 = H_1/\alpha,\) and for leg 2 \(F_2 = H_2/(1-\alpha).\) The key insight for minimizing the fork delay is to equalize the leg delays rather than minimizing the leg delays independently:

Given leg electrical efforts \(H_1\) and \(H_2\) for an \(n\)-fork, even in the special case with equal loads, \(H_1 = H_2 = H_l,\) this constraint presents a nonlinear equation in \(\alpha.\) Solving this equation for \(\alpha\) analytically is difficult for arbitrary \(n.\) We could determine \(\alpha\) numerically, for example by means of a Newton iteration. Alternatively, we can reduce the problem of computing \(\alpha\) to finding the roots of a polynomial, for which solutions exist as part of mathematical software packages like Octave or Mathematica with online portal WolframAlpha.

3.5.2. 1d-Analysis Method¶

The method of logical effort does not require explicit use of skew factor \(\alpha\) to derive the minimum fork delay. We demonstrate this derivation by means of the 3-fork in Figure 3.10 below. First, we apply the key insight of the method of logical effort, i.e. a path achieves minimum delay if all stages bear the same effort. This insight enables us to allocate stage efforts to each inverter as follows. Consider the 3-stage leg of the 3-fork, and think of the stage effort as effort delay in units of time. If the effort delay of the whole leg is \(d_1,\) then each of the 3 stages must have effort delay \(d_1/3\) to minimize the path delay. Analogously, if the 2-stage leg has effort delay \(d_2,\) then each stage must have effort delay \(d_2/2\) to minimize the path delay. Then, the leg delays are

Second, we apply our key insight about minimizing fork delay, i.e. both legs must have equal path delay. In case of the 3-fork, we demand

This equality is satisfied by an effort delay \(d,\) if \(d_1 = d\) and \(d_2 = d + 1,\) because

Figure 3.10 annotates the inverters with the effort delays that yield minimum fork delay as a function of delay \(d.\)

Figure 3.10: 3-fork with effort delay allocation.

Two aspects of the effort delay allocation in Figure 3.10 deserve a closer look. First, the effort delays minimize the fork delay by equalizing the leg delays, which determines skew factor \(\alpha\) implicitly, and by minimizing the path delay of each leg, because each gate on a leg bears the same stage effort. To solve the delay minimization problem, we merely need to determine the value of \(d.\) Second, our algebraic parameterization of leg effort delays \(d_1(d) = d\) and \(d_2(d) = d+1\) may be viewed as compensating for one unit of parasitic delay on leg 1 with one unit of effort delay on leg 2. The path parasitic delay of leg 1 is \(P_1 = 3 p_{inv} = 3,\) whereas leg 2 has path parasitic delay \(P_2 = 2 p_{inv} = 2.\) We call the difference \(\Delta p = P_1 - P_2 = 1\) in \(d_2(d) = d + \Delta p\) the parasitic delay compensation, because it compensates the excess parasitic delay of leg 1 with effort delay in leg 2.

Next, we analyze the delay of the fork legs as a function of \(d.\) The effort delay of an inverter, \(f = g_{inv} h,\) is equal to the electrical effort, because the logical effort is \(g_{inv} = 1.\) Thus, for the inverters of leg 1, we find for the stage-1 inverter effort delay

for the stage-2 inverter effort delay

and for the stage-3 inverter effort delay

Note that the product of the right-hand sides is a telescoping product. Therefore, multiplying the equations yields

Analogously, for the inverters of leg 2, we find the effort delay of the stage-1 inverter

the effort delay of the stage-2 inverter

and the product of the equations

The input capacitance of the fork is the sum of the leg input capacitances. Substituting the expressions in Equation (7) and Equation (8) for \(C_1\) and \(C_2,\) we find

Rearranging the equality we obtain a polynomial in variable \(d\):

The solutions to this equation are the roots of the polynomial, i.e. those values of \(d\) where the polynomial is zero. A polynomial of degree 5 has 5 roots. Given \(H_1\) and \(H_2,\) we can determine the roots with a mathematical software package like WolframAlpha. For \(H_1 = H_2 = 25,\) copy or type this equation:

d^5 + 2 d^4 + (1 - 4 * 25) d^3 - 27 * 25 d^2 - 54 * 25 d - 27 * 25 = 0

into the WolframAlpha input form and click the equal sign.

WolframAlpha returns the roots:

Root \(d_3\) is the only feasible solution for effort delay \(d,\) which must be a positive real number to qualify as a time. Knowing that \(d = 11.91,\) we can deduce the design parameters of our fork. The 3-fork has a minimum delay of \(\hat{D}_1(3) = \hat{D}_2(2) = d + 3 = 14.91\) delay units, if we scale the stage-1 inverters of the legs to present input capacitances \(C_1 = 4.8\) according to Equation (7), \(C_2 = 7.2\) according to Equation (8), and all other inverters for the input capacitances derived above. Note that skew factor \(\alpha = C_1/C_{in} = 0.4,\) although we do not need to know \(\alpha\) to minimize the fork delay. Experiment 3.5 enables you to verify our fork design.

The methodology for deriving the parameters of a fork with minimum delay generalizes to branching circuits with two legs. We call it the 1d-analysis method, because it is based on finding the roots of a univariate polynomial with effort delay \(d\) as the only variable.

1d-Analysis Method

Given a branching circuit with an \(n\)-stage leg 1 and an \(m\)-stage leg 2, input capacitance \(C_{in} = C_1 + C_2,\) and load capacitances \(H_1 C_{in}\) and \(H_2 C_{in}.\) Follow these steps to minimize the circuit delay:

1. Determine the leg parasitic delays \(P_1\) and \(P_2.\)

2. Without loss of generality, assume that \(P_1 \ge P_2,\) and parasitic delay compensation \(\Delta p = P_1 - P_2.\) Allocate effort delay \(d/n\) to each stage of leg 1 and \((d+\Delta p)/m\) to each stage of leg 2.

3. Form the telescoping products of the leg effort delays, including logical efforts:

   \[\Bigl(\frac{d}{n}\Bigr)^n = \frac{G_1 H_1 C_{in}}{C_1}\,,\qquad \Bigl(\frac{d+\Delta p}{m}\Bigr)^m = \frac{G_2 H_2 C_{in}}{C_2}\,.\]

   Substitute leg input capacitances \(C_1\) and \(C_2\) in the branch constraint \(C_{in} = C_1 + C_2\) to derive a univariate polynomial and determine its roots:

   \[d^n (d + \Delta p)^m - m^m G_2 H_2 d^n - (d + \Delta p)^m n^n G_1 H_1 = 0\,.\]

4. Identify the positive real root \(d\) that solves our problem, and determine the scale factors of all gates. The minimum circuit delay is \(d + P_1 = (d + \Delta p) + P_2.\)

The 1d-analysis method enables us to analyze the 1-fork with a 0-stage leg and equal loads in Figure 3.11. The unassuming circuit designer might be tempted to use this degraded fork to generate the complemented and uncomplemented input. However, a 1-fork is rarely a good circuit to use.

Figure 3.11: A 1-fork cannot equalize leg delays.

According to the 1d-analysis method, we assign effort delay \(d\) to the inverter in leg 1. Then, leg 1 has delay \(D_1 = d + 1\) and leg 2 has delay \(D_2 = 0.\) Note that negative effort delay \(d = -1\) would be required to equalize the leg delays. Furthermore, the effort delay of leg 1 is \(d = H_l C_{in}/C_1,\) and the input capacitance of leg 2 is the load capacitance, \(C_2 = H_l C_{in}.\) Thus, the branch constraint yields

Since CMOS inverters have a positive effort delay, \(d > 0,\) we conclude that \(1 - H_l > 0,\) and obtain the constraint on the leg electrical effort:

This constraint determines the input capacitance of the inverter in leg 1. For example, leg electrical effort \(H_l = 3/4\) yields

In terms of \(C_1,\) we can express leg load \(H_l C_{in} = (3/4) C_{in} = 3 C_1\) and input capacitance \(C_{in} = 4 C_1.\) Thus, all capacitances of the 1-fork are determined by choosing \(H_l.\) As a consequence, effort delay \(d\) of the inverter in leg 1 is \(d = 3 C_1 / C_1 = 3,\) and the delay of leg 1 is \(D_1 = d + p_{inv} = 4\) time units. This style of 1d-analysis shows that the 1-fork is effective for \(H_l \approx 1/2.\) However, if \(H_l\) approaches value 1, the inverter has to stem an infinitely large effort. The underlying problem is that the 1-fork has only one inverter to equalize the leg delays. Therefore, as a rule of thumb, it is rarely a good idea to use a 1-fork. Use a 2-fork instead.

3.11

Use the 1d-analysis method to minimize the delay of the 2-fork assuming \(H_1 = 10\) and \(H_2 = 15.\)

1. Determine the leg parasitic delays and allocate effort delays using one parameter \(d.\)
2. For each leg, form the products of the effort delays, and derive a polynomial in \(d.\)
3. Determine the root of the polynomial and the minimum leg delays \(\hat{D}_1\) and \(\hat{D}_2.\)

The 2-fork has two inverters on leg 1 and one inverter on leg 2. The parasitic delay of leg 1 is \(P_1 = 2 p_{inv} = 2\) and of leg 2 \(P_2 = p_{inv} = 1.\) The difference

\[\Delta p = P_1 - P_2 = 1\]

is the parasitic delay compensation that we allocate in the stage effort assignments to balance the leg delays.

Assuming that leg 1 has a total effort delay of \(d,\) we allocate stage effort delay \(d/2\) to each of the two inverters, because path delay is minimized if all stages bear the same effort. Since leg 2 has a single stage only, the inverter has to bear all of the path effort plus the parasitic delay compensation, which amounts to stage effort \(d+1\) for the inverter in leg 2.

Given the allocation of effort delays, we form the products of the stage effort delays, which are simple expressions because the product of the stage electrical efforts telescopes. For leg 1, we obtain

\[\Bigl(\frac{d}{2}\Bigr)^2 = \frac{H_1 C_{in}}{C_1}\,.\]

Leg 2 has one stage only, and the stage effort equals the electrical effort because \(g_{inv} = 1\):

\[d+1 = \frac{H_2 C_{in}}{C_2}\,.\]

We rearrange these equations to obtain expressions for \(C_1\) and \(C_2\):

\[C_1 = \frac{4 H_1}{d^2} C_{in}\,,\qquad C_2 = \frac{H_2}{d+1} C_{in}\,.\]

Next, we substitute \(C_1\) and \(C_2\) in the branch constraint, \(C_{in} = C_1 + C_2,\) and rearrange the equation into a polynomial:

\[\begin{eqnarray*} C_{in} &=& C_1 + C_2 \\ C_{in} &=& \frac{4 H_1}{d^2} C_{in} + \frac{H_2}{d+1} C_{in} \\ d^2 (d+1) &=& 4 H_1 (d+1) + H_2 d^2 \\ d^3 + (1 - H_2) d^2 - 4 H_1 d - 4 H_1 &=& 0\,. \end{eqnarray*}\]

Effort delay \(d\) is a root of the polynomial

\[d^3 - 14 d^2 - 40 d - 40\,,\]

given \(H_1 = 10\) and \(H_2 = 15.\) This polynomial has two complex roots and one real root:

\[d = 16.56\,.\]

Therefore, leg 1 has a delay of \(\hat{D}_1 = d + P_1 = 16.56 + 2 = 18.56\) time units and leg 2 has the same delay \(\hat{D}_2 = (d+1) + P_2 = 17.56 + 1 = 18.56\) time units.

Solution

3.6.1. Path Sizing Branches¶

In Section Forks, we minimize the delay of a 3-fork. We did not ask whether the 3-fork has appropriate leg lengths, or whether a 2-fork or 4-fork would result in an even smaller delay for the given load. In the following, we examine the path sizing problem for a branching circuit if both legs are inverter chains of equal length, see Figure 3.12.

Figure 3.12: A branching circuit with two \(n\)-stage legs, input capacitance \(C_{in} = C_1 + C_2\) and load capacitance \(C_L = (H_1 + H_2) C_{in}.\)

If the electrical efforts of the legs were equal, \(H_l = H_1 = H_2,\) the circuit is symmetric. We would choose equal leg input capacitances, \(C_1 = C_2,\) to supply both legs with equal drive currents. According to the branch constraint, \(C_{in} = C_1 + C_2,\) and given input capacitance \(C_{in},\) we scale the stage-1 inverters of the legs such that \(C_1 = C_2 = C_{in}/2.\) Since both legs bear the same electrical effort, we can determine the best number of stages \(n\) using the path sizing calculator with path effort \(F = 2 H_l.\)

In general, the leg electrical efforts may differ such that \(H_1 \ne H_2.\) According to the method of logical effort, we minimize the delay of each leg, independently, if each inverter stage of a leg bears the same effort. For leg 1, given path effort \(F_1 = G_1 B_1 H_1 = C_{L,1}/C_1,\) the stage effort that minimizes the leg delay is \(\hat{f}_1 = \sqrt[n]{C_{L,1}/C_1}.\) Analogously, the stage effort for leg 2 is \(\hat{f}_2 = \sqrt[n]{C_{L,2}/C_2}.\) To minimize the delay of the entire branching circuit we equalize the leg delays, a lesson we have learned from the design of forks.

Since both legs have the same number of stages \(n,\) this constraint simplifies to

We find that we can minimize the branch delay by choosing the leg input capacitances proportional to the leg electrical efforts. Given the branch constraint with input capacitance \(C_{in} = C_1 + C_2,\) we obtain the leg input capacitances:

Furthermore, Equation (9) yields

i.e. we minimize the delay of the branching circuit, if the stage efforts in the two legs are equal.

Let us contemplate the solution to the path sizing problem for the branching circuit in Example 3.13: We scale the input capacitances of the stage-1 inverters in proportion to the path electrical efforts. As a result, we equalize the path efforts of the legs, which enables us to determine the path lengths of both legs simultaneously, as if we were sizing a single path. This observation motivates us to introduce the concept of an equivalent inverter path, in analogy to equivalent resistive and capacitive networks. Figure 3.13 shows the equivalent inverter path of the branching circuit in Figure 3.12 with input capacitance \(C_{in}\) and the sum of the leg electrical efforts \(H_1 + H_2\) as path electrical effort.

Figure 3.13: Equivalent inverter path of the branching circuit in Figure 3.12.

The equivalent inverter path enables us to reduce the path sizing problem for a branching circuit to that of a multistage path as discussed in Section Path Sizing. Once we have determined the best number of stages, we proceed by employing Equation (9) to scale the stage-1 inverters of the legs, and perform gate sizing according to the method of logical effort to minimize the path delay of the branching circuit. This method generalizes to branching circuits with arbitrary logic gates, if we replace the leg electrical efforts with the leg path efforts to account for the leg logical efforts.

For branching circuits with logic gates on the legs, the path efforts of the legs are:

Assume that leg 1 has \(n\) stages and leg 2 has \(m\) stages. Then, equalizing the leg delays to minimize the delay of the branching circuit yields the constraint:

In the special case for legs with equal lengths, \(n = m,\) and equal path parasitic delays, \(P_1 = P_2,\) this constraint simplifies to

Then, the branch constraint, \(C_{in} = C_1 + C_2,\) enables us to size the stage-1 gates of the legs such that the input capacitances are

The equivalent inverter path of this branching circuit has load capacitance \(C_L = (G_1 H_1 + G_2 H_2) C_{in}.\)

In case where both legs have the same number of stages but different parasitic delays, we may assume that Equation (10) holds approximately:

If the number of stages differ, we may append inverter pairs to the shorter leg until the path lengths differ by at most one stage. Then, Approximation (11) may still be accurate enough to permit path sizing of the equivalent inverter path with load \(C_L = (G_1 H_1 + G_2 H_2) C_{in}.\) If the best number of stages requires increasing the leg lengths, we can accomplish the task by appending inverter pairs. Otherwise, if the best path length is smaller, we may redesign the logic on the legs to reduce the number of stages or settle with a suboptimal design.

Example 3.14: Branch Design with Logic

We wish to minimize the delay of the the branching circuit in Figure 3.14 with path electrical efforts \(H_1 = 9\) and \(H_2 = 15.\)

Figure 3.14: A branching circuit with logic gates on its legs.

We begin by deriving the path logical efforts and path parasitic delays of the legs. Figure 3.14 annotates each gate with its logical effort and parasitic delay. The path logical efforts of the legs are the products of their gate logical efforts:

\[G_1 = \frac{4}{3} \cdot \frac{7}{3} \cdot 1 = \frac{28}{9}\,,\qquad G_2 = 1 \cdot \frac{5}{3} \cdot 1 = \frac{5}{3}\,.\]

The path parasitic delays of the legs are the sums of their gate parasitic delays:

\[P_1 = 2 + 3 + 1 = 6\,,\qquad P_2 = 1 + 2 + 1 = 4\,.\]

We notice that both legs have 3 stages but different path parasitic delays. The equivalent inverter path enables us to determine the best number of stages approximately. The equivalent inverter path has input capacitance \(C_{in}\) and load capacitance

\[C_L = (G_1 H_1 + G_2 H_2) C_{in} = \Bigl(\frac{28}{9} \cdot 9 + \frac{5}{3} \cdot 15\Bigr) C_{in} = 53 C_{in}\,.\]

Thus, the equivalent inverter path has path effort \(F = C_L/C_{in} = 53,\) for which the path sizing calculator prescribes a best number of stages of \(n = 3.\) Since both legs of the branching circuit have 3 stages already, we retain the logic without modifications. To minimize the delay, Approximation (11) permits estimating the input capacitances of the stage-1 gates of the legs as:

\[C_1 \approx \frac{G_1 H_1}{F} C_{in} = \frac{28}{53} C_{in}\,,\qquad C_2 \approx \frac{G_2 H_2}{F} C_{in} = \frac{25}{53} C_{in}\,.\]

Furthermore, if each of the gates bears stage effort \(\hat{f} \approx \sqrt[n]{F} = \sqrt[3]{53} = 3.765,\) then the path effort delay of the branching circuit is approximately \(3 \hat{f} = 11.3.\) Including the path parasitic delays, we estimate the delay of leg 1 to be \(\hat{D}_1(3) \approx 3 \hat{f} + P_1 = 17.3\) and the delay of leg 2 to be \(\hat{D}_2(3) \approx 3 \hat{f} + P_2 = 15.3.\) This approximation is easy to obtain on the back of an envelope.

Alternatively, with a little extra work, we apply the exact 1d-analysis method after determining path size \(n=3\) with the approximating equivalent inverter path. We find parasitic delay compensation \(\Delta p = 2,\) and assign effort delay \(d/3\) to each gate of leg 1 and \((d+2)/3\) to each gate of leg 2. We obtain the polynomial \(d^3 (d+2)^3 - 27 \cdot 28 (d+2)^3 - 25 \cdot 27 d^3,\) which we do not need to expand further for WolframAlpha to find the roots. The only positive real root is \(d = 10.495,\) and the resulting minimal circuit delay \(\hat{D} = 16.5\) delay units. Note that \(\hat{D} = 16.5\) is reasonably close to our approximate leg delays of \(\hat{D}_1(3) = 17.3\) and \(\hat{D}_2(3) = 15.3,\) validating the accuracy of the approximation. The 1d-analysis rewards the extra design effort with exact rather than approximate information for gate sizing, by prescribing different stage efforts \(\hat{f}_1 = d/3 = 3.5\) for leg 1 and \(\hat{f}_2 = (d+2)/3 = 4.2\) for leg 2. With a little practice and the aid of mathematical software like WolframAlpha for root finding, the 1d-analysis is as easy as the back-of-the-envelope approximation.

Example 3.15: Branch Design with Path Sizing

We wish to minimize the delay of the branching circuit in Figure 3.15 with path electrical efforts \(H_1 = H_2 = 15.\)

Figure 3.15: A branching circuit with logic gates on the legs.

Analogous to Example 3.14 we first derive the approximating equivalent inverter path to determine the best path size. The leg logical effort of leg 1 is the logical effort of the NAND gate, \(G_1 = 4/3,\) and for leg 2, we obtain \(G_2 = 1 \cdot 5/3 = 5/3.\) The load capacitance of the approximating equivalent inverter path is

\[C_L = (G_1 H_1 + G_2 H_2) C_{in} = \Bigl(\frac{9}{3} \cdot 15\Bigr) C_{in} = 45 C_{in}\,.\]

For path effort \(F = C_L / C_{in} = 45,\) the path sizing calculator prescribes a path length of \(n = 3.\) Since leg 1 of our branch has only one stage, we append two inverters. Leg 2 we leave unmodified, because two stages may be sufficiently fast, and appending an inverter pair would overshoot the best number of stages by one. The modified branching circuit is shown in Figure 3.16.

Figure 3.16: Branching circuit with leg 1 extended for best leg length.

Next, we apply the 1d-analysis method to minimize the branch delay. The path parasitic delays are \(P_1 = 2 + 1 + 1 = 4\) for leg 1 and \(P_2 = 1 + 2 = 3\) for leg 2. We find a parasitic delay compensation of \(\Delta p = 1,\) and assign stage delay \(d/3\) to each gate of leg 1 and \((d+1)/2\) to each gate of leg 2. Multiplying the effort delays of each path, we obtain \((d/3)^3 = G_1 H_1 C_{in}/C_1\) and \(((d+1)/2)^2 = G_2 H_2 C_{in}/C_2.\) Substituting \(C_1\) and \(C_2\) in the branch constraint, we obtain the polynomial \(d^3 (d+1)^2 - 4\cdot 25 d^3 - 20 \cdot 27 (d+1)^2.\) WolframAlpha finds the positive real root \(d = 11.5.\) If each gate in leg 1 bears stage effort \(\hat{f}_1 = d/3 = 3.8\) and each gate in leg 2 stage effort \(\hat{f}_2 = (d+1)/2 = 6.2,\) then the branching circuit has a minimum delay of \(\hat{D} = 15.5\) delay units. Note that the stage effort \(\hat{f}_2\) exceeds the best stage effort \(f^\star = 3.59\) by more than \(70\,\%.\) To reduce stage effort \(\hat{f}_2,\) we may want to try extending leg 2 with an inverter pair after all.

3.6.2. Branches with Driver Path¶

When we design a circuit with a branch, the input capacitance of the branch presents a load to another logic circuit. In the following, we discuss the design of circuits with branches that are driven by a logic path. Figure 3.17 shows an example, where the driver path consists of a single stage only, a NOR gate.

Figure 3.17: Branching circuit with driver path.

If we wish to minimize the delay of the branching circuit in Figure 3.17, we are faced with the problem of how much effort the driver path and how much effort the legs of the branch should bear. In general, the legs of the branch may bear different path efforts, e.g. \(d_2\) and \(d_2+1\) in Figure 3.17, and, furthermore, the path effort of the driver path may differ from path efforts of the legs. We know how to use the 1d-analysis method to assign effort delays to the gates of the legs. Assume the driver path bears effort delay \(d_1,\) and the branch bears effort delay \(d_2,\) which we allocate to the legs according to the 1d-analysis method. Figure 3.17 includes the allocation of the effort delays to the gates of the circuit. Now, the design task involves deriving effort delays \(d_1\) and \(d_2\) such that the circuit delay is minimized. The 2d-analysis method enables us to find these two delays:

2d-Analysis Method

Given a branching circuit and a driver path with input capacitance \(C_{in}\) and load capacitances \(H_1 C_{in}\) and \(H_2 C_{in}.\) Follow these steps to minimize the circuit delay:

1. Given an \(n\)-stage driver path, assign effort delay \(d_1/n\) to each gate of the driver path, and use the 1d-analysis method to allocate delay \(d_2\) to the gates of the legs.
2. Form the products of the leg efforts and the driver path efforts, and use the branch constraint to express \(d_1\) as a function of \(d_2\) or vice versa.
3. Express path effort delay \(D = d_1 + d_2\) as a function of \(d_2\) (or \(d_1\)), and minimize \(D,\) e.g. by means of calculus.

We introduce the 2d-analysis method with two examples.

Example 3.17: Fork Design with 2d-Analysis

In Section 1d-Analysis Method, we minimize the delay of the 3-fork in Figure 3.10. For leg electrical efforts \(H_1 = H_2 = 25,\) we obtain a minimum delay of \(\hat{D} = 14.91\) units. In this example, we investigate whether it is beneficial to replace two inverters of the 3-fork with one inverter on the drive path of a 2-fork. Figure 3.18 shows the circuit, which is logically equivalent to a 3-fork, but saves one inverter.

Figure 3.18: A 2-fork with a driving inverter is logically equivalent to the 3-fork in Figure 3.10.

We use the 2d-analysis method to minimize the delay of the 2-fork with a 1-stage driver path. In step 1 we allocate the effort delays as annotated in Figure 3.18 already. The inverter in lower leg 2 shoulders parasitic delay compensation \(\Delta p = P_1 - P_2 = 2 - 1 = 1\) w.r.t. upper leg 1. Next, we derive the telescoping products of the effort delays for the legs of the 2-fork:

\[\Bigl(\frac{d_2}{2}\Bigr)^2 = \frac{H_1 C_{in}}{C_1}\,,\qquad d_2 + 1 = \frac{H_2 C_{in}}{C_2}\,,\]

and for the driver path with load capacitance \(C_1 + C_2\):

\[d_1 = \frac{C_1 + C_2}{C_{in}}\,.\]

Substituting \(C_1\) and \(C_2\) yields \(d_1\) as a function of \(d_2\):

\[d_1 = \frac{4 H_1}{d_2^2} + \frac{H_2}{d_2 + 1}\,.\]

Step 3 minimizes path effort delay \(D = d_1 + d_2,\) by taking the derivative of \(D\) w.r.t. \(d_2,\) and finding the relevant root of the resulting polynomial:

\[d_2^3 (d_2 + 1)^2 - H_2 d_2^3 - 8 H_1 (d_2 + 1)^2\,.\]

For \(H_1 = H_2 = 25,\) WolframAlpha finds the positive real root \(d_2 = 6.9,\) from which we deduce \(d_1 = 5.2.\) Including parasitic delay \(P_1 = 3,\) the minimum path delay is \(\hat{D} = d_1 + d_2 + P_1 = 15.1\) units, which is marginally larger than the minimum delay of the 3-fork.

3.6.3. Reconvergent Branches¶

We conclude our discussion of branching circuits by applying the 1d-analysis and 2d-analysis methods to branches whose legs reconverge at the inputs of a gate. Figure 3.19 shows such a circuit. The NAND gate in stage 1 drives a branch with legs in stage 2 that reconverge at the NAND gate in stage 3. Furthermore, each of the inputs of the circuit branches. One of the two legs drives the stage-1 NAND gate and the other the stage-2 NAND gate. The design challenge is to minimize the delay of this circuit.

Figure 3.19: A circuit with reconverging branches.

First, we recognize that the longest path through the circuit traverses three NAND gates, one in each stage. The circuit is symmetric if we assume that the NAND gates in stage 2 have equal size. Then, the path from the upper input through the stage-1 NAND gate, the upper stage-2 NAND gate, and the NAND gate in stage 3 is representative for the four longest paths from either input to the output. This is our path of interest.

To determine the delay of the circuit, we allocate effort delays \(d_1,\) \(d_2,\) and \(d_3\) to the corresponding stages, as shown in Figure 3.19. Analysis of the circuit reveals the stage effort delays:

Here, the load of the stage-1 NAND gate is the sum of the leg input capacitances, both of which are \(C_2\) assuming that the stage-2 NAND gates have equal size. The branch constraint for the circuit input is

enabling us to capture the relation between the effort delays in a single equation:

To solve Equation (12), we need to constrain variables \(d_1,\) \(d_2,\) and \(d_3.\) A simplistic constraint assumes that all stage efforts are equal, \(d_1 = d_2 = d_3,\) as motivated by the key insight from the analysis of multistage paths. Although our circuit is not a simple path, this constraint yields a univariate polynomial of degree three. For example, given \(H = 6,\) we obtain the positive real root \(d_1 = 4.18\) and path delay \(D_{1d} = 3 d_1 + 3 p_{nand} = 18.54.\)

We might expect a better design from a 2d-analysis, assuming that the NAND gates in stages 2 and 3 are the legs of the branch, with the additional constraint that the stage-3 NAND gate belongs to both legs. To equalize the leg delays, we allocate effort delay \(d_2 = d_3\) to stages 2 and 3. However, we assume a potentially different delay \(d_1\) for the driver path in stage 1. Now we wish to minimize path delay \(D = d_1 + 2 d_2.\) We rearrange Equation (12) to express \(d_1\) as a function of \(d_2,\) assuming \(d_3 = d_2\):

such that

We minimize \(D\) by setting the derivative of \(D\) w.r.t. \(d_2\) to zero, and find the root \(d_2 = 4.7\) for \(H = 6.\) As a result, we obtain \(d_1 = 2.5\) and \(D_{2d} = d_1 + 2 d_2 + 3 p_{nand} = 17.89.\) We conclude that the 2d-analysis produces a slightly faster circuit than the 1d-analysis.

To reduce the delay of the circuit beyond \(D_{2d},\) we observe that the branches at the circuit inputs have the topology of reconvergent 1-forks that drive the stage-2 gates. One leg includes the stage-1 NAND gate instead of an inverter, and the other leg contains no logic. In Section 1d-Analysis Method, we identified a 1-fork as an undesirable circuit. As a case in point, we improve the circuit in Figure 3.19 by replacing the 1-fork with 2-fork topologies. To that end we insert back-to-back inverters as shown in Figure 3.20. The back-to-back inverters in the upper leg and the NAND gate in the lower leg resemble a 2-fork, except that the 1-stage leg contains the NAND gate rather than an inverter.

Figure 3.20: Improved version of reconverging branch circuit in Figure 3.19.

Since the path parasitic delay of two inverters equals the parasitic delay of a NAND gate, the delays of the two legs of the 2-forks are equal if we allocate effort delay \(d\) to the NAND gate and \(d/2\) to each of the inverters. Using a 1d-analysis, we also allocate effort delay \(d\) to the remaining NAND gates, as shown in Figure 3.20. The stage efforts of the inverter pair and the NAND gates are:

Applying branch constraint \(C_{in} = C_1 + C_2\) yields:

Given \(H = 6,\) we find the positive real root \(d = 3.44.\) The minimum delay of the circuit in Figure 3.20 is \(\hat{D}_{1d} = 3 d + 3 p_{nand} = 16.3\) units, which is faster than the original circuit in Figure 3.19.

3.12

Use the 1d-analysis method to minimize the delay of the branching circuit assuming \(H_1 = H_2 = 12.\)

1. Determine the leg parasitic delays and allocate effort delays using one parameter \(d.\)
2. For each leg, form the products of the effort delays, and derive a polynomial in \(d.\)
3. Determine the root of the polynomial and the minimum leg delays \(\hat{D}_1\) and \(\hat{D}_2.\)