CS 3410 Spring 2019
Project Due: 11:59pm, Thursday, March 28th, 2019
Circuit Naming: Your top-level circuit must be named either "RISCV" or "RISCV32" (case-sensitive).
Late Policy: Two slip days can be used for the final submission. If a slip day is used, it will be used for both partners.
Read the ENTIRE writeup before you begin. This is cumulative. Both the Table A and the Table B instructions are required.
In this project you will extend and complete the processor design you started in project 2. However, in order to cut down on the amount of work you need to redo, we will provide you with some black box components for each stage in the pipeline. For this project we will use a split-memory "Harvard" architecture design: The Program ROM will store a read-only copy of the instructions, and a separate RAM will be used to store data for the program's execution. You will now implement all the other instructions mentioned in the last project, including load/stores, jumps and branches. You should base your circuit off of the principals you used in project 2. That said, you should build off of the release circuit that is posted under the project in CMS. This circuit uses the black box components in the CS3410 folder on logisim and works for all table-A instructions. You do not need to test these components.
Important: Consult the RISCV Handbook and make sure that all aspects of each of the instructions is implemented exactly as specified in the handbook, except where noted here.
You will also be expected to use Git throughout this project to maintain version control of your circuit and to ensure that you have an online backup available. At the end of the assignment, you will turn in a log of your git commit history in a text file. There are no specific restrictions on how often you should be committing, but it is highly recommended that you commit often and write meaningful commit messages so that you can restore old versions in case of failure. We will expect your commit log to show you made a genuine effort to accomplish this.
Academic Integrity. As one of the most widely studied architectures, RISCV has a wealth of information available on the web and in textbooks. You may consult any RISCV documentation available to you in order to learn about the instruction set, what each instruction does, etc.; however, we expect your design to be entirely your own, and your submission should cite any significant sources of information you used. If you are unsure if it is okay to borrow from some other source, just ask the TAs. If you are hesitant to ask the TAs or to cite the source, then it is probably not okay. Plagiarism in any form will not be tolerated. It is also your responsibility to make sure your sources match the material we describe here (warning: the top Google hit for "RISCV reference" contains several inaccuracies).
In this part of the project you will write a function in assembly in order to test the processor that you will build.
A Fibonacci sequence is characterized by the fact that every number after the first two is the sum of
the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... The sequence F of Fibonacci
numbers is defined by the recurrence relation: F(n) = F(n-1) + F(n-2), with seed values
F(0)=0 and F(1)=1.
You will implement the Fibonacci
function, which compute the n-th number, F(n), in the Fibonacci sequence. For instance,
Fibonacci(12) returns 144. because the sequence starting at
F(0)=0 and F(1)=1, and goes by 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
There are several ways to compute the Fibonacci sequence. You will implement all three of the methods below (please do not submit RISC-V code with any form of main function)
Iterative Fibonacci:
int i_Fibonacci(int n) {
int f1 = 0;
int f2 = 1;
int fi;
if(n == 0) {
return 0;
}
if(n == 1) {
return 1;
}
for(int i = 2; i <= n; i++) {
fi = f1 + f2;
f1 = f2;
f2 = fi;
}
return fi;
}
Recursive Fibonacci: Simple but inefficient. Logisim will be too slow to use this version except when the index is small.
int r_fibonacci(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
return r_fibonacci(n-2) + r_fibonacci(n-1);
}Memoization Fibonacci: For computing the answer for more than one index, it makes sense to remember previously computed answers since answers for larger indices require answers for smaller indices. So if fibonacci(40) and fibonacci(39) has already been computed, then it is easy to compute fibonacci(41). This memoization version is essentially the same as the recursive version but takes two extra arguments: an array log_array of previously computed answers (should be initialized to all zeros), and the number of entries size in the array.
Note: the memoized Fibonacci does not allocate or initialize the
array. It assumes that the function calling m_fibonacci has already
created an array of size size and initialized every entry to zero.
int m_fibonacci(int n, int log_array[], int size) {
if (n < size && log_array[n] != 0) { // non-zero means we already computed this
return log_array[n];
}
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
int answer = m_fibonacci(n-2, log_array, size) + m_fibonacci(n-1, log_array, size);
if (n < size) {
log_array[n] = answer; // save answer for reuse later
}
return answer;
}Implement these three versions of the Fibonacci function using RISC-V assembly code. They must all work on your processor in Logisim, though you will have to be careful when testing to select indices whose Fibonacci number can be computed in a reasonable time.
Testing and input for Fibonacci functions
Your Fibonacci functions are just that: functions. They should get
their inputs from the argument registers (a0,
a1, etc.) and they should return their results via register
a0. To test the functions, you will nead to create a "main"
program which initializes the stack (by setting sp and
fp to something reasonable and usable), puts some input in the
argument registers, then calls the function via JAL. The
Fibonacci functions never make system calls or any other function calls that
could possibly read input from the user. Your main program could if you
managed to wire up a keyboard though.
You will implement a five-stage RISCV pipeline, which is the most common organization for RISCV and is similar to what is described in the book and in class:
Implement all of the instructions in Table A and B. The decode component you get gives you a one hot encoding for each instruction and the register values and potential immediate value. You may have to add additional decoding logic for any new control signals you introduce, as for the memory stage and for the PC update. We will give you the forwarding logic you implemented in P2, however you may need to add additional control logic.
| Table A | |
|---|---|
| Arithmetic | ADD, ADDI, SUB, AUIPC |
| Logic Operations | AND, ANDI, OR, ORI, XOR, XORI, SLT, SLTI, SLTU, SLTIU |
| Shifts (constant and variable) | SRA, SRAI, SRL, SRLI, SLL, SLLI |
| Immediate load | LUI |
Note that LUI doesn't access memory and so, despite its name, it is more similar to an arithmetic or logic instruction than a memory load instruction.
| Table B | |
|---|---|
| Jumps | JAL, JALR |
| Branches | BEQ, BNE, BLT, BGE, BLTU, BGEU |
| Memory Load/Store (little endian) | LW, LB, SW, SB |
Our testing programs will include a mixture of all the instructions from projects 2 and 3, so you must ensure that the instructions from project 2 are correctly implemented as well.
Deviation from the RISCV standard: You can ignore any RISCV instruction or feature not mentioned in this document, such as traps, exceptions, and system calls. You can also assume that your processor will never encounter anything but legal instructions from the lists above. There are other RISCV instructions, however you will not be responsible for knowing/implementing them.
Refer to the RISCV manual linked on the course web site for a full specification of what each of these operations does. Except where noted in here, the RISCV manual is the authoritative specification for this project: information you find elsewhere (e.g. Wikipedia or the book) doesn't count if it contradicts the RISCV manual.
Memory load hazard. Memory operations should use stalling to avoid hazards. That is, you should introduce a bubble in the pipeline after a memory operation, but only if a hazard is detected.
RAM. The "CS3410 Components" library in the most recent version of Logisim includes a RAM component for your memory stage. Logisim does not support RAM components large
enough to cover a full 32-bit (4GB) address space. The largest RAM component contains 64MB of data using 24-bit-wide
word-addresses. Our tests will rely on memory addresses in the lowest 1MB of the address space, so your your processor
should contain at least 1MB of RAM placed at the lowest addresses. That is, reads and writes to byte-addresses
in the range 0x00000000 to 0x000fffff should work as expected.
Important: Writes to addresses that are not backed by any RAM should
have no effect, and the address space should not "wrap around" after 1MB.
For the adventurous. Instead of having a single RAM component backing the low part of the address space, you can add multiple RAM components to cover various convenient pieces of the address space. For instance, to support the conventional MIPS program layout, put a second RAM to cover a few MB of address space near addresses 0x10000000 for program data, and a third RAM to cover addresses just under 0x80000000 for the stack. Or you can redirect reads and writes at certain addresses to some of Logisim's input/output devices. It is actually fairly trivial to make writes at addresses just above 0x80000000 write coordinate and color pixel data to an LCD screen component or ASCII characters to a TTY component. Similarly you can make reads at some designated unused address read from a Logisim Keyboard, Joystick, or other input component. Bonus points if you can code pong to go with an LCD.
Build your RISCV processor as a single Logisim circuit file. Do not use Logisim's Project > Load Library > Logisim Library command to import circuits from other Logisim files.
Your top-level circuit must be named "RISCV" or "RISCV32" (case-sensitive).
Blackbox Components: You will be using Blackbox components for this project so that you will not need to redo work from P2. Exact specifications on the inputs and outputs of the various components are available in the components guide on the resources page of the course web site.
Register file. Don't attempt to create your own register file out of regular Logisim Registers. This one makes debugging and simulation much easier. The register file must be visible either in the toplevel circuit or one level down in a subcircuit. Do not nest the register file in two or more levels down!
ALU. You must use the ALU from this library, rather than your ALU from project 1. Your design may only contain one ALU.
RISCV Program ROM. We will implement a Harvard Architecture design: The Program ROM component will store a read-only copy of the program instructions. The Program ROM component can load and display RISCV assembly language, which helps with debugging and saves you from having to write test programs in machine language.
The restriction on incrementers, comparators, and adders have been changed since Project 2:
You can additionally use any of the components that come with Logisim, such as a Register for the PC, multiplexers, and so on.
Write a test program file for Logisim containing RISCV assembly that fully tests all aspects of your
processor; it should be able to be run by loading it into the Program ROM. The test program should demonstrate
that the processor's behavior conforms to all specifications given here and in the RISCV reference manual.
This is a critical step, and you should spend a fair amount of time developing a comprehensive test program
that exercises all of the different instructions and features of your processor. The program should be well
commented, indicating what it is doing (random vs. targeted, and what target) and what results should be
expected when running the tests, so that the course staff is convinced of the correctness of your processor.
All test cases should be included in a single file, and the quality and thoroughness of the tests will be
graded.
Since the RISCV processor does not use input and output pins in the same way as the ALU, you will not be able to test your cicuit as a whole using test vectors. You must use your RISC-V test program to evaluate the correctness of your processor. However, test vectors may be useful for debugging some of your subcircuits.
Don't forget to include every possible instruction in your testing program.
We would also like you to test your program on a complex computation. As such, you should implement the Fibonacci sequence in iterative, recursive, and memoized styles.
Document your design in the same fashion as project 2. Be sure to revise your block diagram to show any new components, and to revise your descriptions of control and instruction decoding logic to account for any changes or additions.
Help. Ask the instructor, TAs and consultants for help. We also expect to see most students in office hours during the course of the project. Extra hours will be scheduled as needed. Also check Piazza for more help.
Bugs. If you suspect a bug in Logisim or the CS3410 library, ask the course staff for help.
Really, it shows. Do a pencil-and-paper design before implementing in Logisim. We will penalize poorly laid-out designs that are hard to understand.
Read the docs. Refer to the components guide, the design guidelines, the tips and tricks page, and the RISCV manual often.
RISC-V calling conventions and program layout. The three versions of Fibonacci must be implemented as functions: they should take arguments and return results in registers (or on the stack), and use a call stack for recursive invocations. For this project, you are required to follow RISC-V calling convention (as covered in class and lab) precisely. You are expected to create these functions manually.
Testing. Please make sure you are running the most recent Logisim version. Update it when prompted and look at your autograder sanity check results to be sure. Writing a testing script to help generate assembly instructions is certainly recommended, however, edge cases and test completeness are more important than having thousands of random cases. If you have no edge cases nor specification tests, significant points will be deducted from your final score! Please keep in mind that Course Staff would rather see 50 edge cases than 2000 random cases. But doing both is even better.
Ensure that your circuit sticks to the following rules, as well as the Logisim design guidelines to avoid losing points!
CS3410 Components. Do not duplicate any of the provided CS3410 components in your circuit. At most one of each should be used. Note that duplicates of some of the components, such as the register file, will break the autograder, even if placed in an unused subcircuit, so ensure that any extras are removed before submission to avoid losing points.
Clock. You should only have one clock in the entirety of your circuit. Subcircuits requiring a clock signal should use input pins to connect to the processor clock. Your RISCV design should use a rising clock edge to define the boundaries of clock cycles: during the first half of each processor clock cycle the clock is 1; during the second half of each cycle the clock is 0; and the end of the cycle is when clock transitions from 0 to 1. By default, most Logisim memory components (Registers, D Flip-Flops, etc.) are triggered on the rising clock edge, so you can leave them as is. The register file is the only component that may use a falling clock edge, and can be so configured using the attributes panel. In order to avoid read-write hazards, you will either want to change this setting, or negate the clock signal going into the register file (think about why this works).
Comparators, should be used as outlined a few sections above.
Demultiplexors should not be needed for this project, and you should avoid using them.
Tunnels, if used at all, should be used sparingly and only when they make your circuit significantly easier to read. You should be able to complete this project without the use of tunnels.