CSE141L Lab 3, Part A: Execution Unit Datapath

CSE 141L Homepage | Lab Overview | Lab Description

Deadline:	Nov. 14 at NOON
Changes:	None.

Lab Overview:

Congratulations on finishing up your fetch unit. By now you should have either designed your own ISA (if you are currently enrolled in 141) or leased an ISA design from one of the 141 teams. Time is short so to speed-up the process of implementing your processor, you will now be working with a partner of your choosing. In order to set your processor apart, you should come up with a unique "codename" for it.

While things are looking good now, there is still a lot of work left to be done. Namely, you need to implement the back-end (execution unit) of your processor. We are going to follow a similar path as we did for the front-end; we are first going to design the datapath first (part A), then implement control (part B). Finally, you will do a lot of debugging (to make sure that our customers don't end up with faulty chips) and optimize (lab 5). You'll also likely need to go back and change a few things in your front-end now that you have a target ISA. You may also find a few deficiencies in your ISA and will need to properly address them. Based on your previous performance, we know you can accomplish this monumental task though. Good luck!

Lab Deliverables:

For part A of this lab, you will need to create the datapath for your execution unit. Much like you did with your fetch unit, you will need to identify the major components of your datapath and implement them using RTL Verilog. You will then tie them all together using structural Verilog to get your completed datapath. Similar to labs 1 and 2, there are several questions that you need to answer in your report. Please make sure that you answer all of them. For this lab, you will be working with your partner. Since you each completed the fetch unit individually, it is up to you to decide who's fetch unit you will use. Again, there will be no interview for this part of the lab.

Demonstration: None
Progress Report: Your progress report will consist mainly of the answers to the questions posed in this lab. In addition, you will need to include all the Verilog files for your project. This includes the files for your fetch unit, your back-end and your overall processor. Do not include the random project files that are created by the Xilinx software, only the *.v files, the testbench files and the files generated by the "CORE Generator" application.

You will need to turn in an electronic copy by the deadline. Once again, the answers to the questions should be in a PDF file. The Verilog files (as well as your PDF) should be included in a ZIP file with the following name convention: cse141L-lab3-part_a-lastname1-firstname1-AND-lastname2-firstname2.zip. (The name of the PDF should be the same, except with the "pdf" extension instead of "zip".)

You will need to e-mail your ZIP file to Sat with the following naming convention for the subject: [CSE141L] Lab 3, Part A Submission - Last Name 1, First Name 1 & Last Name 2, First Name 2.

Lab Description:

Processor Overview: The "Big Picture"

In lab 2, we gave you the datapath design for your fetch unit. In this lab, you will be developing the execution unit's (i.e. the backend's) datapath on your own. Your guide will be your ISA, which will dictate which components you need to add to your datapath. Because we have split up the front-end and back-end of your processor, your processor will have at least 2 pipeline stages. You may choose how deeply to pipeline your backend, if at all. Just remember that there will be fabulous awards given to those with excellent designs and performance to get creative in designing your backend. Don't make it too complex though, as you don't have a lot of time to complete it.

The Processor Core Interface

The processor core is the top module of your processor design. It should instantiate two modules: your fetch unit and your execution unit. It should haves the following interface:

// D_WIDTH  : data width
// PA_WIDTH : port (i.e. IO channel) address width

module core#(parameter D_WIDTH = 34, PA_WIDTH = 4)
(
    input  clk,
    input  reset,
    
    // I/O interface
    output in_req,
    output out_req,
    output [PA_WIDTH-1 : 0] in_addr,
    output [PA_WIDTH-1 : 0] out_addr,
    input  [D_WIDTH-1 : 0]  in_data,
    output [D_WIDTH-1 : 0]  out_data,
    input  in_ack,
    input  out_ack
);

The core interface is simple - it consists of clk, synchronous reset, and I/O interface. The 'reset' signal should be "active low"; that is when 'reset' signal transitions from high to low, the processor core starts executing from address 0x0 of the instruction memory. The I/O interface provides the interface for in and out instructions, which communicate to the outside world. Since the available pins are usually very limited, the I/O interface multiplexes 16 channels into one physical channel to save the pincount. All I/O interface signals are edge-triggered.

The I/O interface is similar to a conventional bus interface. 'in' instruction asserts 'in_req' and 'in_addr', then waits for 'in_ack' to become 1. If 'in_ack' arrives, the backend stores 'in_data' into the register the 'in' instruction specifies. In the best case, the 'in_ack' signal will arrive in the next cycle, but it can be arbitrarily delayed if no data is available in the specified channel. In the waveform example below, the core asserts 'in_req' with 'in_addr' to 0xF. The core spends two idle cycles, then it stores 0x123 to the register file when 'in_ack' signal arrives.

'out' instruction works in a similar way; but the backend also asserts 'out_data' along with 'out_req' and 'out_addr'. After asserting a request, the backend waits for 'out_ack' comes. Like 'in_ack', 'out_ack' could arrive after an arbitrarily long delay, signaling the completion of a request. In the waveform example below, the core asserts 'out_req' with 'out_addr' to 0xF and 'out_data' to 0x123, then waits for 'out_ack' comes. When 'out_ack' signal is asserted after one cycle, the core completes out instruction.

The Frontend (Fetch Unit) Revisited

You already have a baseline frontend implementation, which allows the fetch unit to work independently of the backend. However, you may find that you need to modify existing fetch unit so that it can be well matched to your ISA.

Q1	Review your fetch unit and update it if you need to. If you make any changes, explain them and why they were needed.

The Execution Unit

The backend of your processor if where execution of instructions occurs. It should be defined structurally, i.e. it should simply consist of instantiations of modules. One of the tasks of this part of the lab is to create these modules using RTL verilog (and the "CORE Generator" utility from Xilinx).

The following is a list of the major modules that you will need to implement in your execution unit.

Register File:

A register file is essential to store register data of your processor. It should support read and write operations simultaneously, and have an interface along the following lines. (You may need to add more read/write ports.)

  // SEL_WIDTH : number of bits needed to specify a register
  // D_WIDTH : data width
  
  module regfile#(parameter SEL_WIDTH = 4, D_WIDTH = 34)
  (
	  input  clk,
	  input  we,
	  input  [SEL_WIDTH-1 : 0]  read_sel0,
	  input  [SEL_WIDTH-1 : 0]  read_sel1,
	  input  [SEL_WIDTH-1 : 0]  write_sel,
	  input  [D_WIDTH-1 : 0]    din,
	  output [D_WIDTH-1 : 0]    dout0,
	  output [D_WIDTH-1 : 0]    dout1,
  );

Note that writing a value to a register occurs at the clock edge, while reading a register does not involve any clock edge. In other words, 'we', 'write_sel', and 'dout' are edge-triggered, while 'read_sel0', 'read_sel1', 'dout0', 'dout1' are level-triggered as you see in the figure above. For example, if you assert 'we (write enable)' signal before the clock edge in a certain clock cycle with 'write_sel', 'din' will be stored in the specified register at the rising edge of the next clock. In contrast, if you change 'read_sel0' or 'read_sel1', 'dout0' or 'dout1' will be changed in the same clock cycle. Examine how a register file behaves in the following waveform. Note that the written value is updated at the clock edge, while 'dout0' and 'dout1' changes instantly when 'read_sel0' or 'read_sel1' changes. You might be able to implement a register file using flip-flops.

Memory Modules

Your processor has two memory modules - an instruction memory and a data memory. While the instruction memory is a part of the fetch unit, the data memory is located in the backend. You should use the provided wrapper module for the data memory. Like the register file, it allows read and write operations, however it does not support simultaneous read and write in a clock cycle. In one cycle, the data memory can serve either a read operation or a write operation.

Memory Wrapper Module: dmem.v (available here)
module dmem#(parameter A_WIDTH = 13, D_WIDTH = 34) ( input reset, input clk, input read_write_req, input write_en, input [A_WIDTH-1 : 0] addr, input [D_WIDTH-1 : 0] din, output [D_WIDTH-1 : 0] dout, output refused );

Data memory interface is straightforward. All the signals of the data memory module are edge-triggered, and you can assert the following signals for read and write operations.

read operation
'read_write_req' <= 1, 'write_en' <= 0
On the next cycle, refused or dout will be set. If refused is set, you will need to wait more cycles.

write operation
'read_write_req' <= 1, 'write_en' <= 1, 'din' <= 34-bit data to write
If not refused, the 34-bit data will be written to the specified location of the memory in the next clock cycle.

Then, why do we need 'refused' signal? 'refused' signal indicates that the memory module cannot service the requested operation at that time. There are a few reasons for the asserted 'refused' signal; the memory could be being refreshed; or another processor core has already been using the memory in the multi-core system. Although 'refused' signal is not used in this lab, your backend must be able to tolerate the 'refused' signal; if 'refused' is asserted upon a memory request, the backend should request the same operation until it succeeds.

In the waveform above, the core requests one write operation and one read operation. Unfortunately, the data memory cannot service the read operation, asserting 'refused' signal. Upon the 'refused' signal, the core requests the same operation in the next clock and successfully get the memory value in the second trial.
Other Modules

In addition to the register file and memory module, you would need other components in the datapath of the backend. In the case of the fetch unit, you used a few adders, a sign extender, and a few muxes to get the updated PC. For the backend, it depends on your ISA and how you implement it.

Q2	List all the other leaf modules needed for the backend of your processor. For each module, list all the instructions that use the module.

The Backend Interface

The backend of your processor should use an interface that is similar (if not identical) to the following:

// I_WIDTH  : instruction width
// IA_WIDTH : instruction address width
// D_WIDTH  : data width
// PA_WIDTH : port address width

module backend#(parameter I_WIDTH = 17, IA_WIDTH = 12, D_WIDTH = 34, PA_WIDTH = 4)
(
    input  clk,
    input  reset,
    
    // inputs from the fetch unit
    input  [I_WIDTH-1 : 0]  instruction_data,
    input  [IA_WIDTH-1 : 0] instruction_addr,
    input  instruction_valid,    
    input  [I_WIDTH-1 : 0]  load_data,
    input  load_data_valid,
    
    // outputs to the fetch unit
    output dequeue,
    output restart,
    output [IA_WIDTH-1 : 0] restart_addr,
    output load_store_valid,
    output store_en,
    output [IA_WIDTH-1 : 0] load_store_addr,
    output [I_WIDTH-1 : 0]  store_data,
    
    // I/O interface
    output in_req,
    output out_req,
    output [PA_WIDTH-1 : 0] in_addr,
    output [PA_WIDTH-1 : 0] out_addr,
    input  [D_WIDTH-1 : 0]  in_data,
    output [D_WIDTH-1 : 0]  out_data,
    input  in_ack,
    input  out_ack
);

Datapath Questions

Now that you have identified all the major components needed for the backend datapath, the next step is to design a datapath consisting of those modules you have identified. Make sure that your datapath can handle all the instructions of your ISA. Answer the following questions about the design of your datapath:

Q3	Draw the datapath schematic of the backend. Annotate all the relevant control signals as you saw in the fetch unit datapath schematic. Include the datapath schematic in your report. (Note: Powerpoint and/or hand drawing are fine. Schematic entries tools are often not worth the trouble.

Example Q & A

For Q4 and Q5, answer questions in the same style used in the following example.

Question: What happens when 'restart' and 'restart_addr' is asserted? Assume that 'load_store_valid' is not asserted.
Answer: Assume that 'restart' and 'restart_addr' are asserted in cycle 0.

Cycle 1: 'restart_addr_r' is fed to SRAM address field. 'fifo_clear' of the FIFO module is asserted to discard all the instructions in the FIFO.
Cycle 2: The instruction at the 'restart_addr' is available at the output of the data, feeding the FIFO. 'fifo_empty' becomes 1
Cycle 3: 'fifo_empty' becomes 0, but 'instruction_valid' is still 0
Cycle 4: Finally 'instruction_valid' is 1, and 'instruction_data', 'instruction_addr' are ready to be used in the backend.

The schematic is available here: example answer schematic

How does your processor handle the following situations?

'reset' is asserted
An execution of an instruction takes multiple cycles (e.g. the execution of 'in' instruction can take arbitrarily long time when input data is unavailable.)
The 'refused' signal of the memory module is asserted.

Note: Each of these is a distinct situation. You should three different explanations (1 for each scenario), not one explanation of a scenario where all three of these things happen at the same time.

Draw a path on your frontend and backend datapaths and explain on the cycle basis. Follow the explanation style of the example above.

For each instruction in your ISA, draw a path in the backend datapath which shows how the instruction is handled, and give an explanation on the cycle basis. You can group instructions into one drawing if they share the same datapath (e.g. add, sub, and mul will likely all be the same). Again, use the answer style used in the example above.

Coding & Implementation

Now that you have the datapath design, let's start implementing the datapath. You need to implement the following things:

Major components of the backend such as a register file and a data memory
A backend consisting of various leaf modules
A processor core consisting of a frontend and a backend. As you did in lab 2, you can use RTL Verilog for the implementation of leaf modules. However, you must use structural Verilog for the implementation of the backend and the processor core.

Q6	Implement a register file module for the backend of your processor in RTL Verilog, and name the file regfile.v. Include the full source file in your report.

Unlike for the register file, it is better to use a highly optimized memory generator for the data memory module rather than writing your own data memory module. Fortunately, Xilinx provides a utility named CORE Generator for such a purpose. Generate a data memory module that has 8K 34-bit words and name is 'dmem_34_8k'. You can follow the step-by-step coregen tutorial to do it. For the initialization of the memory module, use any COE file you generated in lab 3.

Q7	Write a testbench which tests whether your memory module is working correctly, and then actually test your memory module. Capture the behavioral simulation result screen and include it in your report. Make sure that you explain the setup of the testbench and also the results you give in your screen capture. The captured screen should clearly show 1) read and write operations work correctly, and 2) memory is properly initialized with the provided .coe file. The generated module should be used with the provided wrapper module dmem.v*.
Q8	Implement all the other modules required in your datapath. You have to implement each module in a separate .v file with RTL Verilog as you did for modules like adders, muxes, and sign extenders in lab 1. You might find that you can reuse many leaf modules used in the fetch unit. Also include full Verilog source code in your report.
Q9	Implement 'backend.v' in structural Verilog for the backend of the processor. You do not need to implement the control for the backend in this part of the lab. Since it is hard to test an implementation without control logic, it is enough to show that your Verilog file is synthesizable and implementable.
Q10	Implement 'core.v' as the top module of the your processor design. You can simply wire up the fetch unit and the backend. No control logic is required for 'core.v'.

This lab created by Donghwan Jeon, 2007. Modified by Sat Garcia, 2008.