CS 61C Fall 1994 Midterm 2 solutions 1. Where is physical 0x0f1653f8 in the cache? size words policy offset set tag (wds) (wds) 1024 8 direct 24 31 61797 mapped 0x18 0x1f 0xf165 11000 0011111 4096 16 4-way set 56 15 61797 associative 0x38 0xf 0xf165 111000 011111 4096 4 fully 8 not 15820095 associative 0x8 applicable 0xf1653f 1000 We also accepted answers with a word offset instead of a byte offset (that is, with the offset numbers above divided by four). The number of bits in the offset depends on the width of a cache slot. The slot sizes in bytes are 8*4=32=2^5, 16*4=64=2^6, and 4*4=16=2^4. Therefore, the offset sizes are 5, 6, and 4 bits. The offset is the rightmost part of the address, which is 0000 1111 0001 0110 0101 0011 1111 1000. The values listed above under the offset column are the rightmost five, six, and four bits of this address. The number of bits in the set number depends on the number of sets in the cache. We determine this in two steps. First, how many slots (or blocks) are in the cache? This is the total cache size divided by the width of one block. For these three caches there are 1024/8=127=2^7, 4096/16=256=2^8, and 4096/4=1024=2^10. The next step is to divide the total number of slots (computed above) by the number of slots in each set. For a direct mapped cache, each slot is its own set. (In other words, each set contains only one slot; there is only one place that a given address can appear in the cache.) So this cache has 2^7 sets, so the seven bits to the left of the offset are the set number. For a 4-way set associative cache, each set contains four slots, so this cache has 256/4=64=2^6 sets, so its set number takes up six bits. For a fully associative cache, the entire cache is a single set, and there is no set number. Some people thought that the set number is in the high-order (leftmost) bits of the word. If that were true, then consecutive addresses would compete for the same cache set. Locality of reference tells us that such a cache would have a very high miss rate even when most of the slots were unused! The idea is to distribute nearby addresses among all the sets. Finally, the tag is everything not used up for the offset or set number. Scoring: Two points per row. Half credit if one of the three numbers was right and the other two were consistent with each other, i.e., if one of the borders between fields was misplaced. Question 2: Disassemble into TAL 0x02282822 0000 0010 0010 1000 0010 1000 0010 0010 Opcode (first six bits) 0 is R-type: 000000 10001 01000 00101 00000 100010 opcode rs rt rd shamt function Function 0x22 is SUB, so this is sub $5, $17, $8 0xAFB00008 1010 1111 1011 0000 0000 0000 0000 1000 Opcode 101011 = 0x2b is SW, so this is I-type: 101011 11101 10000 0000000000001000 opcode rs rt offset sw $16, 8($sp) # or 8($29) 0x0541FFFFE 0000 0101 0100 0001 1111 1111 1111 1110 Opcode 000001 is branch (I-type): 000001 01010 00001 1111111111111110 opcode rs branch offset Branch type 1 is BGEZ, so this is bgez $10, *****see below***** We accepted a wide range of notations for the branch target. It's actually pointing at the instruction just before the BGEZ. The common answers were -2 and 0xfffe. In practice the target would have a label, so the program would look like foo: some-instruction bgez $10, foo Another plausible answer would be -8(pc), since the branch offset is in words, and so the actual address of the target is 8 less than what's in the PC (namely, the address of the instruction after the BGEZ). Scoring: One point each. 3. What good is the dirty bit? Two point answer: The bit is set whenever something is stored in any address within the page; the operating system examines the bit when that page must be reassigned. If the bit is not set, then the operating system need not write the contents of the page to disk before reading in the new contents. One point answer: The bit is set whenever something is stored in any address within the page. One point answer: The bit is used to keep track of whether anything has been modified and must be written back. [This is a one point answer because it's not clear whether you understand the difference between the cache and the virtual memory system.] Zero point answer: The bit is set when the page table or TLB entry is written; it's used to decide whether or not to write the page table or TLB entry back to memory. [It's not the page table or TLB entry we're concerned with, but rather the data in the page to which that entry refers!] 4. Hardware or software? a. Reading a page table entry from main memory: Could be either. Whether this operation is built into the hardware or left for the operating system software, a memory reference is still required. Therefore the gain from hardwiring this operation is slight. The MIPS processor leaves this task for the operating system, although other processors have specific hardware for the purpose. b. Reading a TLB entry: Definitely hardware. The whole point of having a TLB is to cache the page table, so that the virtual memory translation process will be really fast in most cases. If every TLB read required a processor exception handler to be called, every memory reference would be really slow! c. Setting the write enable bit for a page: Definitely software. The write enable bit (unlike the dirty bit, which also has to do with writing) indicates a policy decision, not a record of the history of memory use. There is no way the hardware could make this decision; the operating system must keep track of which pages should be writable and which should not. Scoring: One point each. 5. Memory geometry. a. The number of page table entries is equal to the number of virtual pages. The number of virtual pages is equal to the size of the entire virtual address space divided by the size of one page. A virtual address is 20 bits wide, so the size of the virtual address space is 2^20 bytes. The size of a page is 4K bytes, which is 2^12. Therefore, the number of virtual pages is (2^20)/(2^12) = 2^(20-12) = 2^8 = 256. So there are 256 entries in the page table. b. What's in 0x05584? First comes the virtual to physical address translation. We must divide the virtual address into a virtual page number and an offset. The page size is 2^12, so the offset is a 12-bit number (or 3 hex digits). So the address 0x05584 is in virtual page 5, at offset 0x584. We look for the virtual page number in the TLB, and find it in entry #2. The corresponding physical page number is 0xb, so the complete physical address is 0xb584. Now we look in the cache for the actual data. As in question 1, we must divide the physical address into tag, set number, and offset. The width of one cache slot is 4 words, or 16 bytes. 16 = 2^4 so the offset is the rightmost four bits of the address, i.e., one hex digit, namely 4. This is a *byte* offset, so we are looking for the second word (word #1) of a cache slot. The cache is direct mapped, so each slot is a set, so there are 16 sets. That means the set number is the next four bits to the left of the offset -- again, one hex digit, namely 8. We look in slot 8 of the cache. The tag is 0xb5, which matches the part of the physical address not already used for offset or set number. The valid bit is on, so this cache entry will indeed give us the data we need. We look in word #1 of slot 8, and we find 0x60. Scoring: One point for part a, one point for the right TLB row, one point for the right cache row, and one point for the right cache column. 6. Translate C to MAL. finalGrade: add $sp, $sp, -24 # allocate stack frame sw $31, 0($sp) # save registers sw $16, 4($sp) sw $17, 8($sp) sw $18, 12($sp) sw $19, 16($sp) sw $4, 20($sp) # save argument value jal getHwGrade # arg is already in $4 move $16, $2 # hwGrade = result lw $4, 20($sp) # get studentId back jal getMtGrade move $4, $2 # use result as arg jal adjustGrade move $17, $2 # mtGrade = result lw $4, 20($sp) # get studentId again jal getProjGrade move $18, $2 # projGrade = result add $8, $16, $17 add $19, $8, $18 # grade = sum move $2, $19 # return grade lw $31, 0($sp) # epilogue lw $16, 4($sp) lw $17, 8($sp) lw $18, 12($sp) lw $19, 16($sp) addi $sp, $sp, 24 jr $31 Scoring (typical errors): 6: correct 5: missed one load into $4 4: missed some saves 2: missed (almost) all saves 0: gibberish