CSE 141 Ungraded Homework #5 Answer Sheet

Note that the low-order three bits of an address specifies the byte address, and the next bit is the index. I'll write addresses as a 4-bit tag, a 1 bit index, and a three bit offest. We have:

Addr     tag  ind o'set  Action
lw 0   = 0000  0  000    Bytes 0-7 loaded into cache index 0.
sw 44  = 0010  1  100    Bytes 40-47 brought into cache index 1; 
                           bytes 44-47 modified; line marked "dirty". 
lw 52  = 0011  0  100    Bytes 48-55 loaded into cache index 0,
                           previous contents discarded.
lw 88  = 0101  1  000    Bytes 88-95 loaded into cache line 1;
                           previous (dirty) contents written back;
                           line marked "clean".

At this point, cache holds bytes 48-55 and 88-95, so references to 48, 52, 88, and 92 would be cache hits.

Neither cache line is dirty.

Addr     tag  ind o'set  Action
lw 0   = 0000  0  000    Bytes 0-7 loaded into cache index 0. Clean miss.
sw 52  = 0011  0  100    Bytes 48-55 loaded into cache index 0.
                           Clean miss (since discarded line is clean).
                           Line is marked "dirty".
lw 68  = 0010  0  100    Bytes 64-71 brought into cache index 0; 
                           Dirty miss (since line was dirty);
                           The new line is also marked clean.
lw 44  = 0010  1  100    Bytes 40-47 loaded into cache line 1;
                           Clean miss. Line marked "clean".

We first need to look the address up in the TLB. To do so, we partition the address (from left to right) into a 15 bit tag, a 5 bit index, and a 12 bit offset. Note that we make the offset 12 bits since the page size is 4096 = 2^12 Bytes, and we make the index 5 bits since there are 64/2 = 32 = 2^5 sets in the TLB (each set has two entries). The remaining high-order bits are the tag. Thus, we use the index field, bits 16-12 (numbering from 31 for the left-most bit and 0 for the right-most one), to index into the TLB. There are two entries at this index (since the TLB is 2-way set associative) - we check to see if either entry there has a tag field that matches the 15 bit tag of the virtual address (bits 31-17).
We are told that this is a TLB hit, so one of the two entries in this set matches the tag (and the corresponding valid bit is "1"). So we take the 16 bit physical page number in the TLB and prepend it to the 12 bit offset of the virtual address to form the 28 bit physical address.
Now we need to use this physical address to look up the data in the data cache. To do so, we partition the 28 bit physical address into (from the left) a 14 bit tag, a 7 bit index, and a 7 bit offset. (The offset is 7 bits because the cacheline is 128=2^7 Bytes long; the index is 7 bits because there are 512/4 = 128 = 2^7 sets of 4 cachelines each). We use the index (bits 7-13 of the physical address) to choose a set, and compare the tag (bits 27-14 of the physical address) to the four tags stored in the chosen set.
Again, we are told it is a cache hit, so the corresponding line in cache has the desired data. We use the index field (bits 0-6) of the physical address to tell us which byte in the cacheline is the first byte of the data that we are looking for.
In the case of cache and TLB misses, we start out as before, but don't find the desired virtual address in the TLB. Thus, we must use the virtual page number (bits 31-12 of the virtual address) to index into the page table. There we find the physical page number. Let's assume the "valid" bit in the page table is set to "1", meaning the page actually is in main memory. (If not, we need to invoke the operating system to go off to disk and find it). So we form the physical address from the 16 bit physical page number (in the page table) concatenated with the 12 bit offset. We also bring this information into the TLB using the TLB index described earlier.
Again, we break the physical page number into tag-index-offset as described earlier, look for the data in cache, and don't find it. Thus, we go to main memory and bring into cache the line that holds the desired data, kicking out the least recently used of the four cachelines that are in the set at the referenced index. If that line happens to be dirty, we must also write it back to memory.

NOTE FROM GREG: Last week in section we discussed how caches deal with stores. Specifically, we looked at caches that are write-back vs. write-through, and write-allocate vs. write around. I believe I may have oversimplified things and would like to provide some clarification. It is true that write-back vs. write-through deals with what happens when you write to the cache and find the data present in the cache. However, some students may have been a little confused in reading the solutions to HW #5 when we actually set the dirty bit on a cache miss. The natural question is, "Hey! I thought we only worry about write-back vs. write-through when we have a cache HIT." The potential tricky point here is what happens if your cache is write-back and write-allocate? In this situation, suppose you have a cache miss. The write-allocate policy of the cache will load the data in question into the cache, and the write-back policy will cause only the cache copy to be modified, also turning on the corresponding dirty bit. On the other hand, if your cache is write-through and write allocate, the same thing will happen, but then both the cache copy and the memory copy will be modified.

Secondly, during section we only spoke of a write-allocate cache in terms of a write-allocate and write-through cache. From the previous paragraph, just make note that it is possible for a write-allocate cache to also be write-back, in which case it is not necessarily true that both the cache copy and memory copy are updated on a write. Sorry for the confusion!