Parallele Programmierung - FS18
Begriffe für Prüfung Parallele Programmierung ETH
Begriffe für Prüfung Parallele Programmierung ETH
Set of flashcards Details
| Flashcards | 26 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | University |
| Created / Updated | 20.08.2018 / 20.08.2018 |
| Weblink |
https://card2brain.ch/box/20180820_parallele_programmierung_fs18
|
| Embed |
<iframe src="https://card2brain.ch/box/20180820_parallele_programmierung_fs18/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Create or copy sets of flashcards
With an upgrade you can create or copy an unlimited number of sets and use many more additional features.
Log in to see all the cards.
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
-
- 1 / 26
-
