Question: cpu language assembly language consider a system that uses a...
CPU language: Assembly Language
Consider a system that uses a 64-bit word. This CPU has a 1 Mbyte (1024*1024 bytes) cache memory. The size of each CPU cache slot is 512 bytes. The system has a 4 GB main memory. Cache line 0 holds main RAM memory (byte) addresses 0 to 511, cache line 1 holds main memory (byte) addresses 512 to 1024, and so on. Assume that the cache initially contains the information in the first 550 cache lines of main RAM memory. Also assume that cache line 0 was loaded first, and that the other 549 cache lines were loaded in numerical sequence. After being loaded each of the cache lines was accessed several times, but the last access to cache line N occurred before the first access to cache line N+1. Further assume that the remainder of the cache (cache slots 550 …) are empty. In other words they have not been used to hold cache lines since the OS was started.
Consider a program that makes a series of memory requests for data and/or instructions. Each request is for information stored in a particular cache line of main RAM memory. The part of the code we are considering consists of two consecutive loops. The first loop will be executed 8 times. The second loop is executed 43 times. To provide the needed instructions and data to the program, as it runs, cache lines are accessed in the following order:
i. The code and data in the first loop is stored in cache lines numbered 400 to 950. Each time the first loop is executed there will be 5 accesses for each cache line, 5 accesses to cache line 400 then 5 accesses to cache line 401, and so on, …, finishing with 5 accesses to cache line 950.
ii. The code and data in the second loop is stored in cache lines 4666 to 5028, and lines 16968 – 17314. Each time the second loop is executed there will be 3 accesses to cache line 4666, 3 accesses to cache line 4667, …, finishing the first group of cache lines with 3 accesses to cache line 5028, then there will be 3 access to cache line 16968, then 3 accesses to 16969, and so on until the 3 accesses to line 17314 are complete.
You will be asked to consider two different mapping algorithms. For each of these mapping algorithms assume the replacement algorithm is to place the new cache line in the MAPPED cache slot that was accessed least recently. The rules for the replacement algorithm are:
i. If there are MAPPED slots that are empty, choose the empty MAPPED slot with the smallest number
ii. otherwise choose the MAPPED cache slot that was last accessed the longest time ago (last accessed at the earliest time)
a) [16 points] The system uses direct mapping of the 4GB memory of the system to the cache. Direct mapping means that if there are N cache slots in the cache memory and M cache lines in memory, cache line K in memory will map to cache slot K%N in the cache. When cache line K is loaded in the cache it must always be loaded in cache slot K%N. What are the number of cache hits, the number of cache misses and the hit ratio for the series of accesses above using direct mapping? Give a step by step explanation in your answer which includes a summary of which cache lines are placed in which cache slots in which sequence. Most of the points will be given for your explanation. HINT: The cache initially contains the information in the first 550 cache lines of main memory in its first 550 cache slots (Cache line 0 in cache slot 0, cache line 1 in cache slot 1, …, finishing with cache line 549 in cache slot 549). HINT: First consider how many hits and misses for the first time through the first loop, then consider how many hits and misses for the remaining times through the first loop, then consider the first time through the second loop, then the subsequent times through the second loop
b) [16 points] assume that all cache lines in the cache when the code begins to execute (lines 0 to 549) were loaded into the cache in numerical order using 4 way associative mapping. When we use M way set associative mapping (for this example M=4) we divide the available cache slots into sets of M slots. If there are N cache slots in the cache memory we can divide them into P groups of M slots (P*M=N). Cache line K in memory will map to any cache slot in group Q (0<=Q