Assignment 1: Pipelined CPU Design and Implementation

Outline#

If you have not completed the tasks in the above labs or do not understand the content, we strongly recommend that you first complete the labs and then start the assignment.

Background#

You have been building the single-cycle CPU for the QuAC ISA from the ground up during the first six labs. The first part of this assignment will require you to submit the single-cycle CPU that conforms to the QuAC ISA. The second part focuses on implementing a pipelined CPU that conforms to the same specification.

Part 1#

For the first part of the assignment, your task is to deliver a single-cycle CPU in Digital that implements the full QuAC ISA specification.

If you have already completed the first six labs that result in a CPU for the QuAC ISA, then congratulations! You have already completed the first part of the assignment.

We will use automated marking for the first part of the assignment. You will receive a mark calculated by the number of passing tests. The tests will be similar to the ones we provide here. You can use these tests to obtain an indicative mark for this part of the assessment. Note that attempting to subvert the tests is academic misconduct. We will manually mark submissions where we believe that the test results do not accurately reflect the quality of the work submitted.

Part 2#

Your task in the second part of the assessment is to build a pipelined CPU for the QuAC ISA. The CPU must conform to the full QuAC ISA specification. You should consult the lecture slides (weeks 3-4) for ideas, but remember that the ARM and MIPS instruction sets are different from the QuAC ISA. Your pipelined CPU should be tailored to the QuAC ISA.

You may assume the absence of any self-modifying code, which means that the contents of a memory location are either instructions or data but not both.

We will mark the second part of the assessment based on your justification for your design choices and your analysis of your final implementation (details below).

Tasks#

We ask everyone to attempt the following three tasks. These tasks are listed approximately in the order of increasing difficulty, and we recommend approaching them in this order. These tasks transform your single cycle CPU into a fully functional pipelined one. We use codenames for each task, which will help guide the interview.

1. (BPIPE) Identify the pipeline stages and implement them. You need to decide (1) the number of pipeline stages and (2) what happens in each pipeline stage. You should take into account any structural hazards. You should strive to balance the pipeline stages so the internal fragmentation is minimized. You can take inspiration from the lecture slides. We discussed fragmentation in the slide deck for the third week (slides 48-57). To correctly execute instruction with BPIPE, you might need to insert bubbles (nops) in your program. You may alternatively insert nops in hardware instead.

2. (DPIPE) Detect and handle data hazards. Your next task is to identify and handle all data hazards in your pipelined CPU. DPIPE should be able to execute programs where the source operands of an instruction are produced by the most recent instruction behind it in the pipeline. Note that DPIPE should handle instructions (other than those that modify the PC) which execute conditionally based on the outcome of the previous instruction.

3. (CPIPE) Detect and handle control hazards. Your final task is to handle control hazards due to jump and conditional jump instructions. Note once again that your pipelined CPU should be able to execute programs with jumps and conditional jumps where the outcome is determined by the previous instruction.

The following are extension tasks. It would be best if you only attempted them once you fully completed the abovementioned tasks. It is not required to try these extensions to get good marks, and if you attempt the tasks above and couple that up with good analysis and insights, then you have a high chance of receiving an HD grade. These tasks exist for those who want to push themselves with an extra challenge.

1. Improve the performance of your CPU on jumps. The performance of a pipelined CPU depends on its ability to keep the pipeline full and running smoothly. Depending on your implementation of CPIPE, the pipeline may run inefficiently (i.e., with idle stages that do nothing useful in a specific cycle). Now, improve your CPU to keep the pipeline as full as possible in the event of jumps.

2. Remove the dual port memory abstraction. Replace the dual port RAM component with a single port RAM component (ask on the class forum if you are unsure which components qualify) and resolve the resulting structural hazards.

3. Allow all memory locations to be simultaneously writeable and executable. Remove the limitation that memory addresses can either be executed or written to and enable your CPU to execute self-modifying code.

As you design and implement your CPU, you should consider the following questions:

• How does your design improve the speed of individual instructions and the overall instruction throughput? It may be helpful to consider the critical path of your CPU. Note that Digital models all components with a uniform delay. This modeling approach is not realistic. One possibility is to research the reasonable delays for the components you use.
• What is the hardware cost of your design and implementation? You should rely on rough estimations and back-of-the-envelope calculations of the gate count needed for each CPU stage.

Assessment of Part 2#

The assessment of the second part of the assignment consists of three parts:

• Your Digital design files
• A short report (500 words max.) that provides an overview of your pipelined CPU, including the optimizations and capabilities of your CPU
• A 15-minute interview

Your Digital design files are self-explanatory. These files must be submitted as part of your assignment repository on GitLab by 19 September 2022, 23:59. We will not accept any push to the repository after the assessment deadline.

You will submit a short report of no more than 500 words giving an overview of what you have accomplished in this part of the assignment. This report is not worth any marks by itself. The goal of this report is not to justify your design or explain considerations; we will use it instead to understand what you have done. This report will help guide the discussion in the interview. The report should highlight the different parts of your CPU, which of the tasks in the second part of the assignment did you attempt, and any critical design considerations. It is in your interest to write a concise report as this will allow a more in-depth discussion in the interview focusing on analysis and justification of your design rather than wasting time explaining what your CPU can do. Submitting this report is a prerequisite to attending the interview. The report is due alongside the Digital design files on 19 September 2022, 23:59.

Most of the assessment for this part of the assignment will be an interview between you (and your group member) and the course convener. These interviews will take place on 22-23 September 2022. Each group must schedule a time when both members can attend. We will release more information regarding scheduling interviews shortly. The interview will consist of a 15-minute discussion between us and yourselves where you will have the opportunity to explain and justify your design. You do not need to prepare a presentation. We will ask questions based on your submitted design and report.

All group members must attend the interview if you are working in a group. If you know you cannot participate in your interview, please contact the course convener as soon as possible. Postponing assessments is always possible with good reason, and good reasons are primarily issues that are not under your control. For example, if you feel sick on the day of your interview, please do not attend. See a doctor instead and provide a certificate that indicates your condition. If you already know beforehand that a specific assessment date or deadline does not work for you, then contact us immediately, and we will work something out for you. In the interest of fairness, we will always require good reasons, specific to you and not under your control.

Deliverables#

• We provide the file single-cycle/cpu.dig as a template for the first part of the assignment. You should build (or copy) your CPU for the first part in this file. We will test only this provided file. Note that if your CPU is in the wrong file, we may not mark it. For any other additional sub-circuits (e.g alu.dig, reg_file.dig, control_unit.dig), you should place them in the single-cycle/ directory.

• We provide the file pipelined/cpu.dig as a template for your pipelined CPU (part 2). You should build your pipelined CPU in this file. For any other additional sub-circuits (e.g alu.dig, reg_file.dig, control_unit.dig), you should place them in the pipelined/ directory. If a sub-circuit is required for both parts, you should ensure it exists in both the single-cycle/ and pipelined/ directories.

• You are also required to submit a short report of no more than 500 words as report.pdf in the top-level directory (see here for details). The report must contain the names and UIDs of all group members.

Working on Your Assignment#

Please follow the process below for working on your assignment submission.

1. One group member forks the assignment 1 template repository
2. On the forked project, go to ‘Members’ in the left side panel
3. Add the other group member
   1. Search for their UID
   2. Change role to ‘Maintainer’
   3. Click ‘Invite’
   4. Check they appear as a maintainer in the members list at the bottom. You will also see a marker bot account down here; leave this as it is.
4. Both members can now clone the forked project to their computer. I.e., the one with the forking group member’s UID in the URL. Do not clone the template repository.
5. Regularly commit and push your changes to the GitLab server
6. The last commit that you push to GitLab before the submission deadline will count as your submission. Please push your work regularly.

Group Work with Git#

Git supports concurrent modification, but its conflict resolution support is not ideal for the circuit files. Try only to have a single member editing a given circuit file at a time for your circuit files, and push your work before the other member pulls and starts working on it.

Submission Checklist#

1. Our CPU in single-cycle/cpu.dig implements the full QuAC ISA.
2. We have run the provided tests on single-cycle/cpu.dig and there are no errors.
3. Our CPU in pipelined/cpu.dig implements the full QuAC ISA.
4. We have pushed all our work to GitLab, and we can see all of our work on GitLab.
5. Our report is at the top-level of our project repository as a PDF file called report.pdf.
6. Our report PDF includes all the necessary references/acknowledgements, and everything not mentioned is our group’s original work.
7. We can read the contents of report.pdf using the GitLab file viewer interface (corrupted PDFs are not accepted).