%% Some useful variations of the document class
%%\documentclass[draft]{beamer}
%%\documentclass[handout]{beamer}
% silence hyperref warnings
\documentclass[hyperref={pdfpagelabels=false}]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[babel]{csquotes}
\usepackage{fancyvrb}
\usepackage{ccbeamer}
\usepackage{tikz}
\usepackage{minted}
\mode<presentation>{\usetheme{Copenhagen}}
\title{Software Transactional Memory}
\author{Marek~Kubica}
\institute{TU~München}
\date{19.07.2011}

%% get rid of navigation symbols
%\setbeamertemplate{navigation symbols}{}
\beamertemplatenavigationsymbolsempty

\usemintedstyle{trac}

\begin{document}

\frame{
  \titlepage
  \vfill
  \begin{center}
    \CcGroupBy{0.83}\\[2.5ex]
    {\tiny\CcNote{\CcLongnameBy}}
    \vspace*{-2.5ex}
  \end{center}
}

\AtBeginSection[]{
  \begin{frame}
    \frametitle{\insertsection}
    \tableofcontents[currentsection]
  \end{frame}
}

% define the logo after the title page
%\logo{\includegraphics[width=1.5cm]{tun}}

\usebackgroundtemplate{
  \begin{tikzpicture}
    \node [opacity=0.015]{\includegraphics[width=\paperwidth,height=\paperheight]{trollface}};
  \end{tikzpicture}
}

\begin{frame}{Problem?}
  \begin{block}{Concurrent writes in shared memory}
    \begin{itemize}
      \item T1 reads value
      \item T1 computes new value
      \item T2 reads value
      \item T1 writes new value
      \item T2 computes new value
      \item T2 \alert{overwrites} value of T1
    \end{itemize}
  \end{block}
\end{frame}

\usebackgroundtemplate{}

\begin{frame}[fragile]{How bad is it?}
  \begin{block}{An example program in C using pthreads}
    \begin{Verbatim}[gobble=6]
      $ ./broken 1 1000
      Number = 1000
      $ ./broken 2 1000
      Number = 997
      $ ./broken 15 1000
      Number = 2408
      $ ./broken 15 1000
      Number = 3228
    \end{Verbatim}
    In short: computation results are nearly random.
  \end{block}
\end{frame}

\begin{frame}{Solutions}
  \begin{block}{Typical real-world solutions}
    \begin{itemize}
      \item Locking (Mutexes, Semaphores, Spinlocks)
      \item Message Passing (MPI)
    \end{itemize}
  \end{block}
  \begin{block}{Problems}
    \begin{itemize}
      \item Deadlocks (Dining philosopher problem)
      \item Complex programs
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Software Transactional Memory}
  \begin{block}{Concept}
    \begin{itemize}
      \item All writes run in transactions
      \item If a value in the transaction was modified, the transaction is rolled back
      \item Transactions get repeated if they don't succeed
      \item Optimistic model, efficient with infrequent writes
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Fixed version}
  \begin{small}
    \inputminted{clojure}{fixed.clj}
  \end{small}
\end{frame}

\begin{frame}{Why does it work?}
  \begin{exampleblock}{Optimistic model}
    \begin{itemize}
      \item Runs computation, tries to write
      \item Succeeds or gets rolled back
      \item Efficient implementation: use data structures with O(1) rollback
      \item Increased concurrency
    \end{itemize}
  \end{exampleblock}
  \begin{alertblock}{Pessimistic model}
    \begin{itemize}
      \item Wait for lock, no computation
      \item Decreased concurrency
    \end{itemize}
  \end{alertblock}
\end{frame}

\begin{frame}{Drawbacks}
  \begin{alertblock}{Problems of STM}
    \begin{itemize}
      \item Transactions sometimes hard to get right (inconsistent state)
      \item Language support not always great
      \item Increased bandwidth usage due to retried transactions
    \end{itemize}
  \end{alertblock}
\end{frame}

\begin{frame}{Sources \& Questions}
  \begin{columns}[c]
    \column{0.7\textwidth}
      \includegraphics[height=8cm]{qr}
    \column{0.3\textwidth}
      \begin{block}{Source code}
        Minified C code on the left.
        Compile with \texttt{gcc -o broken broken.c -pthread}
      \end{block}
      \begin{block}{Questions?}
        And thank you for listening.
      \end{block}
  \end{columns}
\end{frame}

\end{document}