Quiz 1

Problem Q1.1.

[8 pts] In studying a program, Eva Lu Ator identifies that it has three phases: It spends 50% of its time in the first phase; then it proceeds to the second phase, where it spends 10% of its time; and finally it enters the third phase, where it spends 40% of its time.

a. Eva first notices radical inefficiencies in the second phase. If she rewrites the second phase to be ten times faster, how many times faster will this new program be overall? (Show your work.)

b. Eva reconsiders: Rather than change the second phase, she looks very carefully at the first phase and discovers how to make it 25% faster. How many times faster will this new program be overall? (Show your work.)

c. If Eva has time to pursue only one of these two options, should she improve the first phase by 25% or the second phase by ten times?

Problem Q1.2.

[14 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 compute f(1) + f(2) + … + f(100). For example, if f is the squaring function (f(n) = n²), then your subroutine would return 338,350, since this is the result of 1² + 2² + 3² + … + 100².

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

sumTo100: addi $sp, $sp, -16
          sw $s0, 0($sp)
          sw $s1, 4($sp)
          sw $s2, 8($sp)
          sw $ra, 12($sp)

          # your code here

          lw $s0, 0($sp)
          lw $s1, 4($sp)
          lw $s2, 8($sp)
          lw $ra, 12($sp)
          add $sp, $sp, 16
          jr $ra

Problem Q1.3.

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

loop: lw $t0, 4($s0)
      add $s0, $s0, $t0
      bne $t0, $zero, loop
      nop

Problem Q1.4.

[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.

lw $t0, 4($s0)	IF	ID	EX	MEM	WB
lw $t1, ($t0)
xor $t2, $t0, $t1
addi $t3, $t2, -1
and $t4, $t2, $t3

Problem Q1.5.

[8 pts] Suppose we have a two-way set-associative cache with four 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 at left below, and we then access the address sequence 0x00, 0x74, 0x1C, 0x8C, 0x10, what will be the final status of the cache?

set	MRU?	data
0	0	M[0x00–0x0F]
	1	M[0x40–0x4F]
1	0	M[0x10–0x1F]
	1	M[0x50–0x5F]

Problem Q1.6.

[10 pts] Suppose we have a 7-stage pipeline.

The branch prediction is determined by the end of the first stage.
The jump/branch destination is determined by the end of the third stage.
The branch decision is determined by the end of the fourth stage.

Assume that 5% of instructions executed are jumps or calls, while 15% are branches (of which 2/3 are taken). And you should assume that the branch prediction algorithm is correct 95% of the time (whether the branch is taken or not taken). How many clock cycles does the average instruction take before the next instruction is issued? (Ignore data and structural hazards, as well as memory access delays.) Show your work.