FS18

1. Speedup

c)

Amdahl’s: assumes constant problem size
Gustafson’s: assumes constant runtime with variable problem size

2. Pipelining

3.

b) einfach die paar ersten Schritte aufmalen und so extreme Variationen machen, um zu schauen was passiert → Latenz constant oder nicht.

3. Threads

4.

Nutze Helfervariable (boolean oder ähnliches) um irgendwie access zu gaten / ensure the correct order (write → read → write → read, etc…).

b)
Synchronized nötig. Dann ein Beispiel mit einem Bad Interleaving geben → mention that word!

• mention data race on variable x.
• Idealerwise in listen form mit line numbers.

5.

Hier einfach explizit dazuschreiben, diese sind richtig, “wenn threads sterben dürfen”…
Dann ist man auf der sicheren Seite.

4. Fork / Join

int l1 = length / 2;
int l2 = length - l1; // garantiert kompletten coverage!
 
new Task(start, l1);
new Task(start + l1, l2);

Sequential cutoff nicht vergessen! Einfach bei 1 wenn nichts anderes angegeben.

b) → Recommend doing approx 100-5000 basic operations in the sequential cutoff.

5. Linearizability

Linearizability

Linearizability Proof:

• Einfach für alle operation seine Sequential history exhibiten → linearisierungs punkte aufmalen.

Linearizability Disproof: Da linearizability composable ist! können wir es für die einzelnen Projektionen H | p und H | q beweisen!

• wenn eine Projektion nicht linearizable ist, ist es die History auch nicht.

Zeigen dass mit den ${\to }_{HB}$ relations es nicht gehen kann, i.e contradiction.

• hier, p.push(5) < p.push(3) < p.pop(5) und keine overlappings
  • nicht stack semantik legal.

Example: Happens before ordering gives us

• $\text{push(1)}{<}_H\text{push(2), push(3), pop: 3, pop: 1}$
• $\text{push(2), push(3)}{<}_H\text{pop:3, pop:1}$
• nur $\text{push(2)}||\text{push(3)}$ overlappen, i.e. incomparable!
• jede linearization $S$ of $H$ must have:
  • $S=\text{push(1)},\{\text{push(2), push(3)}\},\text{pop:3, pop:1}$
  • with push(2) and push(3) in some order
• so now there are 2 candidates remaining
  • check both, both contradict, i.e. illegal semantic, done.
    

Sequentially Consistent

Sequentially consistent Proof:

• give a sequential order of all operations (i.e. merge across threads)
  • it must respect PO within threads
  • here “all of A, then all of B”
• that is legal with the semantics of the object.

Sequentially Consistent

$H$ is SC iff there is a sequential history $S$ such that:

1. $S$ contains exactly the operations of $H$ (same invocations / responses)
2. $S$ respects PO of every thread
3. $S$ is legal (matches sequential specification of the object)

Sequentially consistent Disproof: (cycle argument)

• Suppose legal Sequential
• Then q.push(...) < q.pop() and …
• then show that a cycle is created.

Thread Synchronization

b) iii)

Das programm beendet sich immer → TRUE

Gibt alle Zahlen in [0, 99] aus → TRUE

• da hier getAndIncrement genutzt wird, speichert irgendein Thread immer jede intermediate value
  • es kann nichts übersprungen werden
  • würde nur passieren, wenn nochmal get() called wird!