---
tags: computer-arch
---

# Quiz4 of Computer Architecture (2021 Fall)
> Solutions

## Problem `A`

Given the timing parameters in the table below, what are the [propagation delay](https://en.wikipedia.org/wiki/Propagation_delay) and [contamination delay](https://en.wikipedia.org/wiki/Contamination_delay) of this circuit?


| Gate | t~PD~ (ns) | t~CD~ (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 | t~pd~ (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 | t~PD~ | t~CD~ | t~SETUP~ | t~HOLD~ |
| --------- | :---: | :---: | :------: | :-----: |
| 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~ $\leq$ t~CD,R1~ + t~CD,CL1~, $2 \leq 1 + 2$ Satisfied
> t~hold,R3~ $\leq$ t~CD,R2~ + t~CD,CL2~, $1 \leq 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 | t~PD~ | t~CD~ | t~SETUP~ | t~HOLD~ | 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~ $\leq$ t~CD,R2~ + t~CD,CL2~ is 4 $\leq$ 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~ $\leq$ t~CD,R2~ + t~CD,CL2-New~ is 4 $\leq$ 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~ $\leq$ t~CD,R1~ + t~CD,CL1-New~ $2 \leq 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 + 2*3 + 3*7 + 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{align}
&\phantom{=}\overline{(A + B) \times (B \overline C + \overline A C)} \\
&= \overline{A+B}+\overline{B\overline{C}+\overline{A}C} \\
&= \overline{A} \times \overline{B}+(\overline{B}+\overline{\overline{C}})(\overline{\overline{A}}+\overline{C}) \\
&= \overline{A} \times \overline{B}+(\overline{B}+C)(A+\overline{C}) \\
&= \overline{A} \times \overline{B} +\overline{B}A+\overline{B}\times\overline{C}+CA+C\overline{C}\\
&= \overline{A} \times \overline{B}+\overline{B}(A+\overline{C})+AC \\
&= \overline{B}(\overline{A}+A+\overline{C})+AC \\
&= \overline{B}(1+\overline{C})+AC\\
&= A \times C + \overline{B}
\end{align}
$$

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

---