CPU Parallelism Flashcards
What is the Roofline model?
• A visual aid to understand software performance
• Relates processor performance to off-chip memory traffic (bandwidth often the bottleneck)
• Horizontal bound (peak performance) is the maximum capability of the processor. Is either 𝑅𝑝𝑒𝑎𝑘 or 𝑅𝑚𝑎𝑥
• The angled bound represents the maximum memory bandwidth available and is either the theoretical (from processor spec) or measured bandwidth (see STREAM benchmark). To plot this, multiply 𝐼 ∗ 𝑏𝑦𝑡𝑒/𝑠 (bandwidth)
If a program has no floating point operations, what arithmetic intensity does it have?
A low arithmetic intensity
What is the Von Neumann architecture?
Single, centralised control (CPU) that consists of a control unit and an arithmetic/logic unit.
• Separate storage area where both instructions and data are stored.
• Instructions are executed by the CPU, so they must be brought from the memory into the CPU.
• The data must also be brought from memory into the CPU in order to be acted upon.
• The CPU contains registers which acts as a scratchpad for temporary storage.
• Data and instructions share a common bus, so an instruction fetch, and a data operation can not happen at the same time – the von Neumann bottleneck.
What are the steps of the Von Neumann cycle? (Fetch execute)
- Fetch the instruction corresponding to the
Program Counter from memory - Decode the instruction
- Fetch data from memory
- Execute the instruction - Write back results
(Inherently serial)
How many clock cycles does the fetch execute cycle take?
If we assume each step takes one clock cycle (more in reality), an operation that requires 1 clock cycle (at the EX stage), now takes 5 clock cycles before we can move on to the next instruction
What is out of order execution?
If instruction 3 has its data ready before instruction 2, the processor will execute instruction 3 first, but later reorder the results to appear as if instruction 2 was executed first.
What is speculative execution?
If the insruction is yet to be executed, the processor might guess which of the two sides of the branch might be taken and start executing the next instruction on that branch speculatively.
It might have to backtrack later if its guess turns out to be wrong
What is fused-multiply-add?
Implement 𝑎 = 𝑎 + (𝑏 ∗ 𝑐) as a single operation
(common in operations like convolutions, matrix multiplications etc)
What can we do to improve the Von Neumann bottleneck?
- Parallelism!!
• Add some fast memory on the chip – Cache
• The bigger the cache, the slower it is.
Solution?
Have multiple hierarchical caches – L1, L2, L3
and so on. L1 is faster but smaller than L2, and so on.
• Caches exploit spatial locality and temporal locality in a program
What is spatial locality?
If a memory location is accessed, it is very likely that its neighbours will be accessed soon
What is temporal locality?
If a variable (memory location) is accessed, it is very likely to be needed again soon.
What kind of parallelism does pipelining give?
Instruction-Level Parallelism (ILP)
What is Single Instruction Multiple Data? (SIMD)
• If one addition operation takes on clock cycle, the code on the right runs in 1000 clock cycles.
• Instead of doing one iteration of this loop in one clock cycle, we could do four (for example)
• This code would run in 250 clock cycles
• This is called vector processing –Also known as Single Instruction, Multiple Data (SIMD)
What is Simultaneous Multithreading?
• Intel brands it as Hyperthreading
• Allows a core to execute multiple threads at the same time.
• Software sees more virtual cores than there are physical cores
• Works well if there are different workloads – less so if two threads are doing similar operations. They may be competing for resources on the core and may run slower than just 1 thread on the core
• In HPC, workloads are usually similar. Hence Hyperthreading is disabled on Barkla.
Why might more cores not make the program faster?
• Cache contention
• What if one core changes some data that another core needs soon after.
• Advanced Reading: False sharing
• Memory contention – locks/semaphores
• Interconnects get slower the more the number of cores, more traffic.
• To effectively utilise multiple cores, programs must be written differently.
• Programmers must think in parallel
• Load balancing
