A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a…

Part (a)

1. Determine the Cache Block Capacity

• Cache Block Size = 128 bytes

• Element Size = 8 bytes

• Number of array elements that fit into a single cache block = 128 bytes / 8 bytes = 16 elements

1. Analyze the Memory Layout and Access Pattern of Program P1

• In C, two-dimensional arrays are stored in row-major order, meaning elements are sequentially placed in memory row by row (e.g., A[0][0], A[0][1], A[0][2], ...).

• Program P1 accesses the array using the loop structure A[i][j], which moves sequentially across the rows.

1. Determine the Cache Miss Behavior for P1

• When the first element A[0][0] is accessed, it results in a cache miss.

• This miss brings an entire 128-byte block into the cache, which contains 16 sequential elements (A[0][0] through A[0][15]).

• The subsequent 15 accesses (A[0][1] through A[0][15]) result in cache hits.

• This pattern repeats continuously: 1 cache miss occurs for every 16 elements accessed.

1. Calculate Total Cache Misses (M1)

• Total number of elements in the array = 512 rows x 512 columns = 262,144 elements

• M1 = Total Elements / Elements per Cache Block

• M1 = (512 x 512) / 16

• M1 = 16384

Part (b)

1. Analyze the Access Pattern of Program P2

• Program P2 accesses the array using the loop structure A[j][i], which means it processes the array column by column (e.g., A[0][0], A[1][0], A[2][0], ...).

• The memory distance between two consecutive column accesses (such as A[0][0] and A[1][0]) is exactly one full row of the array.

• Memory size of one array row = 512 elements x 8 bytes = 4096 bytes.

1. Determine Cache Mapping and Thrashing Behavior for P2

• Total Cache Size = 32 KB = 32,768 bytes.

• Number of full array rows the cache can hold simultaneously = 32,768 bytes / 4,096 bytes = 8 rows.

• Number of cache lines available = 32,768 bytes / 128 bytes = 256 lines.

• Each consecutive row in a column jumps ahead by 4096 bytes, which corresponds to exactly 32 cache lines (4096 / 128).

• In a direct-mapped cache, the rows map as follows:

  • Row 0 maps to Cache Line 0

  • Row 1 maps to Cache Line 32

  • Row 2 maps to Cache Line 64

  • ...

  • Row 8 maps to Cache Line 256, which wraps around and overwrites Cache Line 0 due to direct mapping.

• Because the cache can only hold 8 rows before conflicting and overwriting itself, accessing elements column-by-column causes absolute cache thrashing. Every single access in the loop results in a cache miss.

1. Calculate Total Cache Misses (M2)

• Since every access is a miss, the total number of misses equals the total number of elements in the matrix.

• M2 = 512 x 512 = 262,144

1. Compute the Ratio (M2 / M1)

• Ratio = M2 / M1

• Ratio = (512 x 512) / ((512 x 512) / 16)

• Ratio = 16