University of Washington Sec on 7: Memory and Caches Cache basics Principle of locality Memory hierarchies Cache organiza on Program op miza ons that consider caches Caches and Locality University of Washington Why Caches Work Locality: Programs tend to use data and instruc ons with addresses near or equal to those they have used recently Temporal locality: Recently referenced items are likely block to be referenced again in the near future Spa al locality: Items with nearby addresses tend to be referenced close together in me block How do caches take advantage of this? Caches and Locality University of Washington Example: Locality? sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum; Caches and Locality University of Washington Example: Locality? sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum; Data: Temporal: sum referenced in each itera on Spa al: array a[] accessed in stride 1 pa ern Caches and Locality University of Washington Example: Locality? sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum; Data: Temporal: sum referenced in each itera on Spa al: array a[] accessed in stride 1 pa ern Instruc ons: Temporal: cycle through loop repeatedly Spa al: reference instruc ons in sequence Caches and Locality University of Washington Example: Locality? sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum; Data: Temporal: sum referenced in each itera on Spa al: array a[] accessed in stride 1 pa ern Instruc ons: Temporal: cycle through loop repeatedly Spa al: reference instruc ons in sequence Being able to assess the locality of code is a crucial skill for a programmer Caches and Locality University of Washington Another Locality Example int sum_array_3d(int a[M][N][N]) { int i, j, k, sum = 0; for (i = 0; i < N; i++) for (j = 0; j < N; j++) for (k = 0; k < M; k++) sum += a[k][i][j]; return sum; } What is wrong with this code? How can it be fixed? Caches and Locality