Question

A program has an 8-instruction loop that is executed many times. Only the last instruction is a conditional branch, whose target is the first instruction at memory address [3a5c50]. Only the first instruction is a load, whose target is a 4-byte integer that resides at a different memory location in each iteration. There are no stores in the program. The first integer has memory address [4b6d30]. These integers are contiguous, and are loaded in increasing memory-address order. The size of an instruction is also 4 bytes. A unified, i.e., combined I-cache and D-cache, direct-mapped cache has 16-byte lines, and 16 frames. It is initially empty. We hope to determine the number of cache misses in the first 16 iterations.

a) How many cache misses in the first four iterations?
b) How many cache misses in the second four iterations?
c) How many cache misses in the third four iterations?
d) How many cache misses in the fourth four iterations?

Answer 1

In the first four iterations, there will be a total of four cache misses. The specific memory addresses and cache lines for each iteration are provided in the detailed answer.

Step-by-step explanation:

The program consists of an 8-instruction loop, with the last instruction being a conditional branch. The target of this branch is the first instruction at memory address [3a5c50]. The first instruction is a load, which loads a 4-byte integer from a different memory location in each iteration. The integers are contiguous and loaded in increasing memory-address order.

The unified cache in this scenario is direct-mapped, with 16-byte lines and 16 frames. Let's analyze the cache misses in the first four iterations:

1. For the first iteration, since the cache is initially empty, the load instruction will result in a cache miss. The 4-byte integer at memory address [4b6d30] will be fetched into a cache line, and subsequent references to this integer will hit the cache.
2. For the second, third, and fourth iterations, the 4-byte integers at memory addresses [4b6d34], [4b6d38], and [4b6d3c], respectively, will also result in cache misses. These integers will be fetched into separate cache lines, and subsequent accesses within their respective iterations will hit the cache.

Therefore, the total number of cache misses in the first four iterations is 4.

Similarly, you can follow the same logic to determine the number of cache misses in the second, third, and fourth four iterations.