Question F3b-hard:
loop:
1	addi $t0, $t0, 4
4 lw $s0, 60($t0)
2 lw $v0, 0($t0)
5 bne $s0, $0, loop
3 sw $v0, 20($t0)

1: I D E M W
4:   I D E M W         # forward $t0 from execute stage of (1)
2:     I D E M W       # forward $t0 from execute stage of (1)
5:       I D E M W     # ****** see expanation below
3:         I D E M W   # forward $v0 from memory stage of (2)

The branch instruction requires the value of $s0 during the decode stage for comparison. $s0 becomes available during the memory stage of instruction (4). Since comparators are quite fast relative to the clock cycle, we can fetch memory and compare it's value in the same clock cycle (just like we fetched registers and compared them). Although we never talked about this case explicitly in class, this branch hazard is avoidable using forwarding and a little extra hardware -- namely, a mux or two.


Question F4a:
The first-level data cache for a certain processor can cache 64KiB of physical memory. Assume that the word size is 32 bits, the block size is 64 bytes, the size of physical memory is 2 GiB, and the cache is 4-way set associative.

How many bits are needed for the Tag, Index, and Offset bits? 

Offset: 
64 byte blocks => 2^6 byte blocks => 6 bit offset

Index: 
64KiB of data in cache / 64 bytes per block = 1Ki blocks total
Each set contains 4 blocks,
1 Ki blocks / 4 blocks per set = 256 sets => 2^8 sets => 8 bit index

Tag:
2GiB physical memory => 2^31 bytes physical memory => 31 bit physical address
31 bits total - 6 bit offset - 8 bit index = 17 bit tag


Question F4b:
For each of the following changes to the initial conditions above, indicate how these bits (i.e., the width of these fields) shift around. E.g. if a bit field stays the same, write "0", if a bit field increases by 5, write "+5", if a bit field decreases by 1, write "-1".

Double the cache size (from 64KiB to 128KiB)
	Tag:-1, Index:+1, Offset:0

Double the word size (from 32 bits to 64 bits)
	Tag: 0, Index: 0, Offset:0
	Caches always use physical addresses. So changing the size of the virtual memory space will not change the bit fields at all.

Change the associativity to fully associative:
	Tag:+8, Index:-8, Offset:0