\begin{slide}{Elimination Tree Stack}

Nir Shivat: Data Structures in the Multicore Age,
Communications ACM, 03/2011.

Plan:
\begin{itemize}
\item Ausgangspunkt: lock-free Stack
\item Elimination Array
\item Baum von Stacks
\item Elimination Array in jedem Knoten
\end{itemize}

\end{slide}

\begin{slide}{Semantik von nebenläufigen Stacks}

  \begin{itemize}
  \item 
Dyck-Sprache, gegeben durch Grammatik
mit Regeln
$S \to \epsilon, S \to \text{Push}(i) ~ S ~ \text{Pop}(i) ~ S$
\item
Datenstruktur ist (klassischer) Stack $\iff$ Spursprache
ist Präfixsprache der Dyck-Sprache
\item 
  Nebenläufigkeit: Operationen $\text{Push}_k(i),
  \text{Pop}_k(i)$

  Op. mit unterschiedlichem Index sind vertauschbar
\item nebenläufiger Stack: jede Spur ist vertauschungs-
  äquivalent zu Präfix eines Dyck-Wortes
\item
  später Abschwächung: betrachte nur ``ruhende'' Spuren
  (kein Thread blockiert eine Ressource)
  \end{itemize}

\end{slide}

\begin{slide}{Elimination Array}

  \begin{itemize}
  \item 
die Threads, die push/pop nicht ausführen können
(weil andere Threads zugreifen und deswegen CAS fehlschlägt),
\item
belegen während des Wartens eine zufällige
Position in einem Eliminiation Array.
\item
  wenn sich dort Threads mit push und pop treffen,
  sind diese Threads fertig und brauchen den Stack gar nicht.
  \end{itemize}

\end{slide}

\begin{slide}{Baum von Stacks}

  \begin{itemize}\parskip 0pt
  \item vollständiger binärer Baum
  \item jedes Blatt ist lock-free stack
  \item jeder innere Knoten enthält ein Bit,

    Bit 0/1 $=$ Richtung Links/Rechts
  \end{itemize}


Operationen:
\begin{itemize}\parskip 0pt
\item push: umschalten (CAS) und in die alte Richtung gehen
\item pop: umschalten (CAS) und in die neue Richtung gehen
\end{itemize}

Eigenschaften:\parskip 0pt
\begin{itemize}
\item Stacktiefen sind balanciert
\item Pop nach Push: aus gleichem Stack
\end{itemize}

\end{slide}


\begin{slide}{Baum mit Eliminatoren}

  \begin{itemize}
  \item 
    Flaschenhals ist das Bit in der Wurzel.
  \item 
    Eliminator-Array in jedem Knoten
    \begin{itemize}
    \item push/pop: sofort eliminieren
    \item push/push und pop/pop:

      auf Teilbäume verteilen,
      ohne Bit zu lesen/umzuschalten!
    \end{itemize}
  \end{itemize}
nebenläufige Stack-Semantik jetzt nur noch
für ruhende Spuren ($=$ wenn kein Thread
im Baum wartet)

Ü: Beispiel

\end{slide}
