candc.tex

\pdfminorversion=4
\documentclass[mathserif,xcolor={dvipsnames,table}]{beamer}
\mode<presentation>{\usetheme{Warsaw}\usecolortheme{crane}}
\usepackage{centernot}
\usepackage{graphicx}
\usepackage{transparent}
\usepackage{geometry}
\usepackage{tikz}
\usetikzlibrary{shadows}
\usepackage[utf8x]{inputenc}
%\usepackage[greek,english]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{ae}
%\usepackage[babel=true]{microtype}
\beamertemplatenavigationsymbolsempty
\usepackage{draftwatermark}
\SetWatermarkText{\textsf{\textbf{DRAFT}}}

\title{\textbf{Control and Concurrency}}
\date{}
\author{CS4803UWS at the\\
Georgia Institute of Technology
}

\begin{document}

{
\setbeamertemplate{background canvas}{%
\includegraphics[width=\paperwidth,height=\paperheight]{images/gt2.jpeg}
}%
\begin{frame}[plain]
\textcolor{white}{
\transparent{0.5}%
\colorbox{black}{\textbf{control and concurrency}}
}
\vspace{2.7in}
\\
\hfill\includegraphics[scale=.25]{images/cc-logo.pdf}
\includegraphics[scale=.25]{images/cc-new.pdf}
\includegraphics[scale=.25]{images/cc-share.pdf}
\textcolor{white}{
\\
\hfill \tiny{CC3.0 share-alike attribution}\\
}
\textcolor{white}{
\hfill \scriptsize{copyright \copyright\ 2013}\\
}
\end{frame}
}


\begin{frame}{Local concurrency}
Of two ``schools'' of concurrency, we will focus on the first:
\vfill
\begin{description}
\item[\textbf{Shared memory}]\hfill{Operate on a common store, establishing\\ \hfill mutual exclusion via control objects.}
\item[\textbf{Message passing}]\hfill{Operate on disjoint stores, exchanging\\ \hfill messages containing common data.}
\end{description}
\vfill
\textbf{NB:} Message passing is easily implemented
in terms of shared memory, requiring a simple class. The converse is untrue\footnote{In C, anyway.
In C++, we can do some operator overloading tricks---see Andrei Alexandrescu's ``Modern C++ Design'' (2001).}, since
memory operations are already built into the language.
\end{frame}

\begin{frame}{Necessities of fine-grained locking}
What hardware primitives are required for scalable locking\footnote{Material for this slide is due Lorenzo Alvisi's Fall 2004 CS380D ``Distributed Computing'' slides at UT-Austin.}?
\vfill
\begin{itemize}
\item \textit{Infinite consensus number}---For a concurrent object $X$ and
r/w registers $W$, the largest $n$ for which there exists
a consensus protocol $\{P_1\ldots P_n\}$ on {W, X}. The number is infinite if no
such $n$ exists. Herlihy taxonimized these:
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\rowcolors{1}{ForestGreen!20}{ForestGreen!5}
{\footnotesize
\begin{tabular}{|l|l|}
\hline
\textbf{Consensus number} & \textbf{Object} \\
\hline\hline
$1$ & Atomic r/w registers \\
\hline
$2$ & Test+set, Fetch+add \\
\hline
$2n - 2$ & n-register assignment \\
\hline
$\infty$ & Compare+swap/LLSC, FIFO+peek \\
\hline
\end{tabular}%
}
};
\end{tikzpicture}
\end{center}
\item \textit{Linearizability}---\textbf{FIXME}
\end{itemize}
\end{frame}

\begin{frame}
\huge FIXME about 6 more pages...
\end{frame}

\begin{frame}{Recommended reading}
\footnotesize{
\begin{itemize}
\item Edsger Dijkstra. ``Communicating Sequential Processes'' (1968).
\item Maurice Herlihy. ``Impossibility and universality results for wait-free synchronization'' (1988).
\item ``Volatile Considered Harmful.'' Linux kernel documentation.
\item Fraser and Harris. ``Concurrent Programming Without Locks'' (2007) and/or Fraser,
	``Practical Lock-Freedom'' (2003).
\item Ulrich Drepper. ``Futexes are Tricky'' (2011).
\item Desnoyers et al. ``User-Level Implementations of RCU'' (2012).
\item Hans Boehm. ``Miscompiling Programs with ``Benign'' Data Races'' (2011).
\item Michael Chynowe. ``Implementing Scalable Atomic Locks for Multicore Intel EM64T and IA32 Architectures'' (2012).
\item Kogan and Petrank, ``Wait-free queues with multiple enqueuers and dequeuers'' (2011).
\item Culler and Singh. \textit{Parallel Computer Architecture} (1999). 
\item \textit{Intel 64 and IA-32 Architectures Software Developer's Manuals}.
\end{itemize}
}
\end{frame}

\begin{frame}{Hack on!}
\begin{itemize}
%\item ``\selectlanguage{greek}τίς ἐστι τῶν γινομένων καὶ ῥεῦμα βίαιον ὁ αἰών· ἅμα
%τε γὰρ ὤφθη ἕκαστον, καὶ παρενήνεκται καὶ ἄλλο παραφέρεται, τὸ δὲ
%ἐνεχθήσεται.\latintext'' (``A river made up of the events which
\item ``A river made up of the events which
happen, a violent stream. As soon as a thing has been seen, it is
carried away. Another comes in its place; this too will be carried away.''\\ \hfill---Marcus Aurelius
\vfill
%\item \selectlanguage{frenchb}``Le temps est ce qui empêche que tout soit donné tout d'un coup.'' \latintext (
\item ``Time keeps everything from happening all at once.''\\ \hfill---Henri Bergson
\vfill
\item ``We shall come to see that time does not exist.''\\ \hfill---Julian Barbour
\end{itemize}
\end{frame}

\end{document}