Question

Assume a computer with a cache that holds 64 bytes and has a block size of 32 bytes. Direct address mapping is used and from the beginning the cache is empty. The following program sequence is executed:

for (col = 0; col < 2; col++) {

for (row = 0; row < 4; row++)

A[row][col] = B[row] * C[col]; }

Assume that for the variables row and col registers are used.
The matrix A consists of 4 rows and 4 columns with integers (one word long). A is located in the RAM with start address 0 and is stored in rows (A [0] [0], A [0] [1], ... ).
Array B consists of 4 integers (one word long). B is located in RAM with start address 64.
The arrayC consists of 4 integers (one word long). C is located in RAM with start address 80.
What will be the hit probability for the program sequence? What will be the hit probability if 2-way set associative address mapping (with LRU when changing blocks) is used instead of direct address mapping? Also write explanations of how the calculations are done and interpret the results. (Note that the outer loop runs twice and the inner one four times. There will be a total of 24 memory references.)

Answer 1

Number of lines in cache

= Cache size / Line size

= 32 words / 8 words

= 4 lines

Since each element of the array occupies 4 words, so-

Number of elements that can be placed in one line = 2

Now, let us analyze the statement-

A[i] = A[i] + 10;

For each i,

• Firstly, the value of A[i] is read.
• Secondly, 10 is added to the A[i].
• Thirdly, the updated value of A[i] is written back.

Thus,

• For each i, A[i] is accessed two times.
• Two memory accesses are required-one for read operation and other for write operation.

Assume the cache is all empty initially.

In the first loop iteration,

• First, value of A[0] has to be read.
• Since cache is empty, so A[0] is brought in the cache.
• Along with A[0], element A[1] also enters the cache since each block can hold 2 elements of the array.

• Thus, For A[0], a miss occurred for the read operation.
• Now, 10 is added to the value of A[0].
• Now, the updated value has to be written back to A[0].
• Again cache memory is accessed to get A[0] for writing its updated value.
• This time, for A[0], a hit occurs for the write operation.

In the second loop iteration,

• First, value of A[1] has to be read.
• A[1] is already present in the cache.
• Thus, For A[1]. a hit occurs for the read operation.
• Now, 10 is added to the value of A[1].
• Now, the updated value has to be written back to A[1].
• Again cache memory is accessed to get A[1] for writing its updated value.
• Again, for A[1], a hit occurs for the write operation.

In the similar manner, for every next two consecutive elements-

• There will be a miss for the read operation for the first element.
• There will be a hit for the write operation for the first element.
• There will be a hit for both read and write operations for the second element.

Likewise, for 100 elements, we will have 50 such pairs in cache and in every pair, there will be one miss and three hits.

Thus,

• Total number of hits = 50 x 3 = 150
• Total number of misses = 50 x 1 = 50
• Total number of references = 200 (100 for read and 100 for write)

Thus,

• Hit ratio = 150 / 200 = 3 / 4 = 0.75
• Miss ratio = 50 / 200 = 1 / 4 = 0.25