Consider a machine with a 2-way set associative data cache of size 64 Kbytes…
2008
Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes. A program to be run on this machine begins as follows:
double ARR[1024][1024];
int i, j;
/*Initialize array ARR to 0.0 */
for(i = 0; i < 1024; i++)
for(j = 0; j < 1024; j++)
ARR[i][j] = 0.0;The size of double is 8 bytes. Array ARR is located in memory starting at the beginning of virtual page 0XFF000 and stored in row major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by the program are those to array ARR.
Consider the data given above. Which of the following array elements has the same cache index as ARR[0][0]?
Answer: B. ARR[4][0] — Concept. A set-associative cache splits every byte address into a block offset, a set index and a tag. An address a lies in block number ⌊a ÷ L⌋, where L is…
- A.
ARR[0][4]
- B.
ARR[4][0]
- C.
ARR[0][5]
- D.
ARR[5][0]
Attempted by 184 students.
Show answer & explanation
Correct answer: B
Concept. A set-associative cache splits every byte address into a block offset, a set index and a tag. An address a lies in block number ⌊a ÷ L⌋, where L is the block size in bytes, and that block is mapped to set index ⌊a ÷ L⌋ mod S, where S is the number of sets. Two addresses therefore share a cache index exactly when their block numbers are congruent modulo S. From this follows a convenient sufficient test: if the byte distance between two addresses is a whole multiple of L × S — the cache’s set stride — their block numbers differ by a whole multiple of S, so the set index is unchanged. The converse is not automatic, because two addresses at different offsets inside corresponding blocks can also share an index, so a non-stride separation must be settled by comparing block numbers directly. For a row-major two-dimensional array the byte address of ARR[i][j] is base + (i × C + j) × E, where C is the number of columns and E the size of one element in bytes.
Applying it to this cache and this array.
Cache geometry: the cache holds 64 KB ÷ 16 B = 4,096 blocks, and 2-way set associativity puts 2 blocks in every set, so the number of sets is 4,096 ÷ 2 = 2,048.
Set stride = block size × number of sets = 16 × 2,048 = 32,768 bytes = 215 bytes = 32 KB. A separation that is a whole multiple of 32,768 therefore always preserves the set index, and any other separation has to be checked by comparing block numbers.
Array geometry: C = 1,024 columns and E = 8 bytes, so one complete row occupies 1,024 × 8 = 8,192 bytes = 8 KB. Stepping one column to the right advances the address by 8 bytes; stepping one row down advances it by 8,192 bytes.
Separation of each candidate from ARR[0][0], using (i × 1,024 + j) × 8 bytes: ARR[0][4] → 4 × 8 = 32 bytes; ARR[0][5] → 5 × 8 = 40 bytes; ARR[4][0] → 4 × 8,192 = 32,768 bytes; ARR[5][0] → 5 × 8,192 = 40,960 bytes.
Test each separation against the stride: 32,768 = 1 × 32,768 is exactly one stride, so that separation preserves the set index. The separations 32, 40 and 40,960 are not whole multiples of 32,768, so each must be settled by comparing block numbers directly.
Convert those three separations to block counts using ⌊separation ÷ 16⌋: 32 and 40 bytes both land 2 blocks past ARR[0][0]’s block, and 2 mod 2,048 = 2; 40,960 bytes lands 2,560 blocks past it, and 2,560 mod 2,048 = 512. Neither 2 nor 512 is 0, so none of those three keeps ARR[0][0]’s set index, and ARR[4][0] is the element that lands on it.
Cross-check with absolute addresses. ARR[0][0] starts at virtual page 0XFF000 with a 4 KB page size, i.e. byte address 0XFF000 × 4,096 = 0XFF000000 = 4,278,190,080. Its block number is 4,278,190,080 ÷ 16 = 267,386,880, and 267,386,880 mod 2,048 = 0, so ARR[0][0] occupies set 0. Computing the block number and set index of every candidate the same way gives:
Element | Separation from ARR[0][0] | Byte address | Set index |
|---|---|---|---|
ARR[0][4] | 32 bytes | 0XFF000020 | 2 |
ARR[0][5] | 40 bytes | 0XFF000028 | 2 |
ARR[4][0] | 32,768 bytes | 0XFF008000 | 0 |
ARR[5][0] | 40,960 bytes | 0XFF00A000 | 512 |
Result. ARR[4][0] shares set index 0 with ARR[0][0], because 32,768 bytes is exactly one set stride. Note that the 2-way associativity changes only how many blocks may sit in a set at the same time; the index itself is fixed by the 2,048 sets, and the 32-bit virtual address width and 4 KB page size affect address translation rather than this index calculation.