Parallele Programmierung - FS18
Begriffe für Prüfung Parallele Programmierung ETH
Begriffe für Prüfung Parallele Programmierung ETH
-
- 1 / 26
-
Flashcards
Amdahl's law
Sp = 1/(f+(1-f)/p)
S: Speedup
p: n Processors
f = Anteil nicht parallelisierbarer Instruktionen
Gustafson's law
Sp = p + (p-1)f
S: Speedup
p: n Processors
f: sequential fraction of any parallel process
max Speedup (Amdahl)
Amdahl with p -> inf
Pipeline troughput (Durchsatz)
troughput = 1 / (max(computationtime(stages))
[ignoring lead-in and lead-out time]
Latency (Latenz)
time to perform a computation
balanced pipeline: constant over time
Lock Contention
If a thread wants to take a lock that is already taken by another thread
Solution: Back off if the lock cannot be taken
Mutex
Mutual Exclusion
Solutions for ABA-Problem
- DCAS
- Garbage Collection
- Pointer Tagging
- Hazard Pointers
- Transactional Memory
The ABA-Problem
The ABA Problem occurs when one activity fails to recognise that a single memory location was modified temporarily by another activity and therefore erroneusly assumes that the overall state has not been changed.
Everyone makes progress / non-blocking
wait-free
Everyone makes progress / blocking
starvation-free
someone makes progress / non-blocking
lock-free
someone makes progress / blocking
deadlock-free
Null-Eins-Prinzip
zero-one-prinicple
The zero-one-principle says that if a comparator network sorts any input sequence consisting of 0s and 1s, then it sorts all input sequences.
Peterson lock
only for 2 Threads
with flag (i want to enter in critical section) and victim (but I let you first)
forkjoin: Thread
RecursiveTask<V>
forkjoin: run
compute
forkjoin: ans field
return v from compute
forkjoin: start
fork
forkjoin: just join
join and expect returning an answer
forkjoin: run to handoptimize
compute to hand-optimize
forkjoin: don't have to topmost call to run
create a pool and call invoke
Probleme, die mit locks auftreten können, jedoch nicht mit Transactional Memory
- Convoying: thread holding a resource R is descheduled while other threads queue up waiting for R
- Priority Inversion: lower priority thread holds a resource R that a high priority thread is waiting on.
- Deadlocks: At least not with transactions itself, but still exists on the application level
Was muss Porgrammierer beachten (in Referenz basierten STMs, z.B. scala-stm), wenn er veränderbare geteilte Variablen benutzt?
- Enclosing in special variables: the shared variables has to be wrapped in special variables
- Only access from transactions: the shared variables should only be accessed from within transactions
Vorteil von HW Transactional Memory gegenüber SW Transactional Memory
- fast
- can have lower power consumption
Nachteil HW Transactional Memory gegenüber SW Transactional Memory
- cannot handle big transactions
- bonded resources
- less flexible
