Anki Deck Changes

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: w;X(,bh1:N

modified

Before

Front

Die multiplikative Gruppe modulo $n$ ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:

$n$ prim: $\mathbb{Z}_n^* = [n-1]$ und $\varphi(n) = n - 1$.
$n = p^2$, $p$ prim: $\varphi(n) = p(p-1) = n - \sqrt{n}$.

Back

Die multiplikative Gruppe modulo $n$ ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:

$n$ prim: $\mathbb{Z}_n^* = [n-1]$ und $\varphi(n) = n - 1$.
$n = p^2$, $p$ prim: $\varphi(n) = p(p-1) = n - \sqrt{n}$.

Beispiele: $\mathbb{Z}_9^* = \{1, 2, 4, 5, 7, 8\}$, $\varphi(9) = 6$. $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$, $\varphi(7) = 6$.

Konsequenz für den $p^2$-Fall beim Euklid-Test: $\frac{|\mathbb{Z}_n^*|}{n-1} \approx 1 - \frac{1}{\sqrt{n}}$, die Fehlerrate ist also fast $1$.

After

Front

Die multiplikative Gruppe modulo $n$ ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:

$n$ prim: $\mathbb{Z}_n^* = [n-1]$ und $\varphi(n) = n - 1$.
$n = p^2$, $p$ prim: $\varphi(n) = {{c4::p(p-1) = n - \sqrt{n} }}$.

Back

Die multiplikative Gruppe modulo $n$ ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::|\mathbb{Z}_n^*|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:

$n$ prim: $\mathbb{Z}_n^* = [n-1]$ und $\varphi(n) = n - 1$.
$n = p^2$, $p$ prim: $\varphi(n) = {{c4::p(p-1) = n - \sqrt{n} }}$.

Beispiele: $\mathbb{Z}_9^* = \{1, 2, 4, 5, 7, 8\}$, $\varphi(9) = 6$. $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$, $\varphi(7) = 6$.

Konsequenz für den $p^2$-Fall beim Euklid-Test: $\frac{|\mathbb{Z}_n^*|}{n-1} \approx 1 - \frac{1}{\sqrt{n}}$, die Fehlerrate ist also fast $1$.

Field-by-field Comparison

Field	Before	After
Text	Die <b>multiplikative Gruppe modulo $n$</b> ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::\|\mathbb{Z}_n^\|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:<ul><li>$n$ prim: $\mathbb{Z}_n^ = [n-1]$ und $\varphi(n) = {{c3::n - 1}}$.</li><li>$n = p^2$, $p$ prim: $\varphi(n) = {{c4::p(p-1) = n - \sqrt{n}}}$.</li></ul>	Die <b>multiplikative Gruppe modulo $n$</b> ist\[\mathbb{Z}_n^* := {{c1::\{a \in [n-1] \mid \mathrm{ggT}(a, n) = 1\} }}\]mit Multiplikation mod $n$. Sie ist eine Gruppe der Ordnung\[\varphi(n) := {{c2::\|\mathbb{Z}_n^\|}}\quad\text{(eulersche Phi-Funktion)}.\]Spezialfälle:<ul><li>$n$ prim: $\mathbb{Z}_n^ = [n-1]$ und $\varphi(n) = {{c3::n - 1}}$.</li><li>$n = p^2$, $p$ prim: $\varphi(n) = {{c4::p(p-1) = n - \sqrt{n} }}$.</li></ul>

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::3._Primzahltest

Note 2: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: CR2my^EB=I

modified

Before

Front

In the classic example with $x{=}1;\,y{=}1$ (Thread 1) and $a{=}y;\,b{=}x$ (Thread 2), every possible interleaving satisfies: $b \geq a$ is always true. This proof technique is called proof by exhaustion (full enumeration of interleavings).

Back

In the classic example with $x{=}1;\,y{=}1$ (Thread 1) and $a{=}y;\,b{=}x$ (Thread 2), every possible interleaving satisfies: $b \geq a$ is always true. This proof technique is called proof by exhaustion (full enumeration of interleavings).

Yet the assertion assert(b >= a) can still fail in practice: pure interleaving reasoning ignores memory reordering by the compiler and the hardware.

After

Front

Here, every possible interleaving satisfies: $b \geq a$ is always true.

Back

Here, every possible interleaving satisfies: $b \geq a$ is always true.

Yet the assertion assert(b >= a) can still fail in practice: pure interleaving reasoning ignores memory reordering by the compiler and the hardware.

Field-by-field Comparison

Field	Before	After
Text	~~In the classic example~~ with ~~$x{=}1;\,y{=}1$ (Thread 1) and $a{=}y;\,b{=}x$ (Thread 2)~~, every possible interleaving satisfies: {{c1::$b \geq a$ is always true}}. ~~This proof technique is called {{c2::proof by exhaustion (full enumeration of interleavings)}}.~~	<img src="paste-1925d81ffd7a50429c7275b05887e92bbb5006ee.jpg" width="427"><br><br>Here, every possible interleaving satisfies: {{c1::$b \geq a$ is always true}}.
Extra	Yet the assertion <code>assert(b >= a)</code> can still fail in practice: pure interleaving reasoning ignores <b>memory reordering</b> by the compiler and the hardware.	<img src="paste-f46eba5d409ddfa50ca5ce5c8024928be6a86d8e.jpg"><br><br>Yet the assertion <code>assert(b >= a)</code> can still fail in practice: pure interleaving reasoning ignores <b>memory reordering</b> by the compiler and the hardware.

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::1._Memory_Reordering

Note 3: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: T+YN#N>,$x

modified

Before

Front

Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons: pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally) and per-processor local caches (loads and stores become visible to other processors only after some delay).

Back

Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons: pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally) and per-processor local caches (loads and stores become visible to other processors only after some delay).

What exactly is guaranteed varies a lot across architectures (x86 vs ARM vs POWER vs Alpha …).

After

Front

Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons:

Pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally).
Per-processor local caches (loads and stores become visible to other processors only after some delay).

Back

Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons:

Pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally).
Per-processor local caches (loads and stores become visible to other processors only after some delay).

What exactly is guaranteed varies a lot across architectures (x86 vs ARM vs POWER vs Alpha …).

Field-by-field Comparison

Field	Before	After
Text	Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons: {{c1::pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally)}} ~~and~~ {{c2::per-processor local caches (loads and stores become visible to other processors only after some delay)}}.	Modern multiprocessors do not enforce a global ordering of all instructions for two main reasons: <br><ol><li>{{c1::Pipelining (processors execute parts of multiple instructions simultaneously and may reorder them internally)}}.</li><li>{{c2::Per-processor local caches (loads and stores become visible to other processors only after some delay)}}.</li></ol>

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::1._Memory_Reordering

Note 4: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: VKeMFH&qvc

modified

Before

Front

A proof by contradiction that assert(b >= a) cannot fail (assuming sequential program order) uses the relation happened before together with its property of transitivity.

Back

A proof by contradiction that assert(b >= a) cannot fail (assuming sequential program order) uses the relation happened before together with its property of transitivity.

Assume $b{<}a$; this forces $a{=}1$ and $b{=}0$, which produces a cyclic happened before chain - contradiction.

The proof relies on programs executing in program order; precisely this assumption breaks in practice due to reordering.

After

Front

A proof by contradiction that assert(b >= a) cannot fail (assuming sequential program order) uses the relation happened before together with its property of transitivity.

Back

A proof by contradiction that assert(b >= a) cannot fail (assuming sequential program order) uses the relation happened before together with its property of transitivity.

Assume $b<a$; this forces $a=1$ and $b=0$, which produces a cyclic happened before chain - contradiction.

The proof relies on programs executing in program order; precisely this assumption breaks in practice due to reordering.

Field-by-field Comparison

Field	Before	After
Text	A proof by contradiction that <code>assert(b >= a)</code> cannot fail (assuming sequential program order) uses the relation {{c1::<i>happened before</i>}} together with its property of {{c2::transitivity}}.	<img src="paste-cdd64ab0bfec31d2a02fc961d4e1421ca0b35599.jpg" width="349"><br><br>A proof by contradiction that <code>assert(b >= a)</code> cannot fail (assuming sequential program order) uses the relation {{c1::<i>happened before</i>}} together with its property of {{c2::transitivity}}.
Extra	Assume $b{<}a$; this forces $a~~{=}~~1$ and $b~~{=}~~0$, which produces a cyclic <i>happened before</i> chain - contradiction.<br><br>The proof relies on programs executing in program order; precisely this assumption breaks in practice due to reordering.	Assume $b<a$; this forces $a=1$ and $b=0$, which produces a cyclic <i>happened before</i> chain - contradiction.<br><br>The proof relies on programs executing in program order; precisely this assumption breaks in practice due to reordering.

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::1._Memory_Reordering

Note 5: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: |2|f7e7DL}

modified

Before

Front

Number of interleavings for 2 threads with $k$ statements each: {{c1::$\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) $}}.

Back

Number of interleavings for 2 threads with $k$ statements each: {{c1::$\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) $}}.

Derivation: the merged trace has length $2k$. Once we fix which $k$ of the $2k$ positions belong to thread 1, the interleaving is determined (sampling without replacement).

After

Front

Number of interleavings for 2 threads with $k$ statements each: {{c1::\[\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) \]}}

Back

Number of interleavings for 2 threads with $k$ statements each: {{c1::\[\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) \]}}

Derivation: the merged trace has length $2k$. Once we fix which $k$ of the $2k$ positions belong to thread 1, the interleaving is determined (sampling without replacement).

Field-by-field Comparison

Field	Before	After
Text	Number of interleavings for 2 threads with $k$ statements each: {{c1::$\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) $}}.	Number of interleavings for 2 threads with $k$ statements each: {{c1::\[\binom{2k}{k} = O\!\left(\dfrac{4^k}{\sqrt{2k} }\right) \]}}

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::1._Memory_Reordering

Note 6: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: ~d57MCW=Q9

modified

Before

Front

For the home-made rendezvous

void wait()  { x = 1; while(x==1); }
void arrive(){ x = 2; }

GCC with optimisations compiles the loop into an infinite loop (jmp test without ever reloading x).

Back

For the home-made rendezvous

void wait()  { x = 1; while(x==1); }
void arrive(){ x = 2; }

GCC with optimisations compiles the loop into an infinite loop (jmp test without ever reloading x).

Reason: the compiler hoists the read of x out of the loop (register hoisting) because, from its sequential view, x is not modified inside the loop. Writes from other threads are invisible to it.

Fix: volatile or a lock.

After

Front

For the home-made rendezvous

GCC with optimisations compiles the loop into an infinite loop (jmp test without ever reloading x).

Back

For the home-made rendezvous

GCC with optimisations compiles the loop into an infinite loop (jmp test without ever reloading x).

Reason: the compiler hoists the read of x out of the loop (register hoisting) because, from its sequential view, x is not modified inside the loop. Writes from other threads are invisible to it.

Fix: volatile or a lock.

Field-by-field Comparison

Field	Before	After
Text	For the home-made rendezvous <pre>~~void wait() { x = 1; while(x==1); } void arrive(){ x = 2; }~~</pre> GCC with optimisations compiles the loop into {{c1::an infinite loop (<code>jmp test</code> without ever reloading <code>x</code>)}}.	For the home-made rendezvous <pre><img src="paste-2349a9fad720b636b583c4c000aeaf8d4d9ff717.jpg"><br></pre> GCC with optimisations compiles the loop into {{c1::an infinite loop (<code>jmp test</code> without ever reloading <code>x</code>)}}.
Extra	Reason: the compiler hoists the read of <code>x</code> out of the loop (register hoisting) because, from its sequential view, <code>x</code> is not modified inside the loop. Writes from other threads are invisible to it.<br><br>Fix: <code>volatile</code> or a lock.	<img src="paste-a8cc80880ddd292ccc4c8ec8b899edede0f2ebb5.jpg"><br><br>Reason: the compiler hoists the read of <code>x</code> out of the loop (register hoisting) because, from its sequential view, <code>x</code> is not modified inside the loop. Writes from other threads are invisible to it.<br><br>Fix: <code>volatile</code> or a lock.

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::1._Memory_Reordering

Field	Before	After
Text	~~In the classic example~~ with ~~\(x{=}1;\,y{=}1\) (Thread 1) and \(a{=}y;\,b{=}x\) (Thread 2)~~, every possible interleaving satisfies: {{c1::\(b \geq a\) is always true}}. ~~This proof technique is called {{c2::proof by exhaustion (full enumeration of interleavings)}}.~~	<img src="paste-1925d81ffd7a50429c7275b05887e92bbb5006ee.jpg" width="427"><br><br>Here, every possible interleaving satisfies: {{c1::\(b \geq a\) is always true}}.
Extra	Yet the assertion <code>assert(b >= a)</code> can still fail in practice: pure interleaving reasoning ignores <b>memory reordering</b> by the compiler and the hardware.	<img src="paste-f46eba5d409ddfa50ca5ce5c8024928be6a86d8e.jpg"><br><br>Yet the assertion <code>assert(b >= a)</code> can still fail in practice: pure interleaving reasoning ignores <b>memory reordering</b> by the compiler and the hardware.