FS21

1. Speedups

d)

For two processors, one with 1.5GGHz, 8 cores, other with 2.5GHz and 5 processors, figure out which is faster for $f=0.5$.

Compute the speedup of each processor against 1 core, disregarding the clockspeed.

$S_A=S_8=\frac{1}{0.5+\frac{1-0.5}{8}}=\frac{16}{9}$
$S_B=S_5=\frac{1}{0.5+\frac{1-0.5}{5}}=\frac{5}{3}$

Now multiple the speedups with the clock frequency → $S_A^{\prime }=S_A\cdot 1.5,S_B^{\prime }=S_B\cdot 2.5$.

Da $S_A^{\prime }=2.6<S^{\prime }B=4.16$, ist option B besser.
Das funktioniert, da $T_1$ für beide gleicher Work ist, und durch multiplizieren mit Clock-Speed kann man sie dann vergleichen.

2. Pipelining

b)

Totale time = first cycle * (N - 1) * max(time_stage).

d)

Massive Rechenfehler lol
→ compute alle vergleiche independently, schau was optimal ist.

3. Task Graphs

b)

Wieviele Prozessoren sind nötig?

NICHT Zählen wieviel nodes per Layer und dann max nehmen!

• man muss sich die einzelnen nodes pro layer anschauen und rechnen mit wievielen prozessoren alle schnell fertig sind

→ Layer 3 = 20, 30, 100, 60. Hier reichen 3, da 20 und 30 mit einem Prozessor fertig werden, bevor 100 fertig ist.

• note, 20 + 30 + 60 > 100, also geht es nicht mit 2.

Dann ist die Execution time → equal to critical Path. $T_{\infty }=T_3$ da wir mit mehr als 3 prozessoren keinen Speedup mehr kriegen

Deps

When drawing in the processing times, keep in mind the time at which node $n$ finishes is ${\max }_{d\in \text{parent}}{\text{dep}}_{\text{time}}+{\text{time}}_n$.

Check: wenn critical-path time < time mit split up → noch nicht ideal split gefunden!

c)

Knoten mit 100 aufteilen → 4 prozessoren mit critical path 300.
Knoten mit 80 autteilen → 3 prozessoren mit critical path 300

→ solution mit 80 ist ideal.

4. Wait/notify

thread.interrupt() called den interrupt. Mit thread.join() kann man dann warten bis sie fertig sind.
→ Check das extends Thread gegeben ist.

ExamPile

public Exam pollExam() {
	synchronized (this) {
		while (exams.size() == 0) wait();
		// why no notifyAll?
		return exams.poll();
	}
}

Das notify ist hier nicht sinnvoll, da es ja keinen anderen wartenden thread interessiert, wenn ein exam wieder da ist

• wir entfernen es ja hier direkt wieder → ergo nur wir brauchen es sehen

Note: in addExam() ist wohl ein notify → wir warten ja hier genau auf dieses Notify

Fork/Join Framework

Im Fork/Join Framework wird

• RecursiveTask<Double> verwendet um einen Wert zurückzugeben.
• RecursiveAction verwendet, wenn in-place alles geschieht

6. Locks

a)

Fair: A fair lock is acquired in the order it is requested.
“fair lock is acquired in the order the threads enter the doorway”

Deadlock-Free: A lock is deadlock free if at least one waiting thread acquires it eventually → system wide progress.

Starvation-Free: A lock is starvation free if a thread that requested the lock will eventually acquire it.

Lock-free: infinitely often some method call completes, i.e. the system as a whole makes progress even if individual threads starve.

Wait-free: Every method call by every thread completes in a finite number of its own steps, regardless of speed or failure of other threads.

b)

Starvation-free + deadlock-free ⇒ fair?

No, the filter-lock (or Dekker) for example is not fair.
“In a fair lock, threads cannot overtake each other. In a starvation free lock if threads A, B, C request the lock in that order, it is fine to give the lock to A, C, B (in that order). But this is not fair.”

c)

fair ⇒ starvation + deadlock-free?

False: simple lock that never returns. It’s fair, but it’s also not starvation free.

7. Linearizability

• Jede mit synchronized annotierte Methode hat einen Linearisierungspunkt. → TRUE

  • ja weil, mutex auf dem Monitor des Objekts. Totally ordered and never overlap.
    • → jeder beliebige Punkt in der Methode ist linearisierungspunkt
  • false, if we pass in non-synchronized objects into the method.
  • wait() in der Methode

• Sequentiell konsistentes Speichermodell schreibt vor, das alle Aktionen eines Threads in PO sichtbar werden → TRUE, def. SC

8. Barriers and Semaphores

a)

public synchronized void acquire() throws InterruptedException {
    while (counter <= 0) this.wait();
    counter--;
}

public synchronized void release() {
    counter++;
    this.notify();
}

Note notifyAll vs. notify here

• both would work, but since only one thread can reacquire the lock ⇒ only wake up one sleeping waiting on counter

b)

Learn that by heart!

9. MPI

b)

Eliminiert message-passing (MPI) alle möglichkeiten für deadlocks?

Nein → sie müssen immer noch einen weg haben zu synchronizen, um zu funktionieren (barriers, etc…). Wir können immer noch auf messages waiting mit send, recv

Note: ssend, not send (for synchronous send).

10. Mixer

b)

Explain ABA, using an example.

“Some atomic operations, such as CAS are used to compare a value of a register to an old value, assuming if they are equal that the state of a datastructure did not change in between. This assumption can be wrong, i.e., if we use a node pool and delete and later reuse a node.”

c)

Two techniques to prevent ABA.

”
Usually the ABA problem applies to pointers. We use some bits of the address to use as a counter, incrementing it every time we change the pointer.
This counter might overflow, and thus it makes the ABA problem only less likely.

Another technique is to have a seperate datastructure that contains all elements which have been changed.
”
or use DCAS, LL/SC, Hazard Pointers.

d)

TATAS Lock.

TATAS lock uses non-atomic (but still volatile! otherwise no guarantee we ever get updated value) read first, which avoids the more expensive atomic-reads while the lock is still taken.

void lock(AtomicBoolean flag) {
	while (flag.getAndSet(true)) {
		while (flag.get()) {} // <- non atomic, but volatile read
	}
}
 
void unlock(AtomicBoolean flag) {
	flag.getAndSet(false);
}

volatile read compiles to an ordinary mov → no fence, no lock prefix.
Hardware already guarantees Load-load and load-store ordering, the only thing the volatile does is constrain the JIT → forbids hoisting the load out of the loop:

while (true)  { while (flag) {} }
// can be JITted to
if (flag) { while (true) {} } // hoisting

This read is cheaper than atomic RMW.

TATAS does not prevent “release storm” → when false is written, all treads try to write (exponential backoff is needed).