Question

In this exercise we look at memory locality properties of matrix computation. The following code is written in C, where elements within the same rwo are stored contiguously. Assume each word is a 32-bit integer.

for(I=0;I<8;I++)

for(J=0;J<8000;J++)

A[I][J]=B[I][0]+A[J][I];

5.1.1 [5] How many 32-bit integers can be stored in a 16-byte cache block?

5.1.2 [5] References to which variables exhibit temporal locality?

5.1.3 [5] References to which variables exhibit spatial locality?

Locality is affected by both the reference order and data layout. The same computation can also be written below in Matlab, which differs from C by storing matrix elements within the same column contiguously in memory.

for I=1:8

for J=1:8000

A(I,J)=B(I,0)+A(J,I);

end

end

5.1.4. [10] How many 16-byte cache blocks are needed to store all 32-bit matrix elements being referenced?

5.1.5 [5] References to which variables exhibit temporal locality?

5.1.6 [5] References to which variables exhibit spatial locality?

Short answer

5.1.1 - Four 32-bit integers can be stored in a 16-byte cache block.

5.1.2 - The variables I, J exhibit temporal locality.

5.1.3 - The variables A[I][J] exhibit spatial locality.

5.1.4 - 500 16-byte lines are required.

5.1.5 - I,J,B(I,0) are the variables which exhibit temporal locality.

5.1.6 - A[I][J],A[J][I],B(I,0) are the variables which exhibit spatial locality.

Step-by-step solution

(5.1.1)Step 1: Calculating the number of integers that can be stored in a 16-byte cache block.

To calculate the number of 32-bit integers in a 16 byte cache block, solve the following things:

Number of bits in a byte=8

Number of bits in 16 bytes will be:

$$\begin{gathered} =16\times 8 \\ =128 \end{gathered}$$

Number of 32-bit integers will be:

$$\begin{gathered} =\frac{128}{32} \\ =4 \end{gathered}$$

Therefore, four 32-bit integers can be stored in a 16-byte cache block.

(5.1.2)Step 2: Temporal Locality.

During each iteration of the code, the variables I and J are constantly accessed, and because of processors taking advantage of temporal locality, these will likely stay in the cache the entire time the code is executing as the processor will assume that if a piece of data is accessed, it will likely be accessed again.

(5.1.3)Step 3: Spatial Locality.

The spatial locality is the tendency for data with addresses near the current piece of data we are working with to be needed soon. This is why when one piece of data is needed, the processor will also load the entire block with data that is next to the data which is just accessed. In this example, A[I][J] again exhibit spatial locality as they would be located near each other in the array.

(5.1.4)Step 4: Calculating the number of 16-byte cache lines needed to store all 32-bit matrix elements being referenced.

To calculate the number of 16-byte cache lines needed to store all 32 bit matrix elements being referenced, solve the following things:

Number of bits in a byte = 8.

Number of elements in the bit matrix =$8000\times 8=64000$

Number of bytes =$\frac{64000}{8}=8000$

Number of 16 byte cache lines needed =$\frac{8000}{16}=500$

Therefore, 500 16-byte cache lines are needed to store all 32 bit matrix elements being referenced.

(5.1.5) Step 5: Temporal locality

During each iteration of the code, the variables I,J and B(I,0) are constantly accessed, and because of processors taking advantage of temporal locality, these will likely stay in the cache the entire time the code is executing as the processor will assume that if a piece of data is accessed, it will likely be accessed again.

(5.1.6)Step 6:Spatial Locality

The spatial locality is the tendency for data with addresses near the current piece of data we are working with to be needed soon. This is why when one piece of data is needed, the processor will also load the entire block with data that is next to the data which is just accessed. In this example, A[I][J], A[J][I] and B(I,0) again exhibit spatial locality as they would be located near each other in the array.