SOF108 COMPUTER ARCHITECTURE Tutorial 8 – Memory Hierarchy -II
1. Assume there are three small caches, each consisting of four one-word blocks. One cache is fully associative, a second is two-way set-associative, and the third is direct-mapped. Find the number of misses for each cache organization given the following sequence of block addresses: 0, 8, 0, 6, and 8. Use LRU algorithm, if a replacement policy is required.
*Memory [i] in the below tables are referring to Memory block i.
Copyright By PowCoder代写 加微信 powcoder
For direct mapping, we used the following formula to determine the mapping of each block, i.e., determining which block goes to which line:
(Block number) mod (Number of lines)
For set associative mapping, we used the following formula to determine the mapping of each block, i.e., determining which block goes to which set:
(Block number) mod (Number of sets)
2. Assume a direct mapped cache, with four lines and the tag values for each lines are as below:
11 Invalid
The tag, line, and word field contains: 5, 2, and 5 bits, respectively. Now if you want to access from memory address 3210, is this a hit or a miss? Justify your answer.
Accessing memory address 3210 = 000000100000
Tag Line Word
00000 01 00000
The current tag in line 01 is 00001, which does not match with the tag value from the
given memory address 3210. Therefore, this is a miss.
After this memory access, the tag value in line 01 needs to be changed (since this is a miss) to 00000.
NOTE: The address given in this question is a memory address, not a block address. So, you should not calculate block number mod number of lines to do the mapping.
The block number for the memory address 32 (as given in this question) is represented by the bits in the tag and line field, so in this case the block number would be 0000001. Now, given this block number you can use the mapping function and the mapping function will place this block in line 01 as well!
3. Consider the following code: for (i=0; i < 20; i++) for (j = 0; j < 10; j++) a[i] = a[i]*(j+1); a. Give one example of the spatial locality in the code. b. Give one example of the temporal locality in the code When a[i] is used, in the next iteration of the outer loop a[i+1] will be used. That is after the first instruction is executed, immediately the following one is executed. Inside the inner loop, the same a[i] is accessed ten times in a short interval of time. A computer has a cache, main memory, and a disk used for virtual memory. If a referenced word is in the cache, 20 ns are required to access it. If it is in main memory but not in the cache, 60 ns are needed to load it into the cache, and then the reference is started again from cache (another 20 ns). If the word is not in main memory, 12 ms are required to fetch the word from hard disk, followed by 60 ns to copy it to the cache, and then the reference is started again from the cache. The cache hit ratio is 0.9 and the main memory hit ratio is 0.6. What is the average memory access time (AMAT) in nanoseconds required to access a referenced word on this system? 1nanosecond=1ns=1x10-9 second 1microsecond=1μs=1x10-6 second 1millisecond=1ms=1x10-3 second AMAT = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns = 0.480026 ms Method 2: Hit time Hit at cache 20ns Miss at cache, Hit at Main memory Miss penalty Miss rate 60ns 0.1 Miss at main memory, Hit at hard disk AMAT = 20ns + 0.1 x 60ns + 0.1 x 0.4 x 12000000 ns = 480026 ns 5. If a direct mapped cache has a hit rate of 95%, a hit time of 4 ns, and a miss penalty of 100 ns, what is the AMAT? If replacing the cache with a 2-way set associative increases the hit rate to 97%, but increases the hit time to 5 ns, what is the new AMAT? Direct mapping: AMAT = Hit time + Miss rate x Miss penalty = 4 + 0.05 × 100 = 9 ns 2-way set associative mapping: AMAT = Hit time + Miss rate x Miss penalty = 5 + 0.03 × 100 = 8 ns 6. Assuming the miss rates given in the following diagram: Miss penalty is 50 cycles Hit time is 1 cycle 75% of the total memory accesses for instructions and 25% of the total memory accesses for data On the unified cache, a load or store data hit takes an extra cycle (2 cycles), since there is only one port for instructions and data Which has the lower average memory access time? Split cache: 16 KB instructions + 16 KB data Unified cache: 32 KB (instructions + data) Additional theoretical questions to prepare: What are the differences among direct mapping, associative mapping, and set associative mapping? Direct mapping maps each block of main memory into only one possible cache line. Associative mapping permits each main memory block to be loaded into any line of the cache. In set-associative mapping, the cache is divided into a number of sets of cache lines; each main memory block can be mapped into any line in a particular set. For a direct-mapped cache, a main memory address is viewed as consisting of three fields. List and define these three fields. Word: identifies a unique word or byte within a block of main memory. The remaining two fields specify one of the blocks of main memory. These two fields a line field, which identifies one of the lines of the cache, and 3. For an associative cache, a main memory address is viewed as consisting of two fields. List and define these two fields. a tag field, which identifies one of the blocks that can fit into that line. Tag Line Word A tag field uniquely identifies a block of main memory. A word field identifies a unique word or byte within a block of main memory. For a set-associative cache, a main memory address is viewed as consisting of three fields. List and define these three fields. Word: One field identifies a unique word or byte within a block of main memory. The remaining two fields specify one of the blocks of main memory. These two fields are a set field, which identifies one of the sets of the cache, and a tag field, which identifies one of the blocks that can fit into that set. Tag Set Word What is the distinction between spatial locality and temporal locality? Spatial locality refers to the tendency of execution to involve a number of memory locations that are clustered (near to each other). Temporal locality refers to the tendency for a processor to access memory locations that have been used recently. In general, what are the strategies for exploiting spatial locality and temporal Spatial locality is generally exploited by using larger cache blocks. Temporal locality is exploited by keeping recently used instruction and data values in cache memory and by exploiting a cache hierarchy. What is the general relationship among access time, memory cost, and capacity? Faster access time (e.g. cache), greater cost per bit; Greater capacity (e.g. RAM), smaller cost per bit; Greater capacity (e.g. RAM), slower access time. End of Page 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com