Obsidian + 🪴 Quartz 4.0

HPC - Lecture 7 - Memory Hierarchy

7 min read

HPC - Lecture 5 - Memory Hierarchy

Software performance: top500 list ranks supercomputers on the basis of their performance with the LINPACK benchmark, a software for solving systems of linear equations.

Performance is measured by counting the number of fp operations performed per unit of time, i.e.:

Recently units of measurements reached the Eflops = /sec.

Time complexity vs Performance

Typically, the goodness of an algorithm is measured by:

  • Time complexity (number of trades):
  • Space complexity (number of memory locations)

also depends on other factor:

  • depends on algorithm and depends on hardware.

However, this neglects the access time to the memory :

It is not reasonable to neglect memory-access time :

Therefore formula becomes:

  • and depends on the algorithm
  • and depends on the hardware

is an amplification factor for . We assess the impact of on Perf.

Let us compute Perf =

In ideal case we have:

In the real case, tmem > 0:

Then multiplying num. and den. by

  • The term at the denominator i.e. (1 + X) , X is called performance degration factor of peak performance.

Impact of on Perf:

Assuming the q called Memory-to-compute Ratio:

and therefore bringing performance Perf closer to peak performance Perf*.

Observation: assuming , one has:

If one obtains (that is, about half of peak performance).

Example: With 3 Ghz CPU and DDR4 memory, one has:

therefore must be:

Tens of floating-point operations for each memory access.

Hierarchical memory

Using data in the upper memory levels (L1 and L2 cache) means reducing memory accesses and more easily sustaining the CPU operating speed.

Example: CPU capable of executing 1 floating-point operation in one cycle of s.

Data in L2 cycle ( 5 cycles per access, i.e. ).

If (that is, 5 f.p. ops per transferred datum), we get about of .

Data in main memory ( cycle per access, i.e. ).

If (that is, 30 f.p. ops per transferred datum), we get about 50% of .

The gap between and can be bridged through the use of caches.

How caches work

Data move from memory to the L1 and L2

  • caches are always inside the CPU

These data remain in the caches for subsequent references

  • when the CPU requests a datum, the L1 cache is checked
  • if the datum is present in L1 cache, it is used; if it is absent (L1 miss), the L2 cache is checked
  • if the datum is present in L2 cache, it is used; if it is absent (L2 miss), main memory is checked

Caches are small in size. Example: Intel Core Ultra 7 265K, 20 cores (2024), L1 = 20x192 KB, L2 = 20x3 MB, L3 = 30 MB.

When the CPU requests new data and the cache is full, the old data are replaced by the new ones in the caches (with LRU-like algorithms).

Caches are organized into cache lines and data transfers from memory occur in blocks of contiguous data (cache block):

  • when one datum is requested, a block of nearby elements is transferred
  • if all data in the block are used, the cost of the cache miss is amortized

Each cache level has different:

  • latency (cache access time)
  • bandwidth (number of bytes transferred per unit time)

Many cache levels: efficient cache management is possible only through low-level languages and depends strongly on the operating system, but something can still be done at the application level.

Main methodology: restructure algorithms so as to reuse all the data in a cache block several times.

Some simplifications from now on:

  • System with 2 memory levels (cache memory and main memory)
  • Any possible overlap between memory access and ALU is ignored
  • Cache memory large enough to contain at least 3L data elements
  • Cache-memory access time is neglected

Case study: Matrix Multiplication

Consider the update operation for matrix multiplication: , where . The standard implementation involves three nested loops:

for i = 1 to N
    for j = 1 to N
        for k = 1 to N
            C(i,j) = C(i,j) + A(i,k) * B(k,j)
        endfor
    endfor
endfor

There are 6 possible index permutations (). While all versions perform exactly floating-point operations, their memory access patterns differ significantly, leading to up to a 10x performance gap.

Impact of Loop Ordering on Performance

Experimental data (Intel Xeon E5410, 2.3 GHz) shows that ikj and kij orderings achieve the highest performance.

The reason lies in spatial locality and cache line utilization:

  • ikj ordering: In the inner loop (over ), the algorithm accesses and contiguously in memory (assuming row-major order).
    • If a row fits in cache (), total memory accesses are .
  • jki / ijk ordering: The inner loop accesses elements that are not contiguous or requires frequent re-loading of data.
    • This results in , causing cache thrashing as increases.

Cache Miss Analysis and Ratio

When the matrix size exceeds the cache capacity, performance drops because the amortization of cache misses fails. The memory-to-compute ratio is defined as:

For the general case (), the total accesses increase significantly. For example, if is large: Where is the cache line size. As grows, remains high, meaning the CPU spends more time waiting for data than performing computations.

The Blocked Algorithm Solution

We use blocking (or loop tiling). The matrices are split into sub-blocks of order , where is chosen such that the blocks fit within the cache memory.

Each block of is the product of a block of rows of and a block of columns in

Blocked Algorithm Structure:

for ii = 1 to N/L
    for jj = 1 to N/L
        for kk = 1 to N/L
            ! Perform matrix multiplication on blocks of size L x L
            C(ii,jj) = C(ii,jj) + A(ii,kk) * B(kk,jj)
        endfor
    endfor
endfor

As N increases, the performance of the blocked version remains constant:

Complexity Analysis: For block products, the total memory accesses are: The resulting ratio is:

Since is now independent of (for ), the performance remains stable across different matrix sizes.

Multi-level Cache Implications

In architectures with multiple cache levels (L1, L2, L3), the strategy must be extended:

  • L1 Cache: Managed with 3 nested loops at the register level.
  • L2 Cache: Requires 6 nested loops (blocking for L1).
  • L3/Main Memory: Requires 9 nested loops (blocking for L2).

It is necessary to minimize communication among all levels and find the right block sizes.

Optimal block size selection is highly architecture-dependent and typically requires low-level optimization or specialized libraries like BLAS (Basic Linear Algebra Subprograms).

Graph View