Here we’re taking into consideration that all processors reading/writing to the same memory space is expensive:
Intel i7 Kaby Lake has a ring interconnect (introduced in Sandy Bridge)
Each Core is connected to the ring twice for some reason, not sure why?
In SUN Niagara 2 (UltraSPARC T2), which was one of the first multithreading chip, each core was connected to every cache via a crossbar interconnect. The interconnect takes as much space on the chip as one core.
Non-uniform memory access (NUMA)
Latency of accessing a memory location may be different from different processing cores in the system
Message Passing
- Threads operate in their own address space and communicate by sending/receiving messages.
- With this, we can actually connect different hardware together to create a large parallel machine.
- Since there’s no shared address space, there is no mutex or barriers. Threads can wait for message from another thread to achieve synchronization.
Arithmetic intensity
Arithmetic Intensity = {Amount of computation (e.g. instructions)} / {Amount of communication (e.g. bytes)}
Cache Blocking
Consider a grid of N times N and for the problem we are solving we will access all neighbours of an element.
When iterating in row major order, we’ll fetch a cache line for the current row, previous row and next row. This will be cache hit for some time and then when we come back to process the next row, we might have to fetch the cache line for previous row again.
This is artifactual communication, which is communication caused as an artifact of other things. As opposed to inherent communication which is due to the algorithm.
In this grid case, we can iterate diagonally. For a row, increase column number for cache line size and then go to next row. Continue this until we have processed cache line size column across all rows then move to next chunk.
Performance Analysis Strategy
- First try the simplest solution and measure how much time it’s taking
- Determine if performance is limited by computation, memory bandwidth (or latency) or synchronization
- Try to establish “high watermarks” — What’s the best we can do in practice.
Roofline model
Going along x-axis, the programs are doing more arithmetic operations per byte read. Going along y-axis, the programs are attaining more GFLOPS, i.e. able to do more operations per second. The code flatlines when we reach the max GFLOPS supported by the processor.