Locality mechanism of CPU

Load/store architecture

  • Only load and store instructions can access memory.
  • Once data is loaded from memory to registers, and then processors typically use them multiple times. (temporal locality)
  • When loading data from main memory, processors read data size of one cache line at once. (spatial locality)

Modern CPUs have several levels of hierarchy. Why? Speed vs. Size.

  • Registers – Caches (multiple levels inside it) – Main memory (external) – Disks.
  • Higher level (ex. Register): Lower latency, but smaller storage size.
  • Lower level (ex. Disk): Higher latency, but larger storage size.
  • Exploiting locality is the way to use the hierarchical structure more efficiently.

Performance metric to measure the speed.

  • Latency: Closer device (higher level of hierarchy) has lower latency. Placement is important.
  • Bandwidth: Related to the capability of the interface. Bandwidth of off-chip devices are limited by capability of interface, typically wires, so there is a big difference between on-chip devices and off-chip devices. However, within a category, there is no significant of difference.
  • Example (It is just for showing the trend, not exact value)
 LatencyBandwidth
Registers1 cycle200GB/s
Last Level Cache (LLC)About 10 cycles100GB/s
Memory10s of cycles10GB/s
DISK4~8ms6Gb/s
Flash Memory10~100us6Gb/s

Cache-aware software

  • To obtain performance, the program should be aware of the cache architecture and parameters.

Example: Dense Matrix-Matric Multiplication

  • Problem to solve: C (MxN matrix) = A (MxK matrix) * B (KxN matrix)
  • Assumption 1: For simplicity, all matrices are NxN square matrices.
  • Assumption 2: Matrices are stored in row major order (typical way in C/C++, some languages like Fortran has column major order)

Original program.

for (i=0; i<N; i++) {
   for (j=0; j<N; j++) {
      C[i][j] = 0;
      for (k=0; k<N; k++)
         C[i][j] += A[i][k] * B[k][j];
   }
}
  • Since one cache line is typically 64 or 128 bytes long, one cache line contains multiple elements of a given matrix. (spatial locality)
  • Lots of cache misses. Why?
    • Matrix A has benefit from cache hit since access is done in the order it stored.
    • Matrix C exploits temporal locality: Calculation for a particular element of C is completely done at one time. Matrix C also exploits spatial locality because update is done in the order it stored.
    • However, B[k][j] and B[k+1][j] are separated by N, so every iteration of the most inner loop incurs cache miss. Data in a newly loaded cache line is not reused, but just wastes cache memory.

Solution #1: Swapping the order of loops to exploit locality. 

for (i=0; i<N; i++) {
   for (k=0; k<N; k++) {
      C[i][j] = 0;
      for (j=0; j<N, j++)
         C[i][j] += A[i][k] * B[k][j];
   }
}
  • Matrix A exploits temporal locality as well as spatial locality.
  • Matrix B also has benefit from spatial locality since its access pattern is changed from column direction to row direction.
  • Matrix C loses temporal locality, but holds spatial locality.
  • However, if the row size is much larger than a cache line size, it does not work as expected.

Solution #2: Divide a row or a column into small-sized blocks, which fit into a given cache size, and then calculate its partial result.

  • The final result can be obtained by accumulating the partial results. Break-up is started from the most inner loop to exploit locality.

Solution #3: Break up the original matrix into several small-sized matrices.

  • It is possible to reuse each small-sized chunk.
  • Assumed the block size is BxB, then total number of cache accesses becomes, (B2*N/B*2 + B2)*N2/B2
  • With the original code, there are N3-times MADD (Multiply and Add) operations, thus number of cache accesses becomes 4*N3. (D = A * B + C, A/B/C/D are requested to read from memory)
  • Therefore, the hit rate is (4*N3) / (((B2*N/B*2 + B2)*N2/B2) ≈ 2B, if N is large enough. It means large B is beneficial to achieve higher hit rate.
  • B can be large up to sqrt(cache size/3) in the ideal condition. (3*B2 < cache size) However, cache is non-ideal, means that not fully associative, cache line, so B should be much smaller.

Solution #4: Blocks within a block.

  • Latency is important to achieve high performance, so block size should be small enough to insert in a L1 cache. However, if block size is determined by L1 cache size, which is relatively small, it needs more off-chip bandwidth, so block size should be large enough to fit into LLC size as well. These conflicting requirements lead to multiple levels of blocking that match the locality hierarchy.
  • Using blocks in a block is good way to exploit both latency and bandwidth. While loading a big sized block into LLC to reduce off-chip bandwidth, CPU can compute with smaller sized block fit into L1 cache to exploit its lower latency.

Solution #5: Using registers for highly reused variables.

  • C[i][j] is replaced with registers and write into memory at the final step. It effectively reduce the frequency of accessing memory.
  • For example, (index is used to identify each chuck in a matrix)
    • C00 = A00*B00 + A01*B10 + A02*B20 + A03*B30
      C01 = A00*B01 + A01*B11 + A02*B21 + A03*B31
    • A and C are reused, thus can be replaced with registers. The following is the result.
    • R2 = A00; R3 = A01; R4 = A02; R5 = A03;
      R0 = R2*B00 + R3*B10 + R4*B20 + R5*B30
      R1 = R2*B01 + R3*B11 + R4*B21 + R5*B31
      C00 = R0; C01 = R1;
  • When using registers instead of memory access, block size should be small because most systems have only a limited number of registers.
  • Loop unrolling is useful technique to apply this optimization.

Cache-oblivious Software

Cache-aware software is highly dependent on the details of the machine, for example, cache size of each level, and number of registers. To avoid it, oblivious algorithm can be used. Reclusive algorithm is one example of oblivious algorithm, but it usually needs lots of memory space because of stack.