Question 1

Using the RTL for pipelined mips from slide 29 of the pipeline lecture as a guide. Modify this RTL to use instruction and data cache with the possibility of stalls.

Replace the memory access in IF with I1[PC].data for the data, and I1[PC].ready as a boolean signal that is true on an L1 cache hit or after the data has been fetched from the L2 cache. Thus, you should not advance the PC and should send NOP to IF/ID.IR to cause a stall until the next instruction is ready. Similarly, replace the Mem[] in the MEM stage with D1[].data, checking D1[].ready before storing or before proceeding after a load. This assumes a write-back cache policy so at the RTL level, D1[].ready can be used to stall until the block is in L1 cache for both load and store instructions. For data stalls, you will need to make modifications to the RTL of earlier stages of the pipeline to prevent them from advancing on a data stall.

Question 2

The CDC 6600 was a computer designed by Seymour Cray (of supercomputer fame) in 1965. Among other things, this computer used 60-bit words. Instructions using only registers (R) took 15 bits, while those including an address (A) took 30 bits. Each word could hold multiple instructions (e.g. up to four R-type), but instructions were not allowed to be split across a word boundary. So, if you wanted to have an A-type instruction with only 15-bits left in the current word, you would fill with a 15-bit NOP (N) instruction, and start the A-type at the beginning of the next word.

  1. Write a program to empirically estimate the percentage of NOP instructions if the initial instruction mix (before adding NOPs) was 35% R-type and 65% A-type. You can do this by generating random stream of instructions of both types then padding with NOPs as necessary to obey the alignment constraints. Report the percentage of R and A in the original instruction stream, the percentage of words that have an R or A as their first instruction, the percentage of words that have an R, A or N as their last instruction, and the final percentages of R, A, and N per final instruction. Submit your source to this directory: 
    /afs/umbc.edu/users/o/l/olano/pub/611/EC2/$USER
  2. Derive the percentage analytically. Hint: the first instruction of the word has a different probability of occurrance than later instructions in the word, with A-type instructions more likely since they could be pushed into the first spot in the word from the previous word. This affects the probability of each of the other sequences that can occur in a word. Solving for the first-instruction probabilities is the key to finding the other statistics. If your program and analytic solution do not match, there's a problem with at least one of them.

Many of the details of the CDC 6600 for this problem were taken from Blaauw and Brooks, Computer Architecture: Concepts and Evolution. According to that source, the CDC 6600 could also only branch to addresses on a word boundary, resulting in still more NOPs (which I am not asking you to model). With these two sources (branch target alignment and instruction alignment), apparently 23% of compiled code for this machine was NOP instructions!