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

2006

A CPU has a 32 KB direct-mapped cache with a 128-byte block size. Array A is a two-dimensional 512 × 512 array whose elements occupy 8 bytes each. Consider the following C code segment P1: Assume that A[0][0] is aligned to a 128-byte cache-block boundary.

 
for (i=0; i<512; i++) {
   for (j=0; j<512; j++) {
      x += A[i][j];
   }
}

The second code segment P2 is:

 
for (i=0; i<512; i++) {
   for (j=0; j<512; j++) {
      x += A[j][i];
   }
}

P1 and P2 are executed independently from the same initial state: no block of A is in the cache, and i, j, and x are held in registers. Let M1 and M2 denote the numbers of cache misses for P1 and P2, respectively. The value of M1 is:

Answer: C. 16384 — ConceptIn a row-major array traversal, consecutive elements occupy consecutive memory addresses. Fetching one cache block brings every array element contained…

  1. A.

    0

  2. B.

    2048

  3. C.

    16384

  4. D.

    262144

Attempted by 271 students.

Show answer & explanation

Correct answer: C

Concept

In a row-major array traversal, consecutive elements occupy consecutive memory addresses. Fetching one cache block brings every array element contained in that block into the cache.

Starting from a cold cache, a sequential scan that never reuses an evicted block incurs one miss per distinct block. Direct mapping adds no extra misses when an evicted block is not needed again.

Application

  1. A 128-byte cache block holds 128 ÷ 8 = 16 array elements.

  2. One row occupies 512 × 8 = 4096 bytes.

  3. Therefore, one row spans 4096 ÷ 128 = 32 cache blocks.

  4. P1 scans each row sequentially. The first access to a block misses, and its next 15 element accesses hit, so each row produces 32 misses.

  5. Across 512 rows, M1 = 512 × 32 = 16384 misses.

Cross-check

Assume that A[0][0] is aligned to a 128-byte cache-block boundary. The entire array occupies 512 × 512 × 8 = 2097152 bytes, or 2097152 ÷ 128 = 16384 distinct cache blocks. P1 visits every block once in sequential row-major order, which gives the same count.

Therefore, M1 = 16384 cache misses.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…