CSE 378 - Autumn 2002

Purpose:

This assignment is to be done in pairs. You must work with a different person than you did on Homework #5.

Tasks:

Task 2: Write a (main-program) function that counts the number of 1's in both the first (bits 0-15) and second (bits 16-31) halves of the binary representation of a word, and then returns the difference of the two (i.e. <bits in 1st half> - <bits in 2nd half>).  Then run this program on your machine.

The Details

Pipeline:

The pipeline is:
Fetch -> Register Read -> Execute -> Memory Access -> Register Writeback
See Figure 6.40 in your book for a detailed explanation of the pipeline stages.

Data hazards:

You should implement data hazard detection and forwarding logic to resolve data hazards. For load delays, if a consumer instruction of a loaded value follows the load instruction, your pipeline will have to stall until the load has returned from memory (see figure 6.46). For arithmetic operations, forwarding logic should be sufficient to resolve hazards.
NOTE: We have been talking about hardware that writes to the register file in the first half of the clock cycle, and reads from it in the second half. Unfortunately, SMOK does not work this way. For this reason, you will need to have additional forwarding that goes from the WB stage to the ID stage. Or you may find some other solution to this problem.

Branch hazards:

You will need to handle branch hazards. The basic problem is that your pipeline doesn't know it has fetched a branch instruction until the decode stage, doesn't know the result of the branch condition until the end of the EX stage, and doesn't change the PC value until the MEM stage. By then it will already have fetched the following sequential instructions. Design hardware to handle branches and control hazards. This will involve deciding in which stage your branch resolution hardware should be and squashing any wrong-path instructions that are fetched. Depending on where you place your branch resolution hardware, you may or may not have to extend the forwarding logic you built to eliminate data hazards.

Memory layout:

Use the same memory layout as Homework #5.

Instructions:

Support the following instructions:

Arithmetic:

ADDU, ADDIU, SUBU
AND, SRL <--------- these are new for HW6

Load/Store:

LW, SW

Branch:

BEQ, BNE

Startup code:

You can begin with Homework #5's startup code and modify it as appropriate, but you shouldn't need much. You can just plunk your code down at address 0, and put some kind of termination at the end of it.

The executing program:

Write a new procedure in MIPS assembly and compile it down to the instructions you implemented. This procedure is called diff_halves(int x). What this procedure does is it counts the number of 1 bits in the first and second halves of a word and then calculates the difference of the two (bits in first half - bits in second half). In C this procedure may look like:

int diff_halves(int x){

  int first_half, second_half;
  int count;

  while( count <= 15 ) {
    if ( (x & 1) != 0 )
      first_half = first_half + 1;
    x = x >> 1;
    count = count + 1;
  }

  while( count <= 32) {
    if ( (x & 1) != 0 )
      second_half = second_half + 1;
    x = x >> 1;
    count = count + 1;
  }

  return first_half - second_half;
}

Please follow register conventions--put arguments and return values in the appropriate places, so your code is easy to test.

Performance

Although your primary goal is to design and implement a correctly functioning pipeline and to write a correct test program, try to implement efficient versions of them both. How many cycles does it take to execute your code on your pipeline? How many cycles does your pipeline stall when executing this code? (For both of these questions, you can use the input 0x0007FFC0 but feel free to test cases of your own design as well.)

Written Report

Write a short report (one to two pages is sufficient) describing:

• the design decisions you encountered, with your choices justified. Be sure to mention what parts of the design you thought were tricky or that you found a partiticularly nice solution for;
• how you tested your machine, and how you debugged it;
• what you learned, and what you had trouble with;
• the distribution of work between partners.

Turnin

Turn in your code online, using this form, and turn in your written report in class. Please submit only one set of files per group -- there is no need for you and your partner to both submit code (or written reports) separately. Just make sure to indicate both partners' information on the turnin, so you will both get a grade. Both written and code parts are due before class on November 25. I suggest you finish the code part early, and leave time to describe it well in the written report.

EXTRA CREDIT:

• Implement JAL, JR, and the other necessary opcodes to make fibonacci work, then convert your code and run it. How much faster is it than on the previous implementation (homework 5)?
• Add a branch predictor. This will be a simple predictor that simply predicts the last address of the branch. This is nominally called a "branch target buffer" (BTB). What you do is take the address of the control instruction in the 2nd pipeline stage and feed the low bits of the address to a table (use a memory of 16 entries). From this table start fetching in the next cycle from the outcome of this table. When you resolve the actual branch target, write this target into the table location of the branch address. If you predicted the branch target correctly, then you can keep fetching and executing. However, if you predicted incorrectly, you will need to squash the instructions that were incorrectly fetched (but not the delay slot instruction!).

Grading:

1. functionality of diff_halves on your machine (does diff_halves perform the correct function?)
2. correctness of your machine (do all the instructions on your machine work correctly?)
3. design of your machine (is it understandable, are the design decisions you made justifiable?)
4. your written report

Hints:

• The design given in the book and in lecture is not set in stone. You can move functionality, i.e., logic and components, to one side or the other of a pipeline latch as you see fit. Ideally, you want each stage to take the same amount of time, but for this assignment you don't need to be too worried about that. Just don't go overboard -- don't putt all your functionality into one stage and leave several stages empty.
• You may find it necessary to initialize your pipeline with a nop instruction, to avoid unwanted side effects when starting your execution. You can do this by setting an initial value for the appropriate ControlRegisterRegisters in the IF/ID latch.
• To do the SRL operation efficiently, think 'binary'.