1. Definitions

a. pseudoinstruction A common variation of assembly language instructions often treated as if it were an instruction in its own right.

b. data forwarding A technique for resolving data hazards by getting the result of a previous instruction from internal resources rather than waiting for the instruction to complete.

c. spatial locality The locality principle stating that if a data location is referenced, data locations with nearby addresses will tend to be referenced soon.

d. write-back cache A scheme that handles writes by updating values only to the block in the cache, then writing the modified block to the lower level of the hierarchy when the block is replaced.

e. pipelining stall Also called bubble. A stall initiated in order to resolve a hazard.

2.1: a CISC-style architectures do not facilitate pipeline design. Because CISC architectures support such complex instructions, it's difficult to break them down into uniform-sized stages.

2.2: d There's no such thing as cylinder alignment time.

2.3: b or c Immediate addressing and PC-relative addressing can be safely ignored by the linker.

2.4: c There's no such thing as a conditional miss.

a. This is a control hazard, because the results of the previous add are needed by the beq instruction, and so the decision about whether to branch might be delayed. The hazard can be resolved with speculative execution.

b. This is a data hazard, because the results of the first add are needed by the second one. The hazard can be resolved with data forwarding.

c. There's no hazard here; the second add does not rely on the results of the first.

a. To find the number of blocks in the cache, take the size of the cache (4KB = 2^12 bytes) divided by the size of each block (4 words * 4 bytes/word = 16 bytes = 2^4 bytes), to get 2^8 = 256 blocks.

b. To find the number of bits in the tag, follow the four-step procedure outlined in email. Start with the 32 bits in the address. Throw away 2 because the memory is byte addressed and 2 because the block size is 4 = 2^2. Throw away 8 more for the size of the cache index, and you're left with 32-2-2-8 = 20 bits.

c. The address 0x00543210 was just referenced. To decide whether the next reference X is present in the cache, we have to look at two things. First, do the indices match? Next, do the tags match? We know that the lower 4 bits (lowest hex digit) don't matter from part b. The next 8 bits (next 2 hex digits) form the index, and the top 20 bits (top 5 hex digits) form the tag.

c.1 Here the index is 0x22 and the tag is 0x00543. The index doesn't match that of the previous reference, so we have no way to tell whether this data item is present or not.

c.2 Here the index is 0x21 and the tag is 0x00543. The index matches and the tag matches, so we know that this data item is present in the cache.

c.3 Here the index is 0x21 and the tag is 0x00555. The index matches but the tag doesn't match, so we know that this data item is absent from the cache.

a. t = 25*10^-9, tm = 10^-7, tc = 10^-8. Plugging into the formula and multiplying through by 10^9, we get: 25 = 10h + 100(1-h), or 75 = 90h. The necessary hit rate is 75/90, or about 83%.

b. If the cache hit rates aren't high enough, you might increase the size of the cache (combatting capacity misses) or change the associativity of the cache (combatting conflict misses). There's really not much you can do about compulsory misses, though associativity will help a little with that too.

a. FUN returns 0 if $a0 is 0.

b. FUN returns 1 if $a0 is 1.

c. FUN computes the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. Each Fibonacci number is the sum of the previous two. Expressed as a formula, FUN(a0) = FUN(a0-1) + FUN(a0-2).