CS 208 s21 — Learning Block #18

Table of Contents

1 Quick Check

If we have 6-bit addresses and block size \(B = 4\) bytes, which block and byte does 0x15 refer to?1

2 Exercise

What is wrong with this code (and how would you fix it)?2 

int sum_array_3D(int a[M][N][L]) {
    int i, j, k, sum = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < L; j++)
            for (k = 0; k < M; k++)
                sum += a[k][i][j];
    return sum;
}

cache-spreadsheet-tags.png

What happens on a request for address 0x10?3

  • block offset = _
  • set index = _
  • tag = _
  • hit or miss?
  • any changes to data in the cache?

3 Practice

CSPP practice problem 6.9 (p. 616)4

The following table gives the parameters for a number of different caches. For each cache, determine the number of cache sets (S), tag bits (t), set index bits (s), and block offset bits (b).

Cache m C B E S t s b
1. 32 1,024 4 1        
2. 32 1,024 8 4        
3. 32 1,024 32 32        

Footnotes:

1

0x15 is 0b 01 0101 (6-bit address). With a block size of 4, we need 2 bits to specify a byte within a block, leaving the 4 higher order bits as the block number. Hence, 0x15 refers to byte 0b01 (1) and block 0b0101 (5).

2

The loop ordering results in a very inefficient stride (\(N \times L\)). They can be reordered to achieve a stride 1 access pattern 

int sum_array_3D(int a[M][N][L]) {
    int i, j, k, sum = 0;
    for (k = 0; k < M; k++)
        for (i = 0; i < N; i++)
            for (j = 0; j < L; j++)
                sum += a[k][i][j];
    return sum;
}
3
  • block offset = 00
  • set index = 00
  • tag = 01
  • hit or miss? miss, tag doesn't match
  • any changes to data in the cache? bytes at 0x10, 0x11, 0x12, and 0x13 are loaded in, bytes from 0x00, 0x01, 0x02, and 0x03 removed
4
Cache m C B E S t s b
1. 32 1,024 4 1 256 22 8 2
2. 32 1,024 8 4 32 24 5 3
3. 32 1,024 32 32 1 27 0 5