Assume memory is byte addressable and words are 64 bits, unless specified otherwise. In this exercise we look at memory locality properties of matrix computation. The following code is written in C, where elements within the same row are stored contiguously. Assume each word is a 64-bit integer.

Check the explanation

Explanation:

1

These lines could store 2 integers (16 * 8 = 128/64 = 2)

Cache size=16*8=128

No: of 64 bit integers stored=128/64=2

2

Temporal locality states that if a data value is accessed, then there are chances of reusing the same data value within a small duration. So these data value may remain in cache for the entire time this code is executing.

For the given C code, the access sequence is as shown below.

A[0][0] = B[0][0] + A[0][0]

A[1][0] = B[0][0] + A[0][1]

A[2][0] = B[0][0] + A[0][2]

...

A[7][0] = B[0][0] + A[0][7]

A[0][1] = B[1][0] + A[1][0]

...

A[7][1] = B[1][0] + A[1][7]

...

A[0][7999] = B[7999][0] + A[7999][0]

...

A[7][7999] = B[7999][0] + A[7999][7]

Here the variables i and j are constantly accessed. So these variables are likely to stay in cache and hence exhibit temporal locality.

Also B[j][0] exhibit temporal locality since it is accessed over and over in a row.

3

Spatial locality states that if a data is referred then there are chances of referring data from nearby locations also. So even if one piece of data is needed, an entire block containing the needed data will be loaded to memory.

Thus in the given C code, A[j][i] and B[j][0] exhibit spatial locality because as j is incremented, nearby values of array are accessed.

4

References to A[j][i] exhibit spatial locality

5

References to A[i][j] exhibit spatial locality

6

C Matrix Storage

These lines could store 2 integers (16 * 8 = 128/64 = 2)

Cache size=16*8=128

No: of 64 bit integers stored=128/64=2

That means 2 elements fit in 1 cache line.

Then calculate the number of elements in a 8000 * 8 2D Matrix = 64000 elements, each 64 bits. 64000 / (2*16) = 2000 cache lines (16 byte) are needed