HS23

2. Pipelines / SpeedUp

c)

Derive the equations from the Wser, Wpar

$f=\frac{W_{ser}}{W_{ser}+W_{par}}$.

Note that this is Gustafson’s. Here, the sequential runtime is $W_{ser}+p{W}_{par}$, because we need 1 processor to do all the work (of all processors) sequentially. The parallel runtime is just $W_{ser}+W_{par}$.

Then the speedup gives us:

$$S_p=\frac{W_{ser}+p{W}_{par}}{W_{ser}+W_{par}}=\frac{W_{ser}}{W_{ser}+W_{par}}+p\frac{W_{par}+W_{ser}-W_{par}}{W_{ser}+W_{par}}=f+p(1-f)$$

3

a)

Welche Annahmen?

Nicht das $\text{size}=2^i$ sondern das $\exists d\ge 32$ s.t. $\text{size}=d{2}^i$.
Wir hören ja bei ⇐ 32 auf, also kann der rest auch eine nicht power of 2 sein.

c)

Note: we use .invoke()!

Here, use var task = new ImageNegationFJ(image, ...);

• avoids having to write out the full type

Use ForkJoinPool fjp = new ForkJoinPool();

• don’t pass a parameter for the number of threads, so it automatically uses all of them

.invoke(task) is the right method!

e)

Each recursive call spawns 4 new threads.
$N=\frac{10\cdot 2^{10}}{2^4}=10\cdot 2^6=10\cdot 4^3$ threads maximum

Therefore:

$$4^i\le 10\cdot 4^3⟺i\le {\log }_4(10)+3⟺i\le 4$$

Thus the smallest possible CUTOFF is $4000/2^4=250$ to avoid a fifth division.

Note: Since each thread waits with .join() on all the others (and we do not reuse), all of them, not just the leaves are alive at the same time. This means that the sum of all levels needs to be $\le 10\cdot 4^3$.
We use the geometric sum, for the number of threads:

$$\sum _{i=0}^d{4}^i=\frac{4^{d+1}-4^0}{4-1}$$

then we need to find a $d$ s.t. the sum is $\le 10\cdot 4^3$. Just tabulate it.

5. Locks

a)

Starvation Freedom: if one or more threads are contending for a lock, all of them acquire it after a finite (but unbounded) amount of time.

• this holds under the assumption that all threads continue to take steps and the lock is always eventually released

Wait Freedom: All threads complete in a finite amount of it’s own steps, regardless of the behaviour of other threads.

• Do not include “bounded” here
• bounded wait-freedom is a strictly stronger property

The difference:

• starvation freedom is a blocking / dependent progress condition
  • a threads progress depends on other threads continuing to take steps
• wait-freedom is a non-blocking / independent condition
  • the thread completes in a finite number of it’s own steps, regardless of the speed / failure of other threads

b)

A SpinLock has many threads repeatedly execute something like getAndSet(true) on the same cache line. Since it’s a write (RMW), it must acquire that line in “exclusive/modified” state which invalidates the copy in every other core’s cache.

• each spin triggers coherence transaction → expensive
• This can lead to contention on the memory bus, which slows the system.

This can be solved with a TATAS lock with exponential backoff.

TAS spinning is the problem here → even if it’s already true, we still write to true → thus we acquire in exclusive:

boolean testAndSet() {
	boolean old = value;
	value = true;
	return old;
}

this is why TATAS is actually important → it prevents this write-storm

6. Linearizabiliity

b)

Is Java Code always Linearizable?

No, classic StoreLoad (permitted by x86, delays the write in the store-buffer) reordering problem with:

// T1
x = 1
System.out.println(y);
// or r1 = y
 
// T2
y = 1
System.out.println(x);
// or r2 = x

Could print 0, 0 which would violate linearizability. We have two objects. If they were linearizable, then by composability, the whole history should be.
In any history, one of the two writes must come first (PO), if it’s x = 1, then at least r2 = 1 must hold.

c)

Java Objects, synchronized, no parameters and no globals → always lienearizable?

Yes, because a single monitor serialises all operations and the release/acquire edges eliminate JMM visibility effects (synchronization actions). We can always choose lock acquisition as the linearization point.

7. ASP

b)

Objects with Consensus Numbers 1, 2, $\infty$ and proof of minimum:

1 Atomic Registers, with consensus number $1$

int decide(int proposed)
	return proposed;

this implementation must work for 1 thread, thus the consensus is at least 1

2 TAS proof is implementation of wait-free consensus for 2 threads

boolean decided = false;
int[] value = new int[2];
 
int decide(int proposed, int id) 
	value[id] = proposed;
	if (TAS(decided))
		return value[1 - id];
	return value[id];

3 CAS implementation for $\infty$ threads

int decided = NaN;
int decide(int proposed)
	CAS(decided, NaN, proposed);
	return decided;

9. Mixer

a)

flattened vs. closed nesting in TM:

• flattened nesting:
  • if an inner transaction aborts, the outer transaction aborts as well.
• closed
  • we can abort inner transactions individually and retry them.

b)

Compiler: reordering of independent instructions (JIT hoisting for example)
Hardware: OoO, ILP (StoreLoad reordering)

• it only forbids StoreStore, LoadLoad, LoadStore reordering

c)

Composability: ability to combine multiple transactions into a single larger transaction that still behaves atomically and correct
Isolation: the intermediate states of a transaction are not visible to other transactions until it’s complete

TM vs. Linearizability:

• atomicity: both ensure atomicity
• isolation: TM hides intermediate states, linearizability ensures everything appears instantaneous
• composability: TM supports composing transactions, Linearizability has the composability theorem, if every object history is linearizable, the composition of them must be.