Quiz4 of Computer Architecture (2021 Fall)

Solutions

Problem A

Given the timing parameters in the table below, what are the propagation delay and contamination delay of this circuit?

Gate	tPD (ns)	tCD (ns)
XOR	2	1.5
INV1	1.5	1
AND2	3	2

1. Propagation delay (ns) = __ A01 __

   A01 = ?

   7.5

   Longest path: INV1

   $\to$ AND2

   $\to$ AND2 = 1.5 + 3 + 3 = 7.5

2. Contamination delay (ns): __ A02 __

   A02 = ?

   3

   Shortest path: INV

   $\to$ AND2 = 1 + 2 = 3

---

Problem B

Consider the logic diagram below, which takes 4 inputs {a, b, c, d} and computes two outputs {x, y}. Using the t_PD information for the gate components shown in the table below, compute the t_PD for the circuit.

Gate	tpd (ns)
XNOR2	5.5
AND2	3.5
OR2	2.5
INV	1.0

• t_PD (ns) = __ B01 __

  • B01 = ?

  9.0

We can examine the different paths that exist from each input to the outputs and calculate the critical delay for each.

$\uparrow$ 1.0 + 2.5 = 3.5

$\uparrow$ 1.0 + 3.5 + 2.5 = 7

$\uparrow$ 1.0 + 3.5 + 3.5 = 8

$\uparrow$ 3.5 + 2.5 = 6

$\uparrow$ 3.5 + 3.5 = 7

$\uparrow$ 5.5 + 3.5 = 9

$\uparrow$ 5.5 + 3.5 = 9

The propagation time for the circuit is the slowest path from input to output, so t_PD = 9.0 ns.

We can also avoid examining some of the paths by noticing that some of the paths differ only in that one path goes through an additional gate compared to another, and thus we should not even consider the shorter of those two paths.

---

Problem C

Consider the sequential circuit below, which includes registers made of D flip flops, in addition to combinational logic. All registers share a common clock, which is not shown. The squares that begin with R denote registers. The stars that begin with CL denote combinational logic. The table below contains the propagation delay and contamination delay of the components.

Component	tPD	tCD	tSETUP	tHOLD
R1	2 ps	1 ps	2 ps	1 ps
R2	2 ps	2 ps	1 ps	2 ps
R3	1 ps	1 ps	6 ps	1 ps
CL1	3 ps	2 ps	N/A	N/A
CL2	2 ps	1 ps	N/A	N/A

1. What are the propagation (t_PD) and contamination delays (t_CD) of the circuit? Recall that these are measured from the rising edge of the clock to the output.

• t_PD (ps) = __ C01 __

• t_CD (ps) = __ C02 __

  • C01 = ?

  1

  • C02 = ?

  1

2. What is the minimum clock period we can use for this circuit to function properly?

• Minimum clock period for correct operation (ps): __ C03 __

  • C03 = ?

  10

R1 → R2: t_PD,R1 + t_PD,CL1 + t_S,R2 = 2 + 3 + 1 = 6ps
R2 → R3: t_PD,R2 + t_PD,CL2 + t_S,R3 = 2 + 2 + 6 = 10ps
R3 → R2: t_PD,R3 + t_PD,CL1 + t_S,R2 = 1 + 3 + 1 = 5ps
t_hold,R2

$\le$ t_CD,R1 + t_CD,CL1,

$2\le 1+2$ Satisfied
t_hold,R3

$\le$ t_CD,R2 + t_CD,CL2,

$1\le 2+1$ Satisfied

3. We would like to have a functioning circuit with a clock period of 5 ps. The following table shows possible replacements for each component in the circuit along with the price for the replacement. What is the lowest amount of money we need to spend to achieve this goal? Make sure that your new circuit obeys all timing constraints.

Component	tPD	tCD	tSETUP	tHOLD	Price (USD)
R1-New	1 ps	1 ps	2 ps	1 ps	1.5
R2-New	2 ps	2 ps	1 ps	1 ps	2.0
R3-New	1 ps	1 ps	1 ps	4 ps	5.0
CL1-New	2 ps	2 ps	N/A	N/A	1.0
CL2-New	2 ps	2 ps	N/A	N/A	4.0

• Minimum money spent ($): __ C04 __

  • C04 = ?

  10

• Name(s) of replacement(s) purchased: __ C05 __

  • C05 = ?

R3-New, CL1-New, CL2-New (可換順序)

First replace R3 with R3-New to get rid of 6 ps setup time.
R2 → R3-New: t_PD,R2 + t_PD,CL2 + t_S,R3-New = 2 + 2 + 1 = 5ps

Check if hold time of R3-New is satisfied:
t_hold,R3-New

$\le$ t_CD,R2 + t_CD,CL2 is 4

$\le$ 2 + 1 Not satisfied

Replace CL2 because t_CD,R2-New is the same as t_CD,R2.
R2 → R3-New: t_PD,R2 + t_PD,CL2-New + t_S,R3-New = 2 + 2 + 1 = 5ps
t_hold,R3-New

$\le$ t_CD,R2 + t_CD,CL2-New is 4

$\le$ 2 + 2 Satisfied

Now, we need to fix the R1 → R2 path:
R1 → R2: t_PD,R1 + t_PD,CL1 + t_S,R2 = 2 + 3 + 1 = 6ps
Can either replace R1 or CL1. CL1-New is cheaper so replace CL1.
R1 → R2: t_PD,R1 + t_PD,CL1-New + t_S,R2 = 2 + 2 + 1 = 5ps

t_hold,R2

$\le$ t_CD,R1 + t_CD,CL1-New

$2\le 1+2$ Still Satisfied
R3-New → R2: t_PD,R3-New + t_PD,CL1-New + t_S,R2 = 1 + 2 + 1 = 4ps

---

Problem D

In the following circuit, the registers have a clk-to-q delay of 6ns and setup times of 5ns. NOT gates have a delay of 3ns, AND and OR gates have a delay of 7ns, and the "Black Box" logic component has a delay of 9ns.

1. What is the maximum allowable hold time of the registers? __ D01 __ (ns)

   • D01 = ?

   28

   The shortest path through the circuit to a register clearly follows the path from A to O and includes:
   clk-to-q delay, two NOT gates, one OR gate, and the "Black Box." Maximum hold time = 6 + 2*3 + 7 + 9 = 28ns

2. What is the minimum acceptable clock period for this circuit? __ D02 __ (ns)

   • D02 = ?

   47

   The period is determined by the longest path and includes: clk-to-q delay, two NOT gates, three OR gates (or two OR gates and one AND gate), the "Black Box", and the setup time. Minimum period = 6 + 23 + 37 + 9 + 5 = 47ns

---

Problem E

Consider the following circuit, where A, B, and C are inputs and Out1 is the output:

1. Find the simplest (least gates used) Boolean expression that represents the same logic as above.

   • Notation: NOT is represented by ~, And by *, and OR by +. That is also the order of presence.
   • In addition, please use parentheses if needed to organize your logic correctly though do not add any extra ones.
   • Please add spaces between + and * but do NOT add spaces between ~ and the letter.
   • In each grouping, please organize alphabetically and put groupings before single letters. Try not to add unnecessary parentheses.

   • E01 = ?

   A * C + ~B

$$\begin{array}{rl}& \phantom{=}\overline{(A+B)\times (B\stackrel{―}{C}+\stackrel{―}{A}C)}\\ & =\overline{A+B}+\overline{B\stackrel{―}{C}+\stackrel{―}{A}C}\\ & =\bar{A}\times \bar{B}+(\bar{B}+\overline{\stackrel{―}{C}})(\overline{\stackrel{―}{A}}+\bar{C})\\ & =\bar{A}\times \bar{B}+(\bar{B}+C)(A+\bar{C})\\ & =\bar{A}\times \bar{B}+\bar{B}A+\bar{B}\times \bar{C}+CA+C\bar{C}\\ & =\bar{A}\times \bar{B}+\bar{B}(A+\bar{C})+AC\\ & =\bar{B}(\bar{A}+A+\bar{C})+AC\\ & =\bar{B}(1+\bar{C})+AC\\ & =A\times C+\bar{B}\end{array}$$

2. Consider the unsimplified circuit. Say our OR gates take 5 ns each, the AND gates take 2 ns, and the NOT gates take 1 ns. In addition, the registers have setup time 2 ns and clk-2-q 3 ns. How long is our critical path in ns? __ E02 __

   • E02 = ?

   16

   It is the path of CLK-2-Q -> NOT -> AND -> OR -> AND -> NOT -> SETUP = 3 + 1 + 2 + 5 + 2 + 1 + 2 = 16 ns

---