ex Inspect and manipulate memories and a processor design.

### 1. Flop-flip-flopping (8 points)

Consider the following circuit that uses falling-edge triggered D flip-flops.

Assume the Clock input, and outputs Q0, Q1, and Q2, are all initially 0. Draw waveforms for Clock, Q0, Q1, and Q2, showing at least ten Clock cycles. You do not need to turn in your waveform drawing, but it will help you reason about the circuit.

1. (5 points) Write a table summarizing the values of Q0, Q1, and Q2 after each Clock cycle.

2. (3 points) Briefly explain what this circuit does at a high level, treating the Q outputs together. A phrase to a couple sentences is enough.

### 2. Reconstructing Memories (18 points)

In this set of exercises, you will reuse provided RAMs (random access memories) to design RAMs of different dimensions without reimplementing the internals.

#### Provided RAMs

In an A×B RAM, A is the number of addressable locations (cells) in the memory and B is the width of each location (cell) in bits. Recall that a RAM is much like a register file, but the underlying storage technology is not based on flip-flops. Memory addresses are analogous to register numbers in a register file; memory locations (cells) are analogous to registers in a register file. Unlike the register file we designed, these RAMs support reading only one location at a time.

The provided RAMs have the following form:

• Each RAM has a Data In port, a Data Out port, an Address input and a Write Enable input.
• Each RAM is always reading from the location given by the current Address, expressing its contents on Data Out.
• Each RAM also stores the value on Data In into the location given by the current Address if the Write Enable input carries a 1.
• Each RAM is indivisible.

#### Rules

You will design new RAMs with the same kind of inputs, outputs, and externally observable behavior, but with different dimensions. For each:

• Draw one or more small boxes of the form above, representing the provided RAM(s), inside a larger box of the same form, representing the RAM you are implementing.
• Connect inputs and outputs of the larger box with those of the smaller boxes, possibly adding combinational logic building blocks.
• Do not draw each individual line of a bus (e.g., Address) unless necessary to distinguish the endpoints of the individual lines. Use hatch marks and width annotations instead.

#### Exercises

1. (2 points) Indicate the widths (in bits/lines) of the ports (i) Address, (ii) Data In, and (iii) Data Out for a 256×4 RAM.

2. (4 points) Design a 256×8 RAM by adding minimal wiring and logic to two identical 256×4 RAM components.

3. (12 points) Design a 64K×8 RAM by adding minimal wiring and logic to a single provided 16K×32 RAM. (K = “kilo” = 1024)

• Unlike the previous exercise, this provided RAM component has the same capacity as the desired final product, though it has different dimensions:
• The provided RAM has fewer addressable memory locations (A) than the RAM you will design.
• The provided RAM has a larger addressable unit of data (B) than the RAM you will design.
• Be careful with writes: when writing an 8-bit value into the provided RAM, you must be sure to change only the relevant 8 bits of storage. All other storage bits should hold the same values as before the write operation.

### 3. Taking Control (7 points)

In this exercise you will design the Control Unit for the HW microarchitecture we designed in class. Our design focused on connecting the datapath components (e.g., the register file, ALU, memory, etc.), but we left the Control Unit as black box.

Give a truth table with 4-bit HW instruction opcodes as inputs, plus one output for each of the control lines, outputs of the Control Unit that are control inputs to other components. The table should have one row for each of the seven instructions (one row for each opcode) except JMP from the first instruction table here.) The control lines we need are:

• Reg Write (1 bit): controls the write-enable of the register file.
• ALU Op (4 bits): controls the ALU (with the same 4 ALU control lines we developed earlier).
• From left to right: Invert A, Negate B, Op1, Op0.
• Mem Store (1 bit): controls the write-enable of the data memory.
• Mem Load (1 bit): controls three multiplexers deciding which input to provide for:
• the register file’s write address;
• the register file’s write data; and
• the ALU’s second operand.
• Branch (1 bit, added during class): controls whether to choose the next PC based on a branch target and test

### 4. Jumping into the Unknown (16 points)

1. (8 points) Add logic to the HW microarchitecture to implement the `JMP` instruction, which we did not implement in class. Draw your logic on a copy of the datapath we have so far. You will add:

• One new Jump control line from the Control Unit, carrying 1 if the current instruction is `JMP` and 0 otherwise.
• One new column in the Control Unit table for the Jump control line.
• One new row in the Control Unit table for the `JMP` opcode.
• Wiring and logic using the Jump control line and the offset bits from the `JMP` instruction encoding to store the `JMP` instructions’s target address to the PC if and only if the current instruction is `JMP`. You will need to “cut” one existing wire to splice in some new logic.

`JMP` sets the PC to the absolute instruction address given by its argument (a number) multiplied by 2. For example, `JMP 3` sets the PC to 0x6, causing the instruction stored at address 0x6 (i.e., the 3rd instruction in the program) to be executed next.

2. (8 points) Assume `R2` and `R3` hold input values when the following program starts. `R4` will hold an output when the program stops. The address of each instruction in the instruction memory is shown at left. The (new) `HALT` instruction stops the computer.

1. Execute the program assuming `R2` holds 5 and `R3` holds 2. What value does `R4` hold when the computer reaches `HALT`?
2. Try a couple more examples with (small) positive numbers in `R2` and `R3`. What does this code do with `R2` and `R3` to compute `R4`? Answer with one simple line of C code using variables `R2`, `R3`, and `R4` (i.e., `R4 = ...;`), or answer with an English sentence.
``````    # R2 and R3 hold program inputs here.
0:  AND R2, R2, R4
2:  AND R3, R3, R5
4:  BEQ R5, R0, 3
6:  SUB R5, R1, R5
A:  JMP 2
C:  HALT # Stops execution.
# What value is in R4?``````

### 5. Instruction Not Missing (15 points)

The HW ISA introduced in class lacks an instruction for bitwise complement. A logical choice would be `NOT Rs,Rd`, which takes the bitwise complement of the value in source register `Rs` and stores into destination register `Rd`. You will design two implementations of the proposed `NOT` instruction.

1. (5 points) One way to implement `NOT` is to replace any occurence of a `NOT` instruction by a sequence of existing HW instructions that has the same effect as `NOT`.

Given source register identifier `Rs` and destination register identifier `Rd`, write a sequence of one or more HW instructions that has the same effect as `NOT Rs,Rd`. The replacement instructions may use values from any registers, but must store values only in `Rd`. Instructions may not store values in any other register or data memory location. The sequence may use only the instructions defined in class. (See the instruction table here.)

Hint: Think about the relation of bitwise complement and arithmetic rules.

2. (5 points) A second way to implement `NOT` is to add a new instruction to the ISA, complete with an unique encoding, and to extend the microarchitecture to implement it. First, implement a related instruction (`NAND`) in this way.

1. Give an assembly syntax and define a 16-bit encoding of the `NAND` instruction as in the instruction table here. Choose an unused opcode for the encoding.
2. Add a row to the Control Unit Table from Problem 3 to indicate how to control the datapath to implement `NAND`. Do not add extra logic to the datapath.
3. (5 points) Consider how to implement `NOT` using `NAND`. Define an encoding for the `NOT` instruction directly in the ISA. Choose the encoding carefully to minimize additions to the Control Unit and the datapath. Assuming you have completed (b), an ideal encoding requires no new rows or columns in the Control Unit table.

Hint: Think of how to translate the `NOT` instruction to a `NAND` instruction and use this intuition when designing the bit encoding of `NOT`.