Klausurfragen

• 1 core: S+P = 60 + 6 = 66 secs

  
  

• 2 cores: S stays seq, P divided on 2 cores —> 60/2

  max(6,30) = 30 secs

  
  

• 4 cores: S stays seq. P divided on 4 cores —> 60/4 = 15 secs

  max(6,15) = 15 secs

  
  

• P unendlich —> 0 secs

  total: max(0,6) = 6

  Speedup = original/new runtim = 66/6 = 11

  
  

• Amdahl’s law

s = shared, before loop

A = shared

i = private, in loop,parallel

Race Condition on S. both threads modify without synchronization

Solutions:

• #pragma omp critical

• #pragma omp reduction(+:s)

• race conditions (both thrads change same var, same time)

  in variant 1 in both threasd

• True sharing (both threads write same variable)

  in variant 1 in both threads

• False sharing (both threads write diff, but on same cache line)

  in variant 2, they are near in same cacheline

• solutions:

  • Cacheline Padding: extra space btw a and b —> in new cache line

  • Align both to new cache lines

• 320x20 (every process gets 320x20)

  every process has 2 grenzflächen

  communication per block: 2*320 = 640

  total for 16: 640*16=10240

• 80x80

  eevery block has 4 grenzflächen

  communication per block: 4*80 = 320

  total for 16: 16*320 = 5120

• First-Touch Policy: first thread decides in which NUMA kno var saved

  when sequentoal —> all values in one NUMA knot

• make parallel —> better

temporal locality

same memory loca. accessed repeatedly in short time

—> B

spatial locality

accesses in memory loc that are close to each other

—> A

Amdahls law

increasing number of cores + no linear performance

—> N = 1000

Gustafsons law

problem size increases, scaling with more cores improves significantly

—> N = 4000

6D hypercube

• 2^6 = 64 nodes

• (6*2^6)/2 = 192 edges

• 2^(d-1) = 2^(6-1) = 32 links

3D Torus

• 4*4*4 = 64 nodes

• (6*64)/2 = 192 edges

• 2 * 16 = 32 links

• dynamic scheduling —> improve Load Balancing

  dynamic instead of static

• Parallise inner loop —> better Load Distribution

  collapse(2) before schedule

• Strong Scaling: problem size remains constant, but work distributed over more cores —> reduces time

• Amdahls law: '# cores increase,

1. P0 still holds old value v=10

2. P1 loads v=33

Update-Based

write-update protocol —> all caches receive v=33 immediately

Invalidation Based

old values invalidated —> P1 fetches v=3 when needed

FLOPs per memory access

matrices where most elements zero

used: Scientific Computing, Machine Learning

• Speedup with 6 processors

  Amdahl law: 1/(S+P/N) = 1/(0.4+0.6/6) = 1/0.4+0.1 = 1/0.5 = 2

• Efficiency with 6 processors

  speedup/#processors = 2/6 = 0.33

• max speedup

  1/S+0 = 1/0.4 = 2.5

first: Weak Scaling

second: Strong Scaling

why derivate? —> overhead of comm. + synchr. dominates

—> reduce efficiency

1. OpenMP worksharing constructs

   • #pragma omp for - parallelizes loops

   • #pragma omp selections - runs diff tasks in parallel

1. mututal exclusoni

   • #pragma omp critical

   • #pragma omp atomic

clauses for ‘for’-qualifier control loop behavior btw threads

• schedule(dynamic,2)

  divide iterations in 2-chunks. when threads finished, get new

  good, when unequal runtime per iteration

• reduction(+:sum)

  every thread has private copy, at end all together

  good in parallel accumulation

#include <stdio.h>

#include <omp.h>

void f(), g0(), g1(), g2(), h(); // assumed to be defined elsewhere

int main() {

// Dummy variables to track dependencies

int a = 0, b = 0, c = 0, d = 0, e = 0;

#pragma omp parallel

{

#pragma omp single

{

// Task f → produces "a"

#pragma omp task depend(out: a)

f();

// Task g1 → waits for "a", produces "b" and "c"

#pragma omp task depend(in: a) depend(out: b, c)

g1();

// Task g0 → depends on "b", produces "d"

#pragma omp task depend(in: b) depend(out: d)

g0();

// Task g2 → depends on "c", produces "e"

#pragma omp task depend(in: c) depend(out: e)

g2();

// Task h → depends on "d" and "e"

#pragma omp task depend(in: d, e)

h();

}

}

return 0;

}

• two-sided: MPI_Send(), MPI_Recv()

• one-sided: MPI_Put(), MPI_Get()

• collective: MPI_Bcast(), MPI_Reduce(), MPI_Gather()

• standard MPI_Send()

• synchron MPI_Ssend()

• buffered MPI_Bsend()

• ready MPI_Rsend()

• MPI communicators

  group of processes that can communicate

• MPI tags

  integer labels used to identify messages

• MPI window objects

  memory region that other processes can access directly, w/o matching Recv()

• 2-sided: Communicators, Tags

• 1-sided: Communicators, Window Objects

• collective: Communicators

Deadlock guaranteed!!

both processes block at Send, waiting for other to Receive

no deadlock!

one side ready to receive, others send complete

deadlock guaranteed!!

each process wait for other to receive, deadlock cycle

no deadlock

all start with Recv, they will block, but no send is called

program hangs, but no deadlock

GPU

Device —> SMs —> Warps —> Threads

CUDA

Stream —> Grid —> Thread Block —> CUDA Threads

OpenMP

Master Thread —> Parallel Threads —> Worksharing constructs

MPI = distributed memory-system

each MPI process has own memory space

perfect for using all recources across machine

OpenMP = shared-memory system

all threads access same memory

PGAS = Partitioned Global Address Space

combines global addreass space with partitioning

NUMA = Non-Uniform Memory Access

memory physically distributed

OpenMP and PGAS sensitive to memory locality

7D hypercube

• diameter: 7

• shortest route: 2 bits different —> 2 min steps

• min steps: 7

combine to 8D hypercube

• additional nodes:

  • 7D: 2^7 = 128

  • 8D: 2^8 = 256 —> additional: 128

• additional links: 128 (each new node to 1 exist node)

• add new leading bit: Prepend 0 to old, 1 to new nodes

Blocking

not return until operation completed/safe

MPI_Send(), MPI_Recv(), …

easy to deadlock

Non-Blocking

return immediately

MPI_Isend(), MPI_Irecv()

later must call MPI_Wait()

—> avoid deadlock

number of floating point operation (FLOPs) per byte of memory accessed

—> tells us how much work a program does per memory access

high intensity —> compute-bound —> GPU friendly

low intensity —> memory-bound —> suffers from low memory

Shared memory

OpenMP, pthreads, ..

threads run on multiple cores of same machine

data is shared implicitiyl

distributed memory

MPI

processes can be on different mchines/nodes

must explicitly send/recv data

#pragma omp parallel for reduction(+:x)

Undeferred task

encountering task suspended and new task executed immediately

(by some thread)

deferred task

ecnountering task suspended and new task executed immediately

(by same thread)