Memory and Cache

Question 1

Why is memory access a performance bottleneck in modern computers?

Answer 1

Main memory access is much slower than CPU operations.

Can take ~100 clock cycles

Question 2

What is the purpose of the memory hierarchy?

Answer 2

To balance:
- Capacity
- Cost
- Access time

It also ensures frequently accessed data is available in faster memory levels.

Question 3

What is cache?

Answer 3

A small amount of fast memory which holds data fetched from, and written to, memory

Question 4

How is cache structured in modern CPUs?

Answer 4

CPUs have multiple levels of cache (L1, L2, L3), each progressively larger but slower.

Question 5

What are the two main types of locality that caches exploit?

Answer 5

1. Spatial Locality – Data near recently accessed memory is likely to be used.
2. Temporal Locality – Recently accessed data is likely to be reused soon.

Question 6

How does spatial locality work?

Answer 6

1. Data is fetched in fixed size blocks (cache lines)
2. When we access adjacent memory, it is likely to be in cache (cache hit)
3. If it’s not in the cache we have a cache miss, and the correct data cache line is fetched from main memory

Question 7

Why is loop order important in C for efficient memory access?

Answer 7

• Accessing memory sequentially improves cache efficiency.
• Looping over 2D array rows first (before columns) results in more cache hits.

Question 8

What is cache blocking? What are the benefits?

Answer 8

• Computations are split into blocks that fit in cache
  Benefits:
• Maximises data reuse
• Much faster data access
• Exploits temporal locality

Question 9

How can reducing problem size affect performance testing?

Answer 9

If a test case is too small, memory behavior (e.g., cache misses) may not be representative of real workloads.

Question 10

What can compilers do to optimise memory access?

Answer 10

Techniques like loop interchange and cache blocking can improve cache efficiency.

Question 11

What is arithmetic intensity?

Answer 11

The ratio of floating-point operations to data movement, measured in FLOPs/byte.

Question 12

What does the roofline model describe?

Answer 12

The maximum floating-point performance of an application based on:
1. Peak performance
2. Memory bandwidth
3. Arithmetic intensity

Question 13

When is an application compute-bound vs. memory-bound?

Answer 13

• Compute-bound: High arithmetic intensity, limited by CPU performance.
• Memory-bound: Low arithmetic intensity, limited by memory bandwidth.

Question 14

What does NUMA stand for? What is it?

Answer 14

• Non-Uniform Memory Access
• NUMA is the phenomenon that memory at various points in the address space of a processer have different performance characteristics.

Question 15

Why does NUMA exist?

Answer 15

Multi-socket CPUs have separate memory controllers, making remote memory accesses slower than local ones.

Question 16

How does memory allocation work in a NUMA system?

Answer 16

First Touch Policy - Memory is allocated on the first memory controller that accesses it.

Question 17

How does NUMA affect OpenMP programs?

Answer 17

If one thread initialises memory and other threads access it later, remote memory accesses slow performance.

Question 18

What is hybrid parallelism?

Answer 18

Using both MPI (for distributed memory) and OpenMP (for shared memory) together.

Question 19

How can hybrid parallelism help with NUMA effects?

Answer 19

• Assign one MPI process per socket
• Each MPI process starts OpenMP threads within a single socket

Question 20

How do you compile and run an MPI+OpenMP program (if it was titled lissajous.c)?

Answer 20

mpicc -std=c99 -o lissajous -fopenmp lissajous.c -lm
export OMP_NUM_THREADS=2
mpirun -np 2 ./lissajous