HW9 Solutions


7.35 If direct mapped and stride = 256, then we can assume without 
loss of generality that array[0] . . .  array[31] is in block 0. 
Then, block 1 has array[32] . . . [63] and block 2 has array[64] 
. . . [127] and so on until block 7 has [224] . . . [255]. 
(There are 8 blocks ??32 bytes = 256 bytes in the cache.) Then 
wrapping around, we find also that block 0 has array[256] . . . [287], 
and so on.
Thus if we look at array[0] and array[256], we are looking at the 
same cache block. One access will cause the other to miss, so there 
will be a 100% miss rate. If the stride were 255, then array [0] 
would map to block 0 while array [255] and array [510] would both 
map to block 7. Accesses to array [0] would be hits, and accesses 
to array [255] and array [510] would conflict. Thus the miss rate 
would be 67%.
If the cache is two-way set associative, even if two accesses are 
in the same cache set, they can coexist, so the miss rate will be 0.


7.39 The total size is equal to the number of entries times the size
of each entry. Each page is 16 KB, and thus, 14 bits of the virtual 
and physical address will be used as a page offset. The remaining 
40 – 14 = 26 bits of the virtual address constitute the virtual page 
number, and there are thus 2^26 entries in the page table, one for 
each virtual page number. Each entry requires 36 – 14 = 22 bits to 
store the physical page number and an additional 4 bits for the valid, 
protection, dirty, and use bits. We round the 26 bits up to a full 
word per entry, so this gives us a total size of 2^26 * 32 bits or 256 MB.


7.40
	

                Virtual Address
-----------------------------------------
| Virtual Page Number |    Offset       |
-----------------------------------------
         26-bits           14-bits


TLB
  V      Tag     Physical Page Number	          V    Tag     Physical Page Number
-----------------------------------------	-----------------------------------------
| 1 | 19-bits | 22-bits                 |	| 1 | 19-bits | 22-bits                 |
-----------------------------------------	-----------------------------------------
|   |         |                         |	|   |         |                         |
-----------------------------------------	-----------------------------------------
.......
128 Sets 


       Page Table
 V P D U     Physical Page Number
------------------------------------------
|1|1|1|1|      22-bits                   |
------------------------------------------
| | | | |                                |
------------------------------------------
| | | | |                                |
------------------------------------------
.......



        Physical Address
-------------------------------------------
| Physical Page Number |   Offset         |
-------------------------------------------
         22-bit             14-bits




 
7.41 The TLB will have a high miss rate because it can only access 
64 KB (16 * 4 KB) directly. Performance could be improved by increasing 
the page size if the architecture allows it.

7.45 Less memory—fewer compulsory misses. (Note that while you might 
assume that capacity misses would also decrease, both capacity and 
conflict misses could increase or decrease based on the locality changes 
in the rewritten program. There is not enough information to definitively 
state the effect on capacity and conflict misses.)

7.52 This optimization takes advantage of spatial locality. This way we 
update all of the entries in a block before moving to another block.