# Term Project: Quiz 3 annotated

> [Quiz questions](https://hackmd.io/@sysprog/arch2020-quiz3)
> [Solution](https://hackmd.io/@sysprog/arch2020-quiz3-sol)

---

## Question A

Simplify the following Boolean expressions by finding a minimal sum-of-products expression for each one. These expressions can be reduced into a minimal sum-of-products (SOP) by repeatedly applying the Boolean algebra properties.

1.
$$
\begin{align}
&\phantom{=}
\overline{(a+b \cdot \overline{c} )} \cdot d + c & \\
&= (\overline{a} \cdot \overline{b \cdot \overline c}) \cdot d+c & \text{(DeMorgan)}
\\
&=(\overline{a} \cdot \overline{b} + \overline{\overline{c}}) \cdot d+c & \text{(DeMorgan)}
\\
&=(\overline{a} \cdot \overline{b} + c) \cdot d+c & \text{(Double negation)}
\\
&=\overline{a} \cdot \overline{b} \cdot d + c \cdot d+c &\text{(Distributivity)}
\\
&=\overline{a} \cdot \overline{b} \cdot d + c &\text{(Absorption)}
\end{align}
$$

2.
$$
\begin{align}
&\phantom{=}
a \cdot \overline{(b+c)} (c+a)
\\
&=a \cdot (\overline b \cdot \overline c)(c+a) &\text{(De Morgan)}
\\
&=a \cdot (\overline b \cdot \overline c)(c+a) &\text{(De Morgan)}
\\
&=a \cdot (\overline b \cdot \overline c \cdot c+ \overline b \cdot \overline c \cdot a) &\text{(Distributivity)}
\\
&=a \cdot (\overline b \cdot 0 + \overline b \cdot \overline c \cdot a) &\text{(complementation 1)}
\\
&=a \cdot (0 + \overline b \cdot \overline c \cdot a) &\text{(Annihilator)}
\\
&=a \cdot \overline b \cdot \overline c \cdot a&\text{(Distributivity)}
\\
&=a \cdot \overline b \cdot \overline c &\text{(Idempotence)}
\end{align}
$$

---
## Question B

0.

1. Consider the implementation shown below, which uses two AND gates and an OR gate. Because a single CMOS gate cannot implement AND or OR, each AND gate is implemented with a CMOS NAND gate followed by a CMOS inverter, and the OR gate is implemented with a CMOS NOR gate followed by a CMOS inverter. How many transistors does this implementation have?
Number of transistors in mux: __ B01 __
A: B01 = 20.

| **Gate** | transistors |
| -------- | ----------- |
| INV | 2 |
| NAND | 4 |
| NOR | 4 |
| AND | 6 |
| OR | 6 |

CMOS is made by PMOS and NMOS, which are two kinds of trainsistor .For instance, CMOS inverter is consisted of 1 PMOS and 1 NMOS. The transistor amount of CMOS is shown as above. One mux is consisted of 2 and gate, 1 or gate, and 1 not gate.
2 + 6 + 6 + 6 = 20.

2. Consider the implementation shown below, which uses three instances of gate F. Find the Boolean expression for F. If F can be built using a single CMOS gate, say “Yes.” Otherwise, give a convincing explanation for why F cannot be implemented as a CMOS gate. How many transistors does this implementation have?
Number of transistors in mux (if F can be built as a CMOS gate): __ B02 __
A: B02 = Yes, 14

3. Consider the implementation shown below, which uses gate G. Find the Boolean expression for G. If G can be built using a single CMOS gate, say “Yes.” Otherwise, give a convincing explanation for why G cannot be implemented as a CMOS gate. How many transistors does this implementation have?
Number of transistors in mux (if G can be built as a CMOS gate): __ B03 __
A: B03 =
G cannot be built as a single CMOS gate because it is not inverting: G(1,0,t) = t, so a rising input (G(1,0,0)
→
G(1,0,1)) causes a rising output

4.Consider the implementation shown below, which uses gate H. Find the Boolean expression for H. If H can be built using a single CMOS gate, say “Yes.” Otherwise, give a convincing explanation for why H cannot be implemented as a CMOS gate. How many transistors does this implementation have?
Number of transistors in mux (if H can be built as a CMOS gate): __ B04 __
A:B04 = Yes, 12

---

## Question C
Consider the C procedure below and its translation to RISC-V assembly code, following the C code.

C procedure

int f(int a, int b) {
    int c = b – a;
     if (c & C01 == 0) /* c is a multiple of 4 */
         return 1;
     int d = f(a – 1, b + 2);
     return 3 * (d + a);
}

The translated RISC-V assembly code

f:    sub a2, a1, a0
      andi a2, a2, __C01__
      bnez a2, ELSE
      li a0, 1
      jr ra 
ELSE: addi sp, sp, -8
      sw a0, 0(sp)
      sw ra, 4(sp)
      addi a0, a0, -1
      addi a1, a1, 2
      jal ra, f
A4:   lw a1, 0(sp)
      lw ra, 4(sp)
L1:   add a0, a0, a1
      slli a1, a0, 1
      add a0, a0, a1
      addi sp, sp, 8
      jr ra

1. What value should the C01 term in the C code and the assembly be replaced with to make the if statement correctly check if the variable c is a multiple of 4?
A1: 3.
>To check if c is a multiple of 4, is to check the last 2 bits of c are 0, so C01 needs to be 3(0b11, or 0x3).

2. How many words will be written to the stack before the program makes each recursive call to the function f?
A3: 2. If ```bnez``` is true, the program will go to ```else```, and we can see that there are 2 ```sw```.

3. The program’s initial call to function f occurs outside of the function definition via the instruction jal ra, f. The program is interrupted at an execution (not necessarily the first) of function f, just prior to the execution of add a0, a0, a1 at label L1. The below diagram on the right shows the contents of a region of memory. All addresses and data values are shown in hex. The current value in the SP register is 0xEB0 and points to the location shown in the diagram.
What were the values of arguments a and b to the initial call to f? Write “UNKNOWN” if the argument does not show up in the stack.
Initial arguments to f: a = __ C03 __ ; b = __ C04 __
A3:C03: 4. C04: unknown
>```a``` is passed in ```a0```, can find saved ```a0``` from initial call right before external return address. ```b``` is never saved, so cannot tell.

4. What are the values in the following registers right when the execution of f is interrupted? Write “UNKNOWN” if you cannot tell.
Current value (in hex) of a1: __ C05 __
Current value (in hex) of ra: __ C06 __
A4: 0x2, 0xA4
>These registers were just loaded from the stack at the time of interruption.

5. What is the hex address of the jal ra, f instruction that made the initial call to f?
Address (in hex) of instruction that made initial call to f: __ C07 __
A5: C07:0x3B4
>Saved ```ra``` of initial call is ```0x3B8```, call occurs 0x4 before that at ```0x3B4```

6. What is the hex address of the instruction at label ELSE?
Address of instruction at label ELSE: __ C08 __
A6: C08: 0x8C
>```ra``` saved pointing to ```lw``` ```a1```, ```0(sp)``` is at ```0xA4```, ```ELSE``` is ```0x18``` before at ```0x8C```.


---
## Question D
1. Consider the logic diagram below, which includes XNOR2, OR2, NAND2, AND2, and INV. Using the $t_{PD}$(propagation delay) information for the gate components shown in the table below, compute the $t_{PD}$ for the circuit.

| **Gate** | $t_{PD}$ |
| -------- | -------- |
| XNOR2 | 7.0 ns |
| OR2 | 5.5 ns |
| NAND2 | 3.0 ns |
| AND2 | 5.0 ns |
| INV | 2.0 ns |

A1: The longest path is begin with a/b ->XNOR2 ->NAND2 ->OR2 ->INV->x
7.0+3.0+5.5+2.0 = 17.5 ns
2. Find a minimal sum-of-products expression for output X of the circuit described by the truth table shown below.
A2:
$ab+\overline a c \overline d+\overline a \overline b \overline c d$

---
## Question E

1. What is the hexadecimal encoding of the RISC-V instruction sw t1, -4(t1)? You can use the table below to help you with the encoding.

| [31:25] | [24:20] | [19:15] | [14:12] | [11:7] | [6:0] |
| ------- | ------- | ------- | ------- | ------ | ----- |
| imm[11:5] | rs2 | rs1 | funct3 | imm[4:0] | opcode |
opcode = 0100011
funct3 = 010
t1 = x6
rs1 = 00110, rs2 = 00110

A1: ```1111111_00110_00110_010_11100_0100011``` in binary, to hex, is ```0xFE632E23```

2. For the following code snippet, provide the value left in each register after executing the entire code snippet (i.e., when the processor reaches the instruction at the end label), or specify “UNKNOWN” if it is impossible to tell the value of a particular register.

. = 0x100
     li x4, 0x6
     addi x5, zero, 0xC00
     slli x4, x4, 8
     or x6, x4, x5
end:

- x4 = __ E02 __
- x5 = __ E03 __
- x6 = __ E04 __
- pc = __ E05 __
A1:
> *Except for the 5-bit immediates used in CSR instructions (Section 2.8), immediates are always sign-extended, and are generally packed towards the leftmost available bits in the instruction and have been allocated to reduce hardware complexity.*
> (The RISC-V Instruction Set Manual, Volume I: Base User-Level ISA, p.11)

x4 = 0x6 << 8 = 0x600
x5 = 0xC00 -> 0xFFFFFC00
x6 = x4 | x5 = 0xFFFFFE00

Since RISC-V deals with everything in byte addresses:
>RV32I provides a 32-bit user address space
that is *byte-addressed* and little-endian.(The RISC-V Instruction Set Manual, Volume I: Base User-Level ISA, p.18)

so ```pc = 0x100 + 4*4 = 0x110```

## Question F
---
Consider the following program that computes the Fibonacci sequence recursively. The C code is shown on the below, and its translation to RISC-V assembly is provided as well. You are told that the execution has been halted just prior to executing the ret instruction.

C code

int fib(int n) {
   if (n <= 1) return n;
   return fib(n - 1) + fib(n - 2);
}

The translated RISC-V assembly

fib:  addi sp, sp, -12
      sw ra, 0(sp)
      sw a0, 4(sp)
      sw s0, 8(sp)
      li s0, 0
      li a7, 1
if:   ble __F01__
sum:  addi a0, a0, -1
      call fib
      add s0, s0, a0
      lw a0, 4(sp)
      addi a0, a0, -2
      call fib
      mv t0, a0
      add a0, s0, t0
done: lw ra, 0(sp)
      lw s0, 8(sp)
L1:   addi sp, sp, 12
      ret

Complete the missing portion of the ble instruction to make the assembly implementation match the C code.
A: F01= ```a0, a7, done```. Since ```if``` is to compared the ```n``` and the constant ```1```, and if true, the ```done``` will be executed, otherwise the program will execute the ```sum```, so what we need to figure out is the 2 arguments of ```ble```. We can see that ```a7``` loads the constant ```1```, and a0 does the ```addi -1``` and ```addi -2``` in ```sum```, so ```a0``` is the argument ```n```, compared with ```a7```.

How many distinct words will be allocated and pushed into the stack each time the function ```fib``` is called? Number of words pushed onto stack per call to fib: __ F02 __
A:F02 = 3. We can see that in ```fib```, the ```sw``` executed 3 times.