[8 pts] Microprocessor clock rates grew at a quick clip from 1988 to 2003, going from 16 MHz to 3.2 GHz. But then the race for faster clock rates essentially stopped. Why?

[8 pts] Ben Bitdiddle has been charged with improving the performance of a single-threaded program. He identifies two phases to the program: It starts in the first phase, spending 40% of its time there, before proceeding to the second, where it spends the remaining 60% of its time. Furthermore, he notices that the first phase is very amenable to parallelization, and he proposes to rewrite it so it will go four times as fast on a quad-core computer.

a. Fill in the blank: On a quad-core computer, Ben's revised program with the first phase parallelized will be at most    times as fast as the old program. (Show your work.)

b. Name the law that applies to this scenario of speeding up a portion of a system.

[8 pts] Disassemble each of the following MIPS machine language instructions into assembly language.

[8 pts] Translate the following MIPS “program” into machine language (binary).

[8 pts] Define the assembly language term “delay slot,” and explain why some instruction set architectures include it.

[12 pts] Suppose we decide to add a new instruction lwo to the MIPS instruction set to allow accessing memory based on the sum of a base register and an offset register. In an assembly program, it would appear as “lwo $t0, $t1($s0)”. Define how to encode such an instruction while keeping our circuit implementation simple; explain your answer.

[12 pts] Write a MIPS subroutine that takes one parameter providing the address where a subroutine f begins; this parameter subroutine f (which you can call using jalr) takes an integer parameter and returns an integer. Your subroutine should repeatedly invoke f starting from 1 until it exceeds 1,000, and it should return the number of times f was invoked. For example, if f is the quadrupling function (f(n) = 4 × n), then your subroutine would return 5, since f(f(f(f(1)))) is 256 while f(256) is 1024.

The provided code in the template below handles saving some registers to the stack and restoring them at the end.

[8 pts] Define the pipelining term structural hazard, and provide an example where a structural hazard arises.

[10 pts] Complete the following diagram of how instructions progress through the classic five-stage pipeline, assuming that the processor supports data forwarding. Draw arrows indicating points where forwarding is necessary.

[16 pts] The following table summarizes an 8-stage pipeline with branch prediction.

However, inserting pipeline registers requires adding 0.05 ns to the time for the stage.

a. If we use this eight-stage pipeline, what is the best time per clock cycle? Explain your answer.

b. If we combine pairs of stages into one (S0 and S1 collapse together, then S2 and S3, then S4 and S5, then S6 and S7), what is the best time per clock cycle? Explain your answer.

c. Returning to the original eight-stage pipeline, assume that 5% of instructions executed are jumps or calls, while 20% are branches (of which 3/4 are taken). And you should assume that the branch prediction algorithm is correct 90% of the time (whether the branch is taken or not taken). How many clock cycles does the average instruction take in the 8-stage system? (Ignore data and structural hazards, as well as memory access delays.) Show your work.

[10 pts] Suppose we have a two-way set-associative cache with eight lines, each containing sixteen bytes. The cache uses a least-recently-used policy to replace lines; in the tables below, the “MRU?” column represents which line is most recently used within each set.

If the cache has the initial state diagrammed below, and we then access the address sequence 0xFC, 0x84, 0x18, 0x78, 0xB0, 0xDC, 0x00, what will be the final status of the cache?

[8 pts] The following table summarizes a two-layer cache system, providing the size and associativity of each cache, along with the time to access the cache and the fraction of overall program instructions that incur a miss on that cache while accessing data.

a. Ignoring the time to fetch instructions, and ignoring any pipeline hazards, what is the average time per instruction? Show your work.

b. If we removed the L2 cache, keeping only the 16 KB L1 cache and RAM, what would be the average time per instruction? Show your work.

[24 pts] After studying the 5-stage RISC pipeline that we've been using, Betsy Bitdiddle observes that a large fraction (maybe 25%) of load/store instructions use a displacement of 0. Since these load/store instructions don't need the EX stage for computing the memory address, she suggests that they should skip directly from the ID stage to MEM. Of course, the ID stage would need to identify such instructions, but that is straightforward enough that it doesn't lead the ID stage to take longer.

a. What complexities does Betsy's design entail, and how can the circuit be modified to support her idea?

b. If Betsy's idea were implemented, in what circumstances will the modified CPU be able to complete programs faster? Your explanation should include a specific example of a code sequence, and it should discuss how performance is improved in that example.