Architecture

Assignment: Architecture

• Assign: Thursday 5 October
• Due: Monday 16 October
• Policy: Individual graded synthesis assignment
• Submit: Upload a PDF written on the cs240-arch-worksheet-f23.pdf submission sheet
• Reference:
  • Sequential Logic
  • A Simple Processor

Contents

• Assignment: Architecture
• Exercises
  • 1. A Loopy Program [14 points]
  • 2. Taking Control (8 points)
  • 3. Instruction Not Missing (10 points)
  • 4. Jumping into the Unknown [15 points]
  • 5. Reconstructing Memories (RAM Puzzles) [13 points]
  • 5 Extra Fun Affixed or Afloat in a C of Numbers
• Submission

Exercises

Please write your answers on the cs240-arch-worksheet-f23.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.

Notes:

• This assignment is worth 60 points.

1. A Loopy Program [14 points]

In this exercise you will simulate the execution of an HW ISA program with a loop.

Background

In the solution slides for the HW ISA architecure, there are examples (slides 8-11) of using an execution table to simulate the execution of HW ISA programs, one of which contains a loop.

Here we consider a different program that has a loop to remind you of the conventions used in an execution table. Suppose that register R2 has been initialized with the signed decimal number 3 and register R3 has been initialized with the signed decimal number 7. Also suppose that the program P0 has the following Instruction Memory (IM):

IM

Then here is an execution table that shows the step-by-step execution of the program P0.

Note that the way you should read the meaning of BEQ R1, R2, offset is that the change to the PC, PC <- PC + 2 + offset*2 replaces the non-branch change to the PC (PC <- PC + 2), as we designed in the HW ARCH slides. Specifically, note in the following example that the PC goes from 0 to 8 (not 10) based on the instruction BEQ R2, R3, 3, because PC + 2 + offset*2 = 0 + 2 + 3*2 = 8.

Execution table

Your Task

This task considers a HW ISA program P1 with the following Instruction Memory IM:

IM

1. [8 points] In the worksheet, fill in the execution table for program P1. Use the same notational conventions used in the example execution table for P0 above. Any numbers beginning with 0x will be interpreted as hexidecimal; any numbers not beginning with 0x will be interpreted as decimal.

2. [3 points] Show the final values of the registers R2, R3, and R4 when the program execution halts. Again, any numbers beginning with 0x will be interpreted as hexidecimal; any numbers not beginning with 0x will be interpreted as decimal.

3. [3 points] Alice wants to translate program P1 (except for the final HALT instruction) into a sequence of statements in a version of C with a 16-bit int type. Fill in the rest of her program with assignments to variables named R2, R3, and R4 that represent the registers with these names in P1 and a while loop. (We will not be picky on C syntax, as your long your statements are in the right order you will receive full credit).

   int R0 = 0;
   int R1 = 1;
   int R2 = R0 + R0;
   // ...
   

2. Taking Control (8 points)

In this exercise you will design the Control Unit for the HW microarchitecture we designed in class. (Base your design on the figure below labeled “HW microarchitecture datapath”.) 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.

Flesh out 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. As shown below, the table should have one row for each of the seven instructions (one row for each opcode) except JMP from the HW ISA Instructions table here.

The control lines we need are:

• Reg Write (1 bit): controls the write-enable of the register file. If an instruction should both read and write to the register file, the write-enable should be 1 (that is, the read data lines still produce the contents of their respective registers even when the write-enable is 1).
• ALU Op (4 bits): controls the ALU (with the same 4 ALU control lines we developed earlier; see the end of the Arithmetic slides).
  • From left to right: Invert A, Negate B, Op₁, Op₀.
• Mem Store (1 bit): controls the write-enable of the data memory.
• Mem (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.

Please note that Mem Store, Mem, and Branch are all active high (0 = False, 1 = True).

3. Instruction Not Missing (10 points)

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

1. [4 points] One way to implement NOT is to replace any occurrence 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 not, arithmetic, and two’s complement.

2. [4 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. [3] Define a 16-bit encoding of the NAND instruction as in the instruction table here. Choose any unused opcode for the encoding.
   2. [1] Add a row to the Control Unit Table from the previous problem to indicate how to control the datapath to implement NAND. Do not add extra logic to the datapath diagram.

3. [2 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.

4. Jumping into the Unknown [15 points]

1. [10 points]

   Add logic to the HW microarchitecture depicted in the figure above to implement the JMP instruction, which we did not implement in class. 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.

   1. [7 points] In the wiring diagram for the microarchitecture on the worksheet, you will add:

      • One new Jump control line from the Control Unit (in Problem 4), carrying 1 if the current instruction is JMP and 0 otherwise.

      • 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.

      Notes:

      • The JMP hardware will need to use a Zero Extend unit that is different from the existing Sign Extend unit.

      • Do not attempt to reuse the existing Shift Left by 1 unit; if you need such a shift, use a separate copy of this unit.

   2. [1 point] In the Control Unit Truth Table from the previous problem, flesh out the contents of the the Jump control line in the final column.

   3. [2 points] In the Control Unit Truth Table from the previous problem, flesh out the contents of the row for the JMP opcode.

2. [5 points] Assume R2 and R3 hold unknown 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.

   # 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
   8:  ADD R4, R4, R4
   A:  JMP 2
   C:  HALT # Stops execution.
   # What value is in R4?
   

   1. [3 points] Execute the program assuming R2 holds 5 and R3 holds 3. What are the final values in the registers R2, R3, R4, and R5 when the program reaches HALT? You may write your answers in either decimal or hex, but must use a 0x prefix for hex.
   2. [2 points] Try a few 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 valid C code of the form: R4 = exp;, where exp is a simple C expression using the the variables R2 and R3 (corresponding to the HW registers) and any simple C operations that accomplish the same effect as these combined HW instructions. exp must not include C statements like loops or conditionals.

5. Reconstructing Memories (RAM Puzzles) [13 points]

In these exercises, you will show how one or more provided RAMs (random access memories) can be used to implement a RAM with different dimensions that has the same number of stored bits as the provided RAMs.

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 and only if the Write Enable input carries a 1.
• Each RAM is indivisible and must be used as a “black box” (that is, you cannot modify the working of components inside each RAM).

Rules

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

• On the worksheet, connect inputs and outputs of the larger box with those of the smaller boxes representing RAMs, possibly adding combinational logic building blocks (e.g., muxes, decoders, gates) that make the logic correct.

• For each bus that contains a multi-bit value (e.g., Address); use hatch marks and width annotations to mark how many bits are carried by that bus. You must specify the number of bits (width of bus) carried by each bus (that is, all lines will be interpreted a single bit values unless they are annotated with a width).

• When a larger bus splits into or is joined from smaller buses, you must show which bit ranges from the larger bus correspond to the width of each smaller bus, as shown in the examples below:

Exercises

1. [5 points] Design a 256×8 RAM by adding minimal wiring and logic to two identical 256×4 RAM components. Label the widths (in bits/lines) of the ports Address, Data In, and Data Out for each 256×4 RAM you use and for the 256×8 RAM you implement.

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

   • Unlike the previous part, this one provided RAM component has the exactly same capacity as the desired final product, though it has different dimensions:
     • The provided RAM has fewer addressable memory locations (32K) than the RAM you will design (64K). (Hint: How many bits do you need to specify for the address for the provided RAM? That is, what is log₂(32*1024)?)
     • The provided RAM has a larger addressable unit of data (16 bits = 2 bytes) than the RAM you will design (8 bits = 1 byte).
   • The Data Out of the inner RAM supplies 2 bytes, but the Data Out of the outer RAM can provide only 1 byte. How will you determine which of the 2 bytes is chosen? (Hint: what combinational logic building block chooses between inputs?)
   • The Data In of the outer RAM supplies 1 byte, but the Data In of the inner RAM requires 2 bytes.
     • Where will the other byte that should come from such that only the supplied byte is written? Think carefully about the combinational logic to implement this.
     • If you join 2 1-byte buses to create a 2-byte bus, your wiring notation must unambiguously indicate which is the MSB and which is the LSB.

5 Extra Fun Affixed or Afloat in a C of Numbers

1. The Sea language (an imaginary programming language otherwise identical to C) supports a signed fixed8ths char type¹ using an 8-bit signed fixed point number system with precision to the 1/8 (eighths) place.

   1. What are the minimum and maximum numbers representable by a signed fixed8ths char? Write your answer as a base ten number using fractions or decimals.

   2. What are the minimum and maximum numbers representable by a signed fixed32nds char, which uses 8-bit signed fixed-point representation with precision to the 32nds place? Write your answer as a base ten number using fractions or decimals.

   3. 

      We provide a hardware adder design (at right) that supports 8-bit two’s complement addition (e.g., for signed char numbers). Draw a logic diagram for a hardware adder that supports the signed fixed8ths char number system. You may use the provided two’s complement adder as a black box (no need to draw the internals) and extend it with whatever wiring and logic is necessary. There is a “trick” here! Keep it simple.

2. Using the 6-bit floating-point encoding defined in these slides, give decimal notation of the numbers represented by the following floating-point encodings.

   1. 110101
   2. 100001
   3. 011100
   4. 000011
   5. 010010
   6. 111101

Submission

Please write your answers on the cs240-arch-worksheet-f23.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.