Parallele Programmierung - FS18
Begriffe für Prüfung Parallele Programmierung ETH
Begriffe für Prüfung Parallele Programmierung ETH
Kartei Details
| Karten | 26 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 20.08.2018 / 20.08.2018 |
| Weblink |
https://card2brain.ch/box/20180820_parallele_programmierung_fs18
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20180820_parallele_programmierung_fs18/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
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
