Homework 9

22C:122, Fall 1999

Due Monday Nov 22, 1999, in class

1. Background: Assume you have the example machine we've been studying, with a 5-stage pipe, and with the following complication: During each clock cycle, the memory can only perform one load or store. The Operand Store stage has first priority for memory access, the Operand Fetch stage has second priority, and the instruction fetch stage has first priority. If the instruction fetch stage cannot get to memory during a cycle, it injects a bubble. If the operand fetch stage cannot get to memory during a cycle, it stalls, injecting a bubble. In the absence of interlocks, the machine runs exactly 1 million cycles per second.

                          ______        |
   Instruction Fetch     |______|-------+--
                          |____|   _    |
   Address Computation   |______|-| |   |
                          |____|  | |   |
   Operand Fetch         |______|=| |---+--
                          |____|  |R|   |
   Operate               |______| | |   |
                          |____|  | |   |
   Operand Store         |______|=|_|---+--
                                       _|_
                                      |   |
                                      | M |
                                      |___|
   

   In addition, consider the following: Assume that 1/3 of all instructions reference memory. Assume that 2/3 of the memory reference instructions require the operand fetch interface, while 1/3 require the operand store interface. None require both.

   Part A: Why was it specified that the operand store stage had first priority. What would happen if the instruction fetch stage had priority.

   Part B: How many instructions per second can this machine execute, assuming straight line code with no operand interlocks?

   Part C: Assume 2-way interleaved memory:

                          ______        |     |
   Instruction Fetch     |______|-------+-----+--
                          |____|   _    |     |
   Address Computation   |______|-| |   |     |
                          |____|  | |   |     |
   Operand Fetch         |______|=| |---+-----+--
                          |____|  |R|   |     |
   Operate               |______| | |   |     |
                          |____|  | |   |     |
   Operand Store         |______|=|_|---+-----+--
                                       _|_   _|_
                                      |   | |   |
                                      | M | | M |
                                      |___| |___|
   

   Assume that each operand has equal likelyhood of being found in either memory module. How many instructions per second can this machine execute in straight line code with no operand interlocks?

   Part D: Assume a cache C used only by the instruction fetch pipeline stage, as shown below. This cache has a 10% (random) miss rage. Now how many instructions per second can our machine execute?

                          ______            |
   Instruction Fetch     |______|-------o---+--
                          |____|   _   _|_  |
   Address Computation   |______|-| | | C | |
                          |____|  | | |___| |
   Operand Fetch         |______|=| |-------+--
                          |____|  |R|       |
   Operate               |______| | |       |
                          |____|  | |       |
   Operand Store         |______|=|_|-------+--
                                           _|_
                                          |   |
                                          | M |
                                          |___|