<commit_before>\documentclass[preprint]{sigplanconf}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathpartir}

\newcommand{\ra}{\rightarrow}
\newcommand{\gives}{\vdash}
\newcommand{\proves}{\vdash}
\newcommand{\GA}{\ |\ }
\newcommand{\kw}[1]{\textsf{#1}}
\newcommand{\ty}[1]{\textrm{#1}\ }
\newcommand{\bind}{\mbox{\ \scriptsize$>\!\!>\!=$\ }}
\newcommand{\letrec}[2]{\kw{letrec}\ #1\ \kw{in}\ #2}
\newcommand{\LET}[4]{\kw{let}_{#1}\ #2 = #3\ \kw{in}\ #4}

\begin{document}

\authorinfo{}{}{}
% yikes!
\title{Reagents: expressing and composing patterns of fine-grained concurrency}
\maketitle

\begin{abstract}
blah blah
\end{abstract}

\section{Introduction}

\hspace{\stretch{1}}\emph{Programs are what happens between cache
  misses}.\footnote{Folklore; origin unknown.}

\subsection*{The problem}

Ahmdahl's law tells us that sequential bottlenecks fundamentally limit
profit from parallelism~\cite{?}.  In practice, the effect is made
fatal by a silent killer: interprocessor communication, often in the
form of cache coherence.  When one thread waits on another, the
program pays the cost of lost parallelism \emph{and} an extra cache
miss.  Extra misses can easily add up to parallel \emph{slowdown},
more than negating the benefits of the remaining parallelism.  Cache,
as ever, is king.

The easy answer is: avoid communication.  In other words, parallelize
at a coarse grain, giving threads large chunks of independent work.
That strategy only goes so far.  Some work doesn't easily factor into
large chunks, or equal size chunks.  Fine-grained parallelism is
easier to find, and easier to sprinkle throughout existing sequential
code.  With increasing pressure to parallelize, fine-grained
parallelism will only become more common.

In the past two decades,\footnote{Herlihy/Wing, Mellor-Crummey/Scott}
an enormous literature has emerged 

\subsection*{Our contribution}

\section{Reagents}

\section{Semantics}

\section{Implemention}

\section{Performance}

\section{Related work}

\bibliographystyle{abbrvnat}

\end{document}

# Intro notes

What do we want to accomplish?

 - motivate libraries like j.u.c
 - downsides of such libraries
   - huge research & impl effort
   - not easily extensible
   - internal structure has repeated, but unabstracted patterns
 - our contribution
   - a new way of expressing scalable algorithms that
     - doesn't lose much performance 
     - allows composition<commit_msg>continued work on introduction<commit_after>\documentclass[preprint]{sigplanconf}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathpartir}

\newcommand{\ra}{\rightarrow}
\newcommand{\gives}{\vdash}
\newcommand{\proves}{\vdash}
\newcommand{\GA}{\ |\ }
\newcommand{\kw}[1]{\textsf{#1}}
\newcommand{\ty}[1]{\textrm{#1}\ }
\newcommand{\bind}{\mbox{\ \scriptsize$>\!\!>\!=$\ }}
\newcommand{\letrec}[2]{\kw{letrec}\ #1\ \kw{in}\ #2}
\newcommand{\LET}[4]{\kw{let}_{#1}\ #2 = #3\ \kw{in}\ #4}

\begin{document}

\authorinfo{}{}{}
% yikes!
\title{Reagents: expressing and composing patterns of fine-grained concurrency}
\maketitle

\begin{abstract}
blah blah
\end{abstract}

\section{Introduction}

\hspace{\stretch{1}}\emph{Programs are what happens between cache
  misses}.\footnote{Folklore; origin unknown.}

\subsection*{The problem}

Ahmdahl's law tells us that sequential bottlenecks fundamentally limit our
profit from parallelism~\cite{?}.  In practice, the effect is amplified by
another factor: interprocessor communication, often in the form of cache
coherence.  When one thread waits on another, the program pays the cost of
lost parallelism \emph{and} an extra cache miss.  The extra misses can easily
yield parallel \emph{slowdown}, more than negating the benefits of the
remaining parallelism.  

Cache, as ever, is king.

The easy answer is: avoid communication.  In other words, parallelize at a
coarse grain, giving threads large chunks of independent work.  But some work
doesn't easily factor into large chunks, or equal-size chunks.  Fine-grained
parallelism is easier to find, and easier to sprinkle throughout existing
sequential code.
%With increasing pressure to parallelize, fine-grained parallelism will only
%become more common.

Another answer is: communicate efficiently.  The past two
decades\footnote{Herlihy/Wing, Mellor-Crummey/Scott} have produced a sizable
collection of algorithms for synchronization, communication, and shared
storage which minimize the use of memory bandwidth and avoid unnecessary
waiting.  This research effort has led to industrial-strength
libraries---\texttt{java.util.concurrent} (JUC) the most prominent---offering
a wide range of concurrency primitives appropriate for fine-grained
parallelism.

Such libraries are an enormous undertaking---and one that must be repeated for
new platforms.  They tend to be conservative, implementing only those data
structures and primitives likely to fulfill common needs.  In addition, it is
generally not possible to safely combine the facilities of the library.  For
example, JUC provides queues, sets and maps, but not stacks or bags.  Its
queues come in both blocking and nonblocking forms, while its sets and maps
are nonblocking only.  Although the queues provide atomic (thread-safe)
dequeuing and sets provide atomic insertion, it is not possible to combine
these into a single atomic operation.  

In short, libraries for fine-grained concurrency are indispensable, but hard
to write, hard to extend by composition, and hard to tailor to the exact needs
of a particular user.

\subsection*{Our contribution}

We have developed a core library of \emph{composable} primitives for
fine-grained concurrency.

by no means a silver bullet.

why is this different from STM

\section{Reagents}
\label{sec:reagents}



\section{Semantics}
\label{sec:semantics}



\section{Implementation}
\label{sec:implementation}



\section{Performance}
\label{sec:performance}



\section{Related work}
\label{sec:related}



\bibliographystyle{abbrvnat}

\end{document}

# Intro notes

What do we want to accomplish?

 - motivate libraries like j.u.c
 - downsides of such libraries
   - huge research & impl effort
   - not easily extensible
   - internal structure has repeated, but unabstracted patterns
 - our contribution
   - a new way of expressing scalable algorithms that
     - doesn't lose much performance 
     - allows composition
{'fraction_non_alphanumeric': 0.09684507926542144, 'fraction_numerical': 0.00408099199497724, 'mean_word_length': 4.689285714285714, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3549149', 'n_tokens_mistral': 1873, 'n_tokens_neox': 1755, 'n_words': 707}