Basics of Parallel Computing (Tu Wien, Austria)
118 flashcards · Other · by Locke Lamora
Central Processing Unit (CPU)
Processor executes instructions stored in main memory Parts: several registers at least 1 arithmetic logic unit (ALU) often specialized units like floating point units (FPU)
Core
multi core CPUs most common today all cores on single chip (CPU) each core fully functional unit (has everything a single core CPU would have) communicate via interconnection network
Socket
CPU slot connector that houses a CPU on motherboard more than one possible
Uniform Memory Access (UMA)
all CPUs have same access time to memory
Non Uniform Memory Access (NUMA)
often occurs when placing several CPUs on a mainboard (several sockets) processors have different access times to the various memories many modern systems are NUMA systems
Types of multiprocessor systems
depends on the placement of the main memory (DRAM) UMA vs. NUMA
Graphics Processing Unit (GPU)
can be a dedicated card or part of CPU many small processing cores optimized for data-parallel throughput computation (eg. changing many pixels at the same time)
Distributed Computing
Distributed computing arises when one has to solve a problem in terms of distributed entities (usually called processors, nodes, processes, actors, agents, sensors, peers, etc.) such that each entity has only a partial knowledge of the many parameters involved in the problem that has to be solved.
Parallel Computing
The simultaneous use of multiple compute resources to solve a computational problem: A problem is broken into discrete parts that can be solved concurrently. Instructions from each part execute simultaneously on different processors
What is a Supercomputer?
A supercomputer is one large computer made up of many smaller computers and processors. Each different computer is called a node (compute node). Each node has processors/cores. With a supercomputer, all these different computers talk to each other through a communications network.
High Performance Computing
The practice of aggregating computing power in a way that delivers much higher performance than one could get out of a typical desktop computer or workstation in order to solve large problems in science, engineering, or business.
Unique to each thread are
Thread ID Saved registers, stack pointer, instruction pointer Stack (local variables, temporary variables, return addresses) Signal mask Priority (scheduling information)
Process vs. Thread
both can executed independent instructions work with different data within a process, multiple threads can be created
Items shared among threads within a process are
Text segment (instructions) Data segment (static and global data) BSS segment (uninitialized data) (global variables and static variables, initialized to zero) Open file descriptors Signals Current working directory User and group IDs
Single Instruction Multiple Data (SIMD)
provided by modern processors similar to vector operations same operation or set of instructions performed simultaneously on multiple data elements possibilities depend on instruction set
Parallel Computing Hierarchy
core: SIMD pipelining multiple functional units (eg. ALUs or FPUs) CPU or GPU: several control flows threads or processes executed by different cores computer cluster: use several compute nodes (consisting of multiple CPUs) in parallel
Parallel Runtime
The parallel runtime is the time that elapses from the moment a parallel computation starts to the moment the last processing element finishes execution.
Relative Speed-up
The relative speed-up Sr(n,p)S_r(n, p)Sr(n,p) is defined as the ratio of the running time Tpar(n,1)T_{par}(n, 1)Tpar(n,1) of the parallel code with 1 processor to the parallel running time on ppp processors Tpar(n,p)T_{par}(n, p)Tpar(n,p) , i.e., Sr(n,p)=Tpar(n,1)Tpar(n,p)S_r(n, p) = \frac{T_{par}(n, 1)}{T_{par}(n, p)}Sr(n,p)=Tpar(n,p)Tpar(n,1) .
Absolute Speed-up
The absolute speed-up Sa(n,p)S_a(n,p)Sa(n,p) is defined as the ratio of the best sequential running time Tseq(n)T_{seq}(n)Tseq(n) to the parallel running time on ppp processors Tpar(n,p)T_{par}(n,p)Tpar(n,p) : Sa(n,p)=Tseq(n)Tpar(n,p)S_a(n,p) = \frac{T_{seq}(n)}{T_{par}(n,p)}Sa(n,p)=Tpar(n,p)Tseq(n) where: nnn ... input size ppp ... number of processors
Parallel Efficiency
The parallel efficiency is defined as E(n,p)=Tseq(n)p⋅Tpar(n,p)=Sa(n,p)pE(n, p) = \frac{T_{seq}(n)}{p \cdot T_{par}(n, p)} = \frac{S_a(n, p)}{p}E(n,p)=p⋅Tpar(n,p)Tseq(n)=pSa(n,p) . speed-up alone does not always reveal how efficient a parallelization is (e.g. difference between speed-up of 10 with 32 processors or with 1024 processors)
Ahmdahl's Law
The potential speed-up of a parallel application is bounded by the sequential fraction of the code. Let sss , 0≤s≤10 \leq s \leq 10≤s≤1 denote the sequential fraction of a code and Tseq∗(n)T^*_{seq}(n)Tseq∗(n) the best sequential running time. Then, the attainable speed-up of the parallel code is: S(n,p)=Tseq∗(n)s⋅Tseq∗(n)+1p⋅Tseq∗(n)S(n,p) = \frac{T^*_{seq}(n)}{s \cdot T^*_{seq}(n) + \frac{1}{p}\cdot T^*_{seq}(n)}S(n,p)=s⋅Tseq∗(n)+p1⋅Tseq∗(n)Tseq∗(n) =1s+1−sp≤1s= \frac{1}{s+\frac{1-s}{p}…
Breakeven Efficiency
modern processors do not run all cores with the same frequency Parallel efficiency required to match speed with one core only computation: f1fp⋅p\frac{f_1}{f_p \cdot p}fp⋅pf1
Cost
The cost of a parallel algorithm denotes the total time that one uses all p processors, i.e., C=pTpar(p,n)C = p T_{par}(p, n)C=pTpar(p,n)
Cost Optimality
A parallel program is cost optimal if the cost of solving a problem on a parallel computer has the same asymptotic growth (as a function of the input size) as the fastest-known sequential algorithm on a single processing element, i.e., pTpar(p,n)∈O(Tseq(n))p T_{par} (p, n) \in O(T_{seq}(n))pTpar(p,n)∈O(Tseq(n)) .
Work
The work W of a parallel algorithm denotes the number of operations that are carried out.
Hyper-Threading
simultaneous multithreading (SMT) Intel term run two software threads concurrently on one core done by duplicating parts of the CPU (mainly registers) not duplicated are execution units: ALU, FPUs twice as many "logical cores" as physical CPU cores on average performance increases by 30% (not twice as fast!)
Work Optimality
A parallel program is work optimal if the work W has the same asymptotic growth as the fastest-known sequential algorithm on a single processing element, i.e., W∈O(Tseq(n))W \in O(T_{seq}(n))W∈O(Tseq(n)) .
Strong Scaling (based on Amdahl's law)
keep input size fixed increase the number of processors
Weak Scaling (based on Gustafson's law)
increase the number of processors scale instance size with the number of processors
Gustafson's Law
Idea: more powerful computer systems usually solve larger problems, not the same size problem in less time program consists of serial fraction sss and a parallel fraction 1−s1-s1−s parallel portion scales perfectly with the number of processors p if the parallel part is run on a serial processor, it would take p times longer than on p processors the speed-up is then the following : S=s+p⋅(1−s)s+1−s=s+p⋅(1−s)S = \frac{s+p\cdot(1-s)}{s+1-s}=s+p\cdot(1-s)S=s+1−ss+p⋅(1−s)=s+p⋅(1−s)
Ahmdahl vs. Gustafson
Embarrassing Parallelism
Means that the parallelization strategy is obvious: no advanced algorithms needed very little communication overhead little or no effort to split up work
Dynamic Scheduling
spawn new process for every chunk/task not best choice for many small tasks
Static Scheduling
round-robin assignment of work to processes pros: fast schedule building, small overhead cons: can hardly deal with heterogeneous workload danger of inefficient load balancing!
Python Multithreading
Uses GIL (Global Interpreter Lock) all threads need single GIL to progress Solution: Multiprocessing
Worker Pools
concept is always the same for both threads and processes we start a fixed number of workers (processes or threads) workers do the work (computation) often as many workers as there are cores initially, a dedicated thread/process creates a number of tasks and adds them to a shared data structure (also called channel, queue) workers may emit new tasks and add them to the queue when a worker is idle, it takes the next available task from the queue and executes it
Python Multiprocessing
create pool map task to processes we can asynchronously spawn new tasks chunks may be executed by one process only, it depends on who is fastest
Pros and cons of Pools
Pros: easy load balancing easy parallel computing Cons: choice of chunksize crucial queue can become bottleneck (one central data structure), always problematic (when chunks are too small) be careful, map creates entire argument list (mem usage) (if mem is an issue, use Pool.imap, which works on iterators) small input size causes no speed up
Chunk size considerations for pools
very small chunk size → large overhead if chunk size is too big → bad load balancing (we cannot utilize all cores)
Shared resources
concurrently running processes/threads want to access shared resource resource: variable, file, printer, ... problem: uncoordinated access is bad! (lost updates, erroneous results, ...) solutions: message passing, locks, signals, ...
Mutual Exclusion
When only one thread can enter critical section it is called mutual exclusion
Critical Section
Program parts in which shared resources get modified by concurrently running processes or threads.
Disadvantage of Locks
Can lead to deadlocks
Lock
A lock object is a standard way to ensure mutual exclusion. It implements two main functions: acquire() (or lock()): a thread calls the acquire() function when it is trying to enter the critical section release() (or unlock()): thread calls release() when it leaves critical section
Goal of Coordinated Writing of files
we have a single output file (a file handle) processes compute their local share concurrently after completion, each process wants to write its result to this shared output file
Possible solution for attaining goal of coordinated writing of files
introduce shared variable called turnid (indicates which process can write) we need to protect variable with a lock
Python inter-process communication tools
Queue (several process put and get tasks into/from queue) JoinableQueue (blocks until all tasks are done) Pipe (queue for two processes)
Goal of Message passing
create shared queue start ncoresncoresncores worker main process puts tasks into queue worker take tasks from queue and process them
Deadlock
A deadlock is a phenomenon involving multiple threads (two or more), whereby threads wait indefinitely to get access to resources while holding or not releasing other resources. you can substitute thread with process, or agent, or actor Typical situations where deadlocks occur using multiple locks and using different lock order blocking send/recv, put/get calls in different order
OpenMP Fork-Join Parallelism
Main sequential flow coordinates forking and joining of threads
OpenMP: Parallel region
Creates team of threads end of parallel region hast implicit barrier (threads wait till all completed)
OpenMP: Parallel for
parallelize for loops Syntax: #pragma omp parallel for Or: #pragma omp parallel { #pragma omp for for(i=0; i< 10; i++) {whateverCode()} } Implicit barrier after for Needs canonical form
OpenMP: Parallel for canonical form
loop variable is integer (int i) loop variable must not be modified inside the loop loop limit must not be changed in loop (i < N) Increment and decrement must be loop invariant (only i++, i+=step, i--, i-=step, no multiplications,...) No jumps (goto, break, throw) except to locations inside of loop
Which two types of memories are there in a parallel block (openMP)
Private and Shared
private variables openMP
each thread has unique access no risk of an access conflict multiple threads may use the same name, but the variables are in different locations modifications are only done on the local copy key words: private(a) firstprivate(a) lastprivate(a) potential risks: private(a) does not initialise! firstprivate initialises private variables with value of outside variable, lastprivate writes the last value of a private variable back to a global variable
shared variables openMP
all threads have access to same shared memory there is only one instance of a shared variable each thread can read and write shared variables synchronization of access is responsibility of the user
OpenMP: Static scheduling for
precomputed low overhead possibly bad load balancing static default: each process gets np\frac{n}{p}pn iterations static, chunk_size gives out iterations in chunks of chunk_sizein round robin schedule is deterministic
OpenMP: Dynamic Assignments
dynamic and dynamic,chunk_size each thread executes chunk_size many iterations requests another chunk continues until all chunks are done standard: no chunk_size specified -> default 1 schedule is not deterministic
OpenMP: Guided scheduling for
similar to dynamic, but decreasing chunk size: 1st thread gets: ⌈np⌉\left \lceil{\frac{n}{p}}\right \rceil ⌈pn⌉ iterations 2nd thread gets: ⌈n−⌈np⌉p⌉\left \lceil{\frac{n-\left \lceil{\frac{n}{p}}\right \rceil }{p}}\right \rceil ⌈pn−⌈pn⌉⌉ =K2= K_2=K2 iterations 3rd thread gets: ⌈K2p⌉\left \lceil{\frac{K_2}{p}}\right \rceil ⌈pK2⌉ If chunk_sizeis given, at least chunk_sizenumber of iterations is given to threads schedule is not deterministic
Performance consequences of schedule clauses
dynamic scheduling and a small chunk size is inefficient if each iteration is short-lived in such a case, static is the better choice makes huge difference ! rule of thumb for many short-running iterations, a static assignment works often well when the running time of iterations is very different, use dynamic strategies
OpenMP: reduction
Reduction examples: Find minimum, maximum, sum, product Generally: data race on reduction variable Solution: critical (slow) or reduction (fast) Syntax: #pragma omp parallel for reduction (+:sum) for(i = 0; i<n; i++){ sum += a[i]; }
Primitives for synchronisation: master
code block will be executed by the master thread only all other threads will pass this block no implied barrier on entry and exit
Primitives for Synchronization
in general, we need ways to protect read and write accesses to shared variables: master, barrier, single, critical, atomic there are also lock functions (do not cover this here)
Primitives for synchronisation: barrier
point in the program where threads wait for each other no thread in the team proceeds before all threads in the team of reached the barrier
Primitives for synchronisation: critical
marks code block to be a critical section only one thread will be inside this critical sections
Primitives for Synchronization: single
only one thread of the team will execute this block (not necessarily the master thread) other thread wait at the end, implicit barrier at the end avoid barrier with keyword nowait single with nowait -> the program has a race on x
Primitives for synchronisation: atomic
expression in subsequent line(s) of code is considered atomic may use specialized hardware instructions (fetch_and_add, compare-and-swap) similar to critical but applies to a single line of code (single assignment statement) expression must follow a given form: x++; x--; x = expr; atomic only protects the assignment, not the right-hand side!!!
Loop dependencies: Flow Dependence
S1 writes x and S2 reads x
Loop dependencies: Antidependence
S1 reads x and S2 writes x
Conditional loops in openMP
one can execute a loop in parallel if a condition is satisfied helps to avoid creating a team of threads (and the associated overhead)
Loop dependencies: Output Dependence
S2 writes x and S2 writes x
Why do we need tasks?
recursive parallel computations irregular applications (graph searches) a while loop with independent chunks of work in the body
Goal when dealing with loop dependencies
Eliminate dependencies in order to parallelize/ collapse loops
task directive
OpenMP also contains a task construct tasks are enqueued and later dequeued by the same or other threads generation of tasks can be done by a single thread or by multiple threads
What are openMP tasks composed of
code to execute data environment (set of variables or data owned by a task) thread reference (reference to thread executing a task, location of task) Tasks are created inside the parallel section!
Dependent Tasks: in
task depends on all previously generated sibling tasks that reference at least one of the list items in an out or inout dependency type
Dependent Tasks: out / inout
task depends on all previously generated sibling tasks that reference at least one of the list items in an in, out, or inout dependency type
Dependent Tasks in openMP
often necessary to formulate dependencies between tasks eg, one task produces something other task needs openMP uses keyword "depend" to denote task dependencies different types: in, out, inout we can also iterate over dynamic number of dependencies:
false sharing
problem of cache coherent systems (typical multicore machines) sometimes data are unintentionally shared inefficiently for example : modifications of one threads can unintentionally invalidate cache for others leads to performance issues placement of threads (thread pinning) has huge impact
How long are cache lines on hydra?
64 Bytes
Analyzing Programs
Algorithms often analyzed theoretically (Big O notation) O(n2)O(n^2)O(n2) better than O(n3)O(n^3)O(n3) (asymptotically) Evaluation in practice through experiments Measuring running time, throughput, etc. How fast can our code possibly run on a given machine? Use performance models for answering this question
Basic architectural model
computational elements (CPU,cores): computation consists of floating-point operations (multiply, add, compare, etc.) processors have a certain computational rate (e.g., 2 GFLOPs/s) memory elements (DRAM): movement of data is bounded by processor-memory interconnect links have a maximum memory bandwidth (e.g., 10 MB/s)
Arithmetic Intensity (AI) of computational kernels
The Arithmetic Intensity (AI) is a kernel’s ratio of computation to traffic. It is measured in FLOPs/Bytes.
Arithmetic Intensity (Overview)
AI in practise
usually code too complex for analytical estimation use hardware performance counter for measuring total number of FLOPS/s and communication volume tools: LIKWID, PAPI, linux perf,...
Roofline Model
hope to always attain peak performance (FLOPs/s) BUT performance limited by finite reuse of data maximum bandwidth available (minimum) run-time of kernel is bounded
Roofline Model: Graphically
log log scale ridgepoint: where roof meets diagonal roofline has to be created only once (dependent only on machine not on kernels) Differences between kernels:
Roofline model summary
helps to estimate performance potential of computational kernels on multi-core machines visual 2D performance model (log-log scale) y axis: attainable GFLOPs/s: could also be any other metric: INTs/s x axis: arithmetic intensity of a computational kernel identify kernels that are bandwidth- or compute-bound independent of computational kernel dependent on machine can also be generated for GPUs (other accelerators) can also consider cache levels
CUDA
parallel computing platform and API by Nvidia allows to use GPUs for general purpose processing language bindings for C, C++, Fortran host : refers to the CPU and its memory device: refers to the GPU and its memory
GPU vs CPU Architecture
CPU designed to execute threads as fast as possible several tens of threads large caches attempt to hide DRAM access times complex control-logic for speculation and out-of-order execution GPU designed to execute thousands of threads in parallel hide memory access latencies with computation requires applications with a high degree of parallelism optimized for data-parallel, throughput computation
CUDA programs
CUDA C/C++ program consists of: code that executes on the host, the CPU parallel code that executes on the GPU Execution flow, controlled by host code copy data to GPU memory launch kernel on GPU copy data back to host (CPU memory)
CUDA thread organization
threads are grouped into blocks blocks are grouped into grids thread executes on a single streaming processor blocks of threads execute on a streaming multiprocessor a grid executes on a single GPU device can execute multiple kernels concurrently
CUDA organisation
SIMT(single instruction multiple thread) smallest execution unit is a warp: 32 threads (hardware side) Implemented in the streaming multiprocessor (SM) number of SMs varies by graphics card 32 threads within a warp execute a single instruction stream in lockstep warps are combined into thread blocks: 32 - 2048 threads warp schedulers and dispatch units distribute instructions to free compute resources
CUDA kernel syntax
kernel <<<num_Blocks, threads_per_block>>> (args...)
CUDA Memory Hierarchy
Thread indexing
essential to know thread’s index to define which thread does what blocks of threads can be organized into 1D, 2D, or 3D arrays of threads grids of blocks can also be organized into 1D, 2D, or 3D arrays of blocks there are restrictions by the hardware for these values we need to pay attention when indexing threads so that we don't try to access memory out of bounds!
Location of a Thread
CUDA has built-in variables for finding location of thread location of a block blockIdx.x, blockIdx.y, blockIdx.z location of a thread in a block threadIdx.x, threadIdx.y, threadIdx.z size of a block blockDim.x, blockDim.y, blockDim.z
2D and 3D thread blocks
often problems can be expressed better if threads are arranged logically in 2D or 3D arrays use dim3 to specify the dimensions of threads blocks/grids can mix them (eg. 2D thread blocks in a 1D grid layout) important to adapt to problem
Global Memory
largest, highest-latency memory on a GPU commonly used (cudaMalloc, cudaFree) variables can be declared dynamically or statically static declaration __device__ from device code access pattern to global memory important for performance warps performs load/stores from/to memory, then we have 2 key factors distribution of memory addresses accessed by threads in a warp alignment of memory addresses per transaction when accessing data from global memory, we should ensure (for performance, not for co…
Alignment
depending on the device, data is served in blocks via 32, 64, or 128 byte transactions data should be aligned properly to the respective boundary to utilize max. bandwidth