Final

Instruction-level parallelism refers to opportunities to execute simultaneously different instructions from the same instruction stream, even though the stream is written as if it is sequential. Pipelined and superscalar architectures are two techniques that use ILP to enhance processor performance.

Calling f in the jalr instruction can potentially change all caller-save registers (and it will certainly change $ra). But the subroutine as written depends upon $t0, $t1, $t2, and $ra all retaining their original value, even though they are caller-save registers.

A partial solution is to use callee-save registers $s0, $s1, and $s2 wherever the original code uses $t0, $t1, and $t2. But using these requires that the subroutine restore these registers' original values (as well as $ra) before returning. So another required step would be to add code at the beginning to push the old values onto the stack, and to add code before “jr $ra” to restore the pushed values. The added code at the beginning would be:

And at the end would be:         move $v0, $s2       ; original next-to-last instruction, using $s2 not $t2
        lw $ra, 12($sp)
        lw $s0, 8($sp)
        lw $s1, 4($sp)
        lw $s2, 0($sp)
        addi $sp, $sp, 16
        jr $ra
        nop

Since this instruction only has register arguments, it should be an R-type instruction. The first six bits should therefore be 0's. Looking at the available R-type opcodes, the last six bits might be 0x28 (which places it next to the other bit-twiddling instructions like nor). The R-type instructions all place the destination register ($t0 in the example) in bits 11–15, while the R-type instructions that use just one register place that register into bits 21–25. Bits 16–20 and 6–10 should be 0's.

For pop $t0, $s1, then, the encoding would be 000000 10001 00000 01000 00000 101000.

A 16-bit encoding leads to encoding programs in less memory. A 32-bit encoding tends to lead to fewer instructions per program, and hence a greater opportunity for increased performance; but for low-cost systems, performance is not as much a priority as cost and power. (Less memory in the system means a lower power requirement.)

One reason is that a more finely separated pipeline requires running the clock faster to get any advantage, but running the clock beyond 4 GHz is basically impossible due to the amount of heat generated by the fast-switching transistors.

Another is that increasing the pipeline length does not increase the clock speed proportionately, due to the delay introduced by each pipeline register. In itself, this is not a problem, until one considers data and control hazards that lead to pipeline delays. For instance, suppose that 10% of instructions turn out to be mispredicted branches, and branch predictions aren't determined until halfway through the pipeline. If an original instruction takes T time and a pipeline register introduces a delay of p, then a 10-stage pipeline would have a clock running at T/10 + p; but 10% of instructions would complete after 5 clock cycles, so the average clocks per instruction would be 0.9 ⋅ 1 + 0.1 ⋅ 5 = 1.4, for an average time per instruction of 1.4 (T/10 + p) = 0.14 T + 1.4 p. For a 20-stage pipeline, a clock cycle takes T/20 + p time, while the average clocks per instruction is 0.9 ⋅ 1 + 0.1 ⋅ 10 = 1.9, for an average time of 1.9 (T/20 + p) = 0.95 T + 1.9 p. If p is at least 9% of T, then the 10-stage pipeline will end up completing instructions more quickly.

A final reason — though not a major concern — is that the forwarding logic becomes increasingly unwieldy for longer pipelines, as logic must exist basically to forward data from every stage to every earlier stage. Eventually this logic becomes too unwieldy to be a practical use of transistors.

a. 0.8 * 1 + 0.05 * 3 + 0.15 * 4 = 1.55.

b. 0.8 * 1 + 0.05 * 3 + 0.10 * 4 + 0.05 * 1 = 1.4.

c. 0.8 * 1 + 0.05 * 3 + 0.10 * 3 + 0.05 * 4 = 1.45.

a. 2, 3, 5, 6. The predictions would be N, N, N, N, N, Y. The below table shows how the cache would change after each prediction.

A	WN/0 SN/1 WN/2 SN/4
B	WN/0 SY/3 WY/6

b. 2, 3, 6. The predictions would be N, N, N, N, Y, Y. The below table shows how the cache would change after each prediction; row “NY” represents the situation where the previous branch result was “yes” but the one before that was “no”.

NNN	WN/0
NNY	WN/0
NYN	WN/0
NYY	WN/0 SN/4
YNN	WN/0
YNY	WN/0 SY/3 WY/6
YYN	WN/0 SY/2 SY/5
YYY	WN/0 SN/1

Suppose we had the following instruction sequence.

lw   $t1, 0($a0)
ori  $t2, $t1, 1
addi $a0, $a0, 4

In a pipelined processor doing in-order execution, the lw instruction would reach the MEM stage at the same time that the ori instruction reaches the EX stage. The ori instruction would have to stall at this point, because the lw instruction will not have determined the value for $t1 (which the EX stage needs to execute ori instruction) until the MEM stage completes. This stall adds one clock cycle to the time needed to complete this sequence.

This wasted clock cycle could be avoided, however, if the processor executes the addi instruction first. Then the addi instruction (which doesn't depend on the result of the lw instruction) could complete the EX stage at the time that the lw instruction completes the MEM stage. The ori instruction would complete the EX stage at the same time as it otherwise would have done.

In a simultaneous multithreaded processor, the processor is aware of different threads of execution (instruction queues manipulating different sets of registers), and instructions from different threads can be dispatched into execution units in the same clock cycle.

“Private” memory is available to just one computation unit (“stream processor”). “Local” memory that is available to one group of computation units (“multiprocessor”, driving multiple stream processors with the same instruction stream). And “global” memory is available across the GPU (and CPU).

The snoopy approach involves connecting each core to a common bus, so that all communication between a core and memory is visible to all cores. Individual cores can update their private caches based on the traffic they see on the bus.

This system tends to break down beyond eight cores because each core needs a certain bandwidth to retrieve memory, but a bus is limited to handling only one message per clock cycle. The amount of traffic that the bus can handle ends up becoming a bottleneck beyond eight cores.

Cache coherency considers each memory address in isolation, looking for a guarantee that the sequence of accesses to that individual memory address is reasonable; it also allows for some fudging where individual processors' accesses are “near-simultaneous.” Cache consistency looks for a more precise ordering of instructions between different threads, and it looks for consistency in the order of access across all memory addresses.

4: We could execute all of B before executing any of A, so B would get the initial values 1 and 3 for a and b.

7: We could execute B's first instruction (getting 1), then A's first instruction (setting b to 6), then B's second instruction (getting 6).

8: We could execute all of A before executing any of B, so B would get the values for a and b as set by A: 2 + 6.

In the Map phase, we would decode the file and emit (studentName, gradeValue) for each student/grade pair found in the file. (We'd translate the letter grade into a number between 0 and 4 at this point.)

In the Reduce phase, we'd take the list of gradeValues received and compute both the sum of the list and the length of the list, reporting the quotient as our result for that student.