Changes in / [fa6ca1a:34b6a7b6]


Ignore:
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/colby_parsons_MMAth/Makefile

    rfa6ca1a r34b6a7b6  
    101101        -${BibTeX} ${Build}/${basename $@}
    102102        # Some citations reference others so run again to resolve these citations
    103         ${LaTeX} ${basename $@}.tex
    104         -${BibTeX} ${Build}/${basename $@}
     103#       ${LaTeX} ${basename $@}.tex
     104#       -${BibTeX} ${Build}/${basename $@}
    105105        # Make index from *.aux entries and input index at end of document
    106106        makeglossaries -q -s ${Build}/${basename $@}.ist ${Build}/${basename $@}
    … …  
    115115        mkdir -p ${Build}
    116116
    117 %.tex : %.fig ${Build}
    118         fig2dev -L eepic $< > ${Build}/$@
     117# The following rules are currently unused but could be used later
     118# if we want to swap figures to be .pngs
     119# %.tex : %.fig ${Build}
     120#       fig2dev -L eepic $< > ${Build}/$@
    119121
    120 %.ps : %.fig | ${Build}
    121         fig2dev -L ps $< > ${Build}/$@
     122# %.ps : %.fig | ${Build}
     123#       fig2dev -L ps $< > ${Build}/$@
    122124
    123 %.pstex : %.fig | ${Build}
    124         fig2dev -L pstex $< > ${Build}/$@
    125         fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
     125# %.pstex : %.fig | ${Build}
     126#       fig2dev -L pstex $< > ${Build}/$@
     127#       fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    126128
    127 #-----------------------------------------------------------------------------------
    128 # Tools to generate png files
    129 # to create a png we create a pdf and convert it to png
    130 %.png : build/%.pstex figures/%.tex ${Build}
    131         echo ${basename $@}
    132         ${LaTeX} figures/${basename $@}.tex
    133         dvips build/${basename $@}.dvi -o build/${basename $@}.ps
    134         ps2pdf build/${basename $@}.ps
    135         convert -negate ${basename $@}.pdf $@
     129# #-----------------------------------------------------------------------------------
     130# # Tools to generate png files
     131# # to create a png we create a pdf and convert it to png
     132# %.png : build/%.pstex figures/%.tex ${Build}
     133#       echo ${basename $@}
     134#       ${LaTeX} figures/${basename $@}.tex
     135#       dvips build/${basename $@}.dvi -o build/${basename $@}.ps
     136#       ps2pdf build/${basename $@}.ps
     137#       convert -negate ${basename $@}.pdf $@
    136138
    137139# creating a pdf of a figure requires generating some latex that just includes the figure
    138 figures/%.tex: build/%.pstex ${Build}
    139         echo -n         "\documentclass[preview]{standalone}\n"         \
    140                         "\usepackage[T1]{fontenc}\n"                    \
    141                         "\usepackage[usenames]{color}\n"                \
    142                         "\usepackage{graphicx}\n"                       \
    143                         "\usepackage{listings}\n"                       \
    144                         "\usepackage{xspace}\n"                         \
    145                         "\input{style}\n"                               \
    146                         "\\\\begin{document}\n"                         \
    147                         "{\\\\resizebox{3\\\\textwidth}{!}{\input{${basename ${notdir $@}}.pstex_t}}}\n" \
    148                         "\end{document}" > $@
     140# figures/%.tex: build/%.pstex ${Build}
     141#       echo -n         "\documentclass[preview]{standalone}\n"         \
     142#                       "\usepackage[T1]{fontenc}\n"                    \
     143#                       "\usepackage[usenames]{color}\n"                \
     144#                       "\usepackage{graphicx}\n"                       \
     145#                       "\usepackage{listings}\n"                       \
     146#                       "\usepackage{xspace}\n"                         \
     147#                       "\input{style}\n"                               \
     148#                       "\\\\begin{document}\n"                         \
     149#                       "{\\\\resizebox{3\\\\textwidth}{!}{\input{${basename ${notdir $@}}.pstex_t}}}\n" \
     150#                       "\end{document}" > $@
    149151
    150152data/%: ;

  • doc/theses/colby_parsons_MMAth/glossary.tex

    rfa6ca1a r34b6a7b6  
    1 \makeglossaries
     1% % Main glossary entries -- definitions of relevant terminology
     2% \newglossaryentry{computer}
     3% {
     4% name=computer,
     5% description={A programmable machine that receives input data,
     6%                stores and manipulates the data, and provides
     7%                formatted output}
     8% }
    29
     10% % Nomenclature glossary entries -- New definitions, or unusual terminology
     11% \newglossary*{nomenclature}{Nomenclature}
     12% \newglossaryentry{dingledorf}
     13% {
     14% type=nomenclature,
     15% name=dingledorf,
     16% description={A person of supposed average intelligence who makes incredibly brainless misjudgments}
     17% }
    318
    4 % \longnewglossaryentry{uthread}
    5 % {name={user-level thread}}
     19% % List of Abbreviations (abbreviations type is built in to the glossaries-extra package)
     20% \newabbreviation{aaaaz}{AAAAZ}{American Association of Amateur Astronomers and Zoologists}
     21
     22% % List of Symbols
     23% \newglossary*{symbols}{List of Symbols}
     24% \newglossaryentry{rvec}
    625% {
    7 % Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system.
     26% name={$\mathbf{v}$},
     27% sort={label},
     28% type=symbols,
     29% description={Random vector: a location in n-dimensional Cartesian space, where each dimensional component is determined by a random process}
     30% }
    831
    9 % \textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
    10 % }
    11 % C_TODO: replace usages of these acronyms with \acrshort{name}
    12 \newacronym{tls}{TLS}{Thread Local Storage}
    13 \newacronym{api}{API}{Application Program Interface}
    14 \newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
    15 \newacronym{numa}{NUMA}{Non-Uniform Memory Access}
    16 \newacronym{rtti}{RTTI}{Run-Time Type Information}
    17 \newacronym{fcfs}{FCFS}{First Come First Served}
    18 \newacronym{toctou}{TOCTOU}{time-of-check to time-of-use}
     32% Examples from template above
     33
     34\newabbreviation{raii}{RAII}{Resource Acquisition Is Initialization}
     35\newabbreviation{rtti}{RTTI}{Run-Time Type Information}
     36\newabbreviation{fcfs}{FCFS}{First Come First Served}
     37\newabbreviation{toctou}{TOCTOU}{time-of-check to time-of-use}
     38
     39\newglossaryentry{actor}
     40{
     41name=actor,
     42description={A basic unit of an actor system that can store local state and send messages to other actors.}
     43}
     44
     45\newglossaryentry{impl_concurrency}
     46{
     47name=implicit concurrency,
     48description={A class of concurrency features that abstract away explicit thread synchronization and mutual exclusion.}
     49}
     50
     51\newglossaryentry{actor_model}
     52{
     53name=actor model,
     54description={A concurrent computation model, where tasks are broken into units of work that are distributed to actors in the form of messages.}
     55}
     56
     57\newglossaryentry{actor_system}
     58{
     59name=actor system,
     60description={An implementation of the actor model.}
     61}

  • doc/theses/colby_parsons_MMAth/local.bib

    rfa6ca1a r34b6a7b6  
    3131@phdthesis{Delisle22,
    3232author={{Delisle, Thierry}},
    33 title={The C∀ Scheduler},
     33title={The \textsf{C}$\mathbf{\forall}$ Scheduler},
    3434year={2022},
    3535publisher="UWSpace",
    … …  
    5050@mastersthesis{Beach21,
    5151author={{Beach, Andrew James}},
    52 title={Exception Handling in C∀},
     52title={Exception Handling in \textsf{C}$\mathbf{\forall}$},
    5353year={2021},
    5454publisher="UWSpace",

  • doc/theses/colby_parsons_MMAth/style/cfa-format.tex

    rfa6ca1a r34b6a7b6  
    99\definecolor{identifierCol}{HTML}{000000}
    1010
    11 % from https://gist.github.com/nikolajquorning/92bbbeef32e1dd80105c9bf2daceb89a
    12 \lstdefinelanguage{sml} {
    13   morekeywords= {
    14     EQUAL, GREATER, LESS, NONE, SOME, abstraction, abstype, and, andalso, array, as, before, bool, case, char, datatype, do, else, end, eqtype, exception, exn, false, fn, fun, functor, handle, if, in, include, infix, infixr, int, let, list, local, nil, nonfix, not, o, of, op, open, option, orelse, overload, print, raise, real, rec, ref, sharing, sig, signature, string, struct, structure, substring, then, true, type, unit, val, vector, where, while, with, withtype, word
    15   },
    16   morestring=[b]",
    17   morecomment=[s]{(*}{*)},
    18 }
    19 
    20 \lstdefinelanguage{D}{
    21   % Keywords
    22   morekeywords=[1]{
    23     abstract, alias, align, auto, body, break, cast, catch, class, const,
    24     continue, debug, delegate, delete, deprecated, do, else, enum, export,
    25     false, final, finally, for, foreach, foreach_reverse, function, goto, if,
    26     immutable, import, in, inout, interface, invariant, is, lazy, macro, mixin,
    27     module, new, nothrow, null, out, override, package, pragma, private,
    28     protected, public, pure, ref, return, shared, static, struct, super,
    29     switch, synchronized, template, this, throw, true, try, typedef, typeid,
    30     typeof, union, unittest, volatile, while, with
    31   },
    32   % Special identifiers, common functions
    33   morekeywords=[2]{enforce},
    34   % Ugly identifiers
    35   morekeywords=[3]{
    36     __DATE__, __EOF__, __FILE__, __LINE__, __TIMESTAMP__, __TIME__, __VENDOR__,
    37     __VERSION__, __ctfe, __gshared, __monitor, __thread, __vptr, _argptr,
    38     _arguments, _ctor, _dtor
    39   },
    40   % Basic types
    41   morekeywords=[4]{
    42      byte, ubyte, short, ushort, int, uint, long, ulong, cent, ucent, void,
    43      bool, bit, float, double, real, ushort, int, uint, long, ulong, float,
    44      char, wchar, dchar, string, wstring, dstring, ireal, ifloat, idouble,
    45      creal, cfloat, cdouble, size_t, ptrdiff_t, sizediff_t, equals_t, hash_t
    46   },
    47   % Strings
    48   morestring=[b]{"},
    49   morestring=[b]{'},
    50   morestring=[b]{`},
    51   % Comments
    52   comment=[l]{//},
    53   morecomment=[s]{/*}{*/},
    54   morecomment=[s][\color{blue}]{/**}{*/},
    55   morecomment=[n]{/+}{+/},
    56   morecomment=[n][\color{blue}]{/++}{+/},
    57   % Options
    58   sensitive=true
    59 }
    60 
    61 \lstdefinelanguage{rust}{
    62   % Keywords
    63   morekeywords=[1]{
    64     abstract, alignof, as, become, box,
    65     break, const, continue, crate, do,
    66     else, enum, extern, false, final,
    67     fn, for, if, impl, in,
    68     let, loop, macro, match, mod,
    69     move, mut, offsetof, override, priv,
    70     proc, pub, pure, ref, return,
    71     Self, self, sizeof, static, struct,
    72     super, trait, true,  type, typeof,
    73     unsafe, unsized, use, virtual, where,
    74     while, yield
    75   },
    76   % Strings
    77   morestring=[b]{"},
    78   % Comments
    79   comment=[l]{//},
    80   morecomment=[s]{/*}{*/},
    81   % Options
    82   sensitive=true
    83 }
    84 
    85 \lstdefinelanguage{pseudo}{
    86         morekeywords={string,uint,int,bool,float},%
    87         sensitive=true,%
    88         morecomment=[l]{//},%
    89         morecomment=[s]{/*}{*/},%
    90         morestring=[b]',%
    91         morestring=[b]",%
    92         morestring=[s]{`}{`},%
    93 }%
    94 
    95 \newcommand{\KWC}{K-W C\xspace}
    96 
    97 \lstdefinestyle{pseudoStyle}{
    98   escapeinside={@@},
    99   basicstyle=\linespread{0.9}\sf\footnotesize,          % reduce line spacing and use typewriter font
    100   keywordstyle=\bfseries\color{blue},
    101   keywordstyle=[2]\bfseries\color{Plum},
    102   commentstyle=\itshape\color{OliveGreen},                  % green and italic comments
    103   identifierstyle=\color{identifierCol},
    104   stringstyle=\sf\color{Mahogany},                                % use sanserif font
    105   mathescape=true,
    106   columns=fixed,
    107   aboveskip=4pt,                                  % spacing above/below code block
    108   belowskip=3pt,
    109   keepspaces=true,
    110   tabsize=4,
    111   % frame=lines,
    112   literate=,
    113   showlines=true,                                 % show blank lines at end of code
    114   showspaces=false,
    115   showstringspaces=false,
    116   escapechar=\$,
    117   xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    118   moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    119   % moredelim=* detects keywords, comments, strings, and other delimiters and applies their formatting
    120   % moredelim=** allows cumulative application
    121 }
    122 
    12311\lstdefinestyle{defaultStyle}{
    12412  escapeinside={@@},
    125   basicstyle=\linespread{0.9}\tt\footnotesize,          % reduce line spacing and use typewriter font
    126   keywordstyle=\bfseries\color{blue},
    127   keywordstyle=[2]\bfseries\color{Plum},
    128   commentstyle=\itshape\color{OliveGreen},                  % green and italic comments
    129   identifierstyle=\color{identifierCol},
    130   stringstyle=\sf\color{Mahogany},                                % use sanserif font
     13%   basicstyle=\linespread{0.9}\tt\footnotesize,                % reduce line spacing and use typewriter font
     14  basicstyle=\linespread{0.9}\sf,               % reduce line spacing and use typewriter
     15%   keywordstyle=\bfseries\color{blue},
     16%   keywordstyle=[2]\bfseries\color{Plum},
     17%   commentstyle=\itshape\color{OliveGreen},                % green and italic comments
     18%   identifierstyle=\color{identifierCol},
     19%   stringstyle=\sf\color{Mahogany},                              % use sanserif font
     20  stringstyle=\tt,                                % use sanserif font
    13121  mathescape=true,
    132   columns=fixed,
    133   aboveskip=4pt,                                  % spacing above/below code block
    134   belowskip=3pt,
     22%   columns=fixed,
     23  columns=fullflexible,
     24%   aboveskip=4pt,                                  % spacing above/below code block
     25%   belowskip=3pt,
    13526  keepspaces=true,
    13627  tabsize=4,
    … …  
    14940\lstdefinestyle{cfaStyle}{
    15041  escapeinside={@@},
    151   basicstyle=\linespread{0.9}\tt\footnotesize,          % reduce line spacing and use typewriter font
    152   keywordstyle=\bfseries\color{blue},
    153   keywordstyle=[2]\bfseries\color{Plum},
    154   commentstyle=\sf\itshape\color{OliveGreen},             % green and italic comments
    155   identifierstyle=\color{identifierCol},
    156   stringstyle=\sf\color{Mahogany},                                % use sanserif font
     42%  basicstyle=\linespread{0.9}\tt\footnotesize,         % reduce line spacing and use typewriter font
     43  basicstyle=\linespread{0.9}\sf,               % reduce line spacing and use typewriter font
     44%  keywordstyle=\bfseries\color{blue},
     45%  keywordstyle=[2]\bfseries\color{Plum},
     46%  commentstyle=\sf\itshape\color{OliveGreen},            % green and italic comments
     47%  identifierstyle=\color{identifierCol},
     48%  stringstyle=\sf\color{Mahogany},                               % use sanserif font
     49  stringstyle=\tt,                                % use sanserif font
    15750  mathescape=true,
    158   columns=fixed,
    159   aboveskip=4pt,                                  % spacing above/below code block
    160   belowskip=3pt,
     51%  columns=fixed,
     52  columns=fullflexible,
     53%  aboveskip=4pt,                                  % spacing above/below code block
     54%  belowskip=3pt,
    16155  keepspaces=true,
    16256  tabsize=4,
    … …  
    16660  showspaces=false,
    16761  showstringspaces=false,
     62  showlines=true,                                                       % show blank lines at end of code
    16863  escapechar=\$,
    16964  xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    17065  moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    171   morekeywords=[2]{accept, signal, signal_block, wait, waitfor},
     66  morekeywords=[2]{accept, signal, signal_block, wait, waitfor, waituntil},
     67  abovecaptionskip=5pt,
    17268}
    173 
    174 % \lstMakeShortInline[basewidth=0.5em,breaklines=true,basicstyle=\normalsize\ttfamily\color{basicCol}]@  % single-character for \lstinline
    175 % \lstMakeShortInline@
    17669
    17770\lstnewenvironment{ccode}[1][]{
    … …  
    18881    language = CFA,
    18982    style=cfaStyle,
    190     captionpos=b,
    191     #1
    192   }
    193 }{}
    194 
    195 \lstnewenvironment{pseudo}[1][]{
    196   \lstset{
    197     language = pseudo,
    198     style=pseudoStyle,
    19983    captionpos=b,
    20084    #1
    … …  
    229113}{}
    230114
    231 \lstnewenvironment{scalacode}[1][]{
    232   \lstset{
    233     language = scala,
    234     style=defaultStyle,
    235     captionpos=b,
    236     #1
    237   }
    238 }{}
    239 
    240 \lstnewenvironment{smlcode}[1][]{
    241   \lstset{
    242     language = sml,
    243     style=defaultStyle,
    244     captionpos=b,
    245     #1
    246   }
    247 }{}
    248 
    249 \lstnewenvironment{dcode}[1][]{
    250   \lstset{
    251     language = D,
    252     style=defaultStyle,
    253     captionpos=b,
    254     #1
    255   }
    256 }{}
    257 
    258 \lstnewenvironment{rustcode}[1][]{
    259   \lstset{
    260     language = rust,
    261     style=defaultStyle,
    262     captionpos=b,
    263     #1
    264   }
    265 }{}
    266 
    267115\lstnewenvironment{gocode}[1][]{
    268116  \lstset{

  • doc/theses/colby_parsons_MMAth/style/style.tex

    rfa6ca1a r34b6a7b6  
    1 \input{common}                                          % bespoke macros used in the document
    2 \input{cfa-format}
     1\input{common}
    32
    4 % \CFADefaultStyle
     3\lstdefinestyle{defaultStyle}{
     4    escapeinside={@@},
     5    %  basicstyle=\linespread{0.9}\tt\footnotesize,             % reduce line spacing and use typewriter font
     6      basicstyle=\linespread{0.9}\sf,           % reduce line spacing and use typewriter font
     7    %  keywordstyle=\bfseries\color{blue},
     8    %  keywordstyle=[2]\bfseries\color{Plum},
     9    %  commentstyle=\sf\itshape\color{OliveGreen},                % green and italic comments
     10    %  identifierstyle=\color{identifierCol},
     11    %  stringstyle=\sf\color{Mahogany},                           % use sanserif font
     12      stringstyle=\tt,                            % use sanserif font
     13      mathescape=true,
     14    %  columns=fixed,
     15      columns=fullflexible,
     16    %  aboveskip=4pt,                                  % spacing above/below code block
     17    %  belowskip=3pt,
     18      keepspaces=true,
     19      tabsize=4,
     20      % frame=lines,
     21      literate=,
     22      showlines=true,                                 % show blank lines at end of code
     23      showspaces=false,
     24      showstringspaces=false,
     25      showlines=true,                                                   % show blank lines at end of code
     26      escapechar=\$,
     27      xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
     28      moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
     29      morekeywords=[2]{accept, signal, signal_block, wait, waitfor, waituntil},
     30      abovecaptionskip=5pt,
     31}
    532
    6 % \lstset{
    7 % morekeywords=[2]{nomutex,mutex,thread,wait,wait_release,signal,signal_block,accept,monitor,suspend,resume,coroutine},
    8 % keywordstyle=[2]\color{blue},                         % second set of keywords for concurency
    9 % basicstyle=\linespread{0.9}\tt\small,         % reduce line spacing and use typewriter font
    10 % stringstyle=\sf\color{Mahogany},                      % use sanserif font
    11 % commentstyle=\itshape\color{OliveGreen},              % green and italic comments
    12 % }%
     33\lstdefinestyle{cfaStyle}{
     34  escapeinside={@@},
     35  basicstyle=\linespread{0.9}\sf,               % reduce line spacing and use typewriter font
     36  stringstyle=\tt,                                % use sanserif font
     37  mathescape=true,
     38  columns=fullflexible,
     39  keepspaces=true,
     40  tabsize=4,
     41  literate=,
     42  showlines=true,                                 % show blank lines at end of code
     43  showspaces=false,
     44  showstringspaces=false,
     45  showlines=true,                                                       % show blank lines at end of code
     46  escapechar=\$,
     47  xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
     48  moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
     49  morekeywords=[2]{accept, signal, signal_block, wait, waitfor, waituntil},
     50  abovecaptionskip=5pt,
     51}
     52
     53\lstnewenvironment{cfacode}[1][]{
     54  \lstset{
     55    language = CFA,
     56    style=cfaStyle,
     57    captionpos=b,
     58    #1
     59  }
     60}{}
     61
     62\lstnewenvironment{cppcode}[1][]{
     63  \lstset{
     64    language = c++,
     65    style=defaultStyle,
     66    captionpos=b,
     67    #1
     68  }
     69}{}
     70
     71\newcommand{\code}[1]{\lstinline[language=CFA,style=cfaStyle]{#1}}
     72\newcommand{\uC}{$\mu$\CC}
     73

  • doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex

    rfa6ca1a r34b6a7b6  
    11\chapter{Concurrency in \CFA}\label{s:cfa_concurrency}
    22
    3 The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis\cite{Delisle18}. In that work he introduced coroutines, user level threading, and monitors. Not listed in that work were the other concurrency features that were needed as building blocks, such as locks, futures, and condition variables which he also added to \CFA.
     3The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis\cite{Delisle18}.
     4In that work he introduced coroutines, user level threading, and monitors.
     5Not listed in that work were the other concurrency features that were needed as building blocks, such as locks, futures, and condition variables which he also added to \CFA.
    46
    57\section{Threading Model}\label{s:threading}
    6 \CFA has user level threading and supports a $M:N$ threading model where $M$ user threads are scheduled on $N$ cores, where both $M$ and $N$ can be explicitly set by the user. Cores are used by a program by creating instances of a \code{processor} struct. User threads types are defined using the \code{thread} keyword, in the place where a \code{struct} keyword is typically used. For each thread type a corresponding main must be defined, which is where the thread starts running once it is created. Listing~\ref{l:cfa_thd_init} shows an example of processor and thread creation. When processors are added, they are added alongside the existing processor given to each program. Thus if you want $N$ processors you need to allocate $N-1$. To join a thread the thread must be deallocated, either deleted if it is allocated on the heap, or go out of scope if stack allocated. The thread performing the deallocation will wait for the thread being deallocated to terminate before the deallocation can occur. A thread terminates by returning from the main routine where it starts.
     8\CFA has user level threading and supports a $M:N$ threading model where $M$ user threads are scheduled on $N$ cores, where both $M$ and $N$ can be explicitly set by the user.
     9Cores are used by a program by creating instances of a \code{processor} struct.
     10User threads types are defined using the \code{thread} keyword, in the place where a \code{struct} keyword is typically used.
     11For each thread type a corresponding main must be defined, which is where the thread starts running once it is created.
     12Listing~\ref{l:cfa_thd_init} shows an example of processor and thread creation.
     13When processors are added, they are added alongside the existing processor given to each program.
     14Thus if you want $N$ processors you need to allocate $N-1$.
     15To join a thread the thread must be deallocated, either deleted if it is allocated on the heap, or go out of scope if stack allocated.
     16The thread performing the deallocation will wait for the thread being deallocated to terminate before the deallocation can occur.
     17A thread terminates by returning from the main routine where it starts.
    718
    819\begin{cfacode}[tabsize=3,caption={\CFA user thread and processor creation},label={l:cfa_thd_init}]

  • doc/theses/colby_parsons_MMAth/text/CFA_intro.tex

    rfa6ca1a r34b6a7b6  
    66
    77\section{Overview}
    8 The following serves as an introduction to \CFA. \CFA is a layer over C, is transpiled to C and is largely considered to be an extension of C. Beyond C, it adds productivity features, libraries, a type system, and many other language constructions. However, \CFA stays true to C as a language, with most code revolving around \code{struct}'s and routines, and respects the same rules as C. \CFA is not object oriented as it has no notion of \code{this} and no classes or methods, but supports some object oriented adjacent ideas including costructors, destructors, and limited inheritance. \CFA is rich with interesting features, but a subset that is pertinent to this work will be discussed.
     8The following serves as an introduction to \CFA.
     9\CFA is a layer over C, is transpiled to C and is largely considered to be an extension of C.
     10Beyond C, it adds productivity features, libraries, a type system, and many other language constructions.
     11However, \CFA stays true to C as a language, with most code revolving around \code{struct}'s and routines, and respects the same rules as C.
     12\CFA is not object oriented as it has no notion of \code{this} and no classes or methods, but supports some object oriented adjacent ideas including costructors, destructors, and limited inheritance.
     13\CFA is rich with interesting features, but a subset that is pertinent to this work will be discussed.
    914
    1015\section{References}
    11 References in \CFA are similar to references in \CC, however in \CFA references are rebindable, and support multi-level referencing. References in \CFA are a layer of syntactic sugar over pointers to reduce the number of ref/deref operations needed with pointer usage. Some examples of references in \CFA are shown in Listing~\ref{l:cfa_ref}. Another related item to note is that the \CFA equivalent of \CC's \code{nullptr} is \code{0p}.
    12 
    13 \begin{cfacode}[tabsize=3,caption={Example of \CFA references},label={l:cfa_ref}]
     16References in \CFA are similar to references in \CC, however in \CFA references are rebindable, and support multi-level referencing.
     17References in \CFA are a layer of syntactic sugar over pointers to reduce the number of ref/deref operations needed with pointer usage.
     18Some examples of references in \CFA are shown in Listing~\ref{l:cfa_ref}.
     19Another related item to note is that the \CFA equivalent of \CC's \code{nullptr} is \code{0p}.
     20
     21\begin{cfacode}[caption={Example of \CFA references},label={l:cfa_ref}]
    1422int i = 2;
    1523int & ref_i = i;            // declare ref to i
    … …  
    2937
    3038\section{Overloading}
    31 In \CFA routines can be overloaded on parameter type, number of parameters, and return type. Variables can also be overloaded on type, meaning that two variables can have the same name so long as they have different types. The variables will be disambiguated via type, sometimes requiring a cast. The code snippet in Listing~\ref{l:cfa_overload} contains examples of overloading.
    32 
    33 
    34 \begin{cfacode}[tabsize=3,caption={Example of \CFA function overloading},label={l:cfa_overload}]
     39In \CFA routines can be overloaded on parameter type, number of parameters, and return type.
     40Variables can also be overloaded on type, meaning that two variables can have the same name so long as they have different types.
     41The variables will be disambiguated via type, sometimes requiring a cast.
     42The code snippet in Listing~\ref{l:cfa_overload} contains examples of overloading.
     43
     44
     45\begin{cfacode}[caption={Example of \CFA function overloading},label={l:cfa_overload}]
    3546int foo() { printf("A\n");  return 0;}
    3647int foo( int bar ) { printf("B\n"); return 1; }
    … …  
    5061
    5162\section{With Statement}
    52 The with statement is a tool for exposing members of aggregate types within a scope in \CFA. It allows users to use fields of aggregate types without using their fully qualified name. This feature is also implemented in Pascal. It can exist as a stand-alone statement or it can be used on routines to expose fields in the body of the routine. An example is shown in Listing~\ref{l:cfa_with}.
     63The with statement is a tool for exposing members of aggregate types within a scope in \CFA.
     64It allows users to use fields of aggregate types without using their fully qualified name.
     65This feature is also implemented in Pascal.
     66It can exist as a stand-alone statement or it can be used on routines to expose fields in the body of the routine.
     67An example is shown in Listing~\ref{l:cfa_with}.
    5368
    5469
    … …  
    89104
    90105\section{Operators}
    91 Operators can be overloaded in \CFA with operator routines. Operators in \CFA are named using the operator symbol and '?' to respresent operands.
     106Operators can be overloaded in \CFA with operator routines.
     107Operators in \CFA are named using the operator symbol and '?' to respresent operands.
    92108An example is shown in Listing~\ref{l:cfa_operate}.
    93109
    … …  
    113129
    114130\section{Constructors and Destructors}
    115 Constructors and destructors in \CFA are two special operator routines that are used for creation and destruction of objects. The default constructor and destructor for a type are called implicitly upon creation and deletion respectively if they are defined. An example is shown in Listing~\ref{l:cfa_ctor}.
     131Constructors and destructors in \CFA are two special operator routines that are used for creation and destruction of objects.
     132The default constructor and destructor for a type are called implicitly upon creation and deletion respectively if they are defined.
     133An example is shown in Listing~\ref{l:cfa_ctor}.
    116134
    117135
    … …  
    143161
    144162\section{Polymorphism}\label{s:poly}
    145 C does not natively support polymorphism, and requires users to implement polymorphism themselves if they want to use it. \CFA extends C with two styles of polymorphism that it supports, parametric polymorphism and nominal inheritance.
     163C does not natively support polymorphism, and requires users to implement polymorphism themselves if they want to use it.
     164\CFA extends C with two styles of polymorphism that it supports, parametric polymorphism and nominal inheritance.
    146165
    147166\subsection{Parametric Polymorphism}
    148 \CFA provides parametric polymorphism in the form of \code{forall}, and \code{trait}s. A \code{forall} takes in a set of types and a list of constraints. The declarations that follow the \code{forall} are parameterized over the types listed that satisfy the constraints. Sometimes the list of constraints can be long, which is where a \code{trait} can be used. A \code{trait} is a collection of constraints that is given a name and can be reused in foralls. An example of the usage of parametric polymorphism in \CFA is shown in Listing~\ref{l:cfa_poly}.
     167\CFA provides parametric polymorphism in the form of \code{forall}, and \code{trait}s.
     168A \code{forall} takes in a set of types and a list of constraints.
     169The declarations that follow the \code{forall} are parameterized over the types listed that satisfy the constraints.
     170Sometimes the list of constraints can be long, which is where a \code{trait} can be used.
     171A \code{trait} is a collection of constraints that is given a name and can be reused in foralls.
     172An example of the usage of parametric polymorphism in \CFA is shown in Listing~\ref{l:cfa_poly}.
    149173
    150174\begin{cfacode}[tabsize=3,caption={Example of \CFA polymorphism},label={l:cfa_poly}]
    … …  
    194218
    195219\subsection{Inheritance}
    196 Inheritance in \CFA copies its style from Plan-9 C nominal inheritance. In \CFA structs can \code{inline} another struct type to gain its fields and to be able to be passed to routines that require a parameter of the inlined type. An example of \CFA inheritance is shown in Listing~\ref{l:cfa_inherit}.
     220Inheritance in \CFA copies its style from Plan-9 C nominal inheritance.
     221In \CFA structs can \code{inline} another struct type to gain its fields and to be able to be passed to routines that require a parameter of the inlined type.
     222An example of \CFA inheritance is shown in Listing~\ref{l:cfa_inherit}.
    197223
    198224\begin{cfacode}[tabsize=3,caption={Example of \CFA inheritance},label={l:cfa_inherit}]

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    rfa6ca1a r34b6a7b6  
    66
    77% C_TODO: add citations throughout chapter
    8 Actors are a concurrent feature that abstracts threading away from a user, and instead provides \newterm{actors} and \newterm{messages} as building blocks for concurrency. Actors are another message passing concurrency feature, similar to channels, but with more abstraction. Actors enter the realm of what is called \newterm{implicit concurrency}, where programmers can write concurrent code without having to worry about explicit thread synchronization and mutual exclusion. The study of actors can be broken into two concepts, the \newterm{actor model}, which describes the model of computation and the \newterm{actor system}, which refers to the implementation of the model in practice. Before discussing \CFA's actor system in detail, it is important to first describe the actor model, and the classic approach to implementing an actor system.
     8Actors are a concurrent feature that abstracts threading away from a user, and instead provides \gls{actor}s and messages as building blocks for concurrency.
     9Actors are another message passing concurrency feature, similar to channels, but with more abstraction.
     10Actors enter the realm of what is called \gls{impl_concurrency}, where programmers can write concurrent code without having to worry about explicit thread synchronization and mutual exclusion.
     11The study of actors can be broken into two concepts, the \gls{actor_model}, which describes the model of computation and the \gls{actor_system}, which refers to the implementation of the model in practice.
     12Before discussing \CFA's actor system in detail, it is important to first describe the actor model, and the classic approach to implementing an actor system.
    913
    1014\section{The Actor Model}
    11 The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{Hewitt73}. Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors. The actor model is an implicit model of concurrency. As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation. Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors typically operate on local state.
     15The actor model is a paradigm of concurrent computation, where tasks are broken into units of work that are distributed to actors in the form of messages \cite{Hewitt73}.
     16Actors execute asynchronously upon receiving a message and can modify their own state, make decisions, spawn more actors, and send messages to other actors.
     17The actor model is an implicit model of concurrency.
     18As such, one strength of the actor model is that it abstracts away many considerations that are needed in other paradigms of concurrent computation.
     19Mutual exclusion, and locking are rarely relevant concepts to users of an actor model, as actors typically operate on local state.
    1220
    1321\section{Classic Actor System}
    14 An implementation of the actor model with a community of actors is called an actor system. Actor systems largely follow the actor model, but differ in some ways. While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent. Another way an actor system varies from the model is that actors are often allowed to access non-local state. When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
     22An implementation of the actor model with a community of actors is called an actor system.
     23Actor systems largely follow the actor model, but differ in some ways.
     24While the definition of the actor model provides no restrictions on message ordering, actor systems tend to guarantee that messages sent from a given actor $i$ to actor $j$ will arrive at actor $j$ in the order they were sent.
     25Another way an actor system varies from the model is that actors are often allowed to access non-local state.
     26When this occurs it can complicate the implementation as this will break any mutual exclusion guarantees given by accessing only local state.
    1527
    1628\begin{figure}
    … …  
    2335
    2436\section{\CFA Actors}
    25 Actor systems \cite{} have often been implemented as an actor-centric system. As such they are constructed as a set of actors that are scheduled and run on some underlying threads. Each actor has their own queue for receiving messages, sometimes called a mailbox. When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread to run their unit of work. This approach can be implemented with a global queue of actors, but is often implemented as each worker thread owning a queue of actors. This is known as sharding the actor queue, which is done to decrease contention across worker threads. A diagram of an actor-centric system with a sharded actor queue is shown in Figure \ref{f:standard_actor}.
     37Actor systems \cite{} have often been implemented as an actor-centric system.
     38As such they are constructed as a set of actors that are scheduled and run on some underlying threads.
     39Each actor has their own queue for receiving messages, sometimes called a mailbox.
     40When they receive messages in their mailbox, actors are moved from idle to ready queues and then scheduled on a thread to run their unit of work.
     41This approach can be implemented with a global queue of actors, but is often implemented as each worker thread owning a queue of actors.
     42This is known as sharding the actor queue, which is done to decrease contention across worker threads.
     43A diagram of an actor-centric system with a sharded actor queue is shown in Figure \ref{f:standard_actor}.
    2644
    2745% cite parallel theatre and our paper
    28 The actor system in \CFA is instead message-centric, an uses what is called an inverted actor system \cite{}. In this inverted actor system instead of each worker thread owning a queue of actors, they each own a queue of messages. This system is called inverted since in this scheme, actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor. Since multiple actors belong to each message queue, messages to each actor are interleaved in the queue. In this scheme work is consumed from their queue and executed by underlying threads. In High-Performance Extended Actors \cite{} this inverted model is taken a step further and the message queues are sharded, so that each worker now instead owns a set of queues. A diagram of an inverted actor scheme with a sharded message queue is shown in Figure \ref{f:inverted_actor}. The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
     46The actor system in \CFA is instead message-centric, an uses what is called an inverted actor system \cite{}.
     47In this inverted actor system instead of each worker thread owning a queue of actors, they each own a queue of messages.
     48This system is called inverted since in this scheme, actors belong to a message queue, whereas in the classic approach a message queue belongs to each actor.
     49Since multiple actors belong to each message queue, messages to each actor are interleaved in the queue.
     50In this scheme work is consumed from their queue and executed by underlying threads.
     51In High-Performance Extended Actors \cite{} this inverted model is taken a step further and the message queues are sharded, so that each worker now instead owns a set of queues.
     52A diagram of an inverted actor scheme with a sharded message queue is shown in Figure \ref{f:inverted_actor}.
     53The arrows from the message queues to the actors in the diagram indicate interleaved messages addressed to each actor.
    2954
    3055The actor system in \CFA builds on top of the architecture laid out in High-Performance Extended Actors \cite{} and adds the following contributions:
    … …  
    3257\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
    3358\item
    34 Provides insight into the impact of envelope allocation in actor systems. In all actor systems dynamic allocation is needed to ensure that the lifetime of a unit of work persists from its creation until the unit of work is executed. This allocation is often called an envelope as it "packages" the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields for a list. This dynamic allocation occurs once per message sent. This is a large source of contention on the memory allocator since all these allocations occur concurrently. A novel data structure is used to consolidate allocations to improve performance by minimizing contention on the allocator.
    35 
    36 \item
    37 Introduces work stealing in the inverted actor system. Work stealing in actor-centric systems tends to involve stealing one or more actors. In the inverted system the notion of stealing queues is introduced. The queue stealing is implemented such that the act of stealing work does not contend with non-stealing actors that are saturated with work.
     59Provides insight into the impact of envelope allocation in actor systems.
     60In all actor systems dynamic allocation is needed to ensure that the lifetime of a unit of work persists from its creation until the unit of work is executed.
     61This allocation is often called an envelope as it "packages" the information needed to run the unit of work, alongside any other information needed to send the unit of work, such as an actor's address or link fields for a list.
     62This dynamic allocation occurs once per message sent.
     63This is a large source of contention on the memory allocator since all these allocations occur concurrently.
     64A novel data structure is used to consolidate allocations to improve performance by minimizing contention on the allocator.
     65
     66\item
     67Introduces work stealing in the inverted actor system.
     68Work stealing in actor-centric systems tends to involve stealing one or more actors.
     69In the inverted system the notion of stealing queues is introduced.
     70The queue stealing is implemented such that the act of stealing work does not contend with non-stealing actors that are saturated with work.
    3871
    3972\item
    … …  
    4881
    4982\section{\CFA Actor Syntax}
    50 \CFA is not an object oriented language and it does not have run-time type information (RTTI). As such all message sends and receives between actors occur using exact type matching. To use actors in \CFA you must \code{\#include <actors.hfa>}. To create an actor type one must define a struct which inherits from the base \code{actor} struct via the \code{inline} keyword. This is the Plan-9 C-style nominal inheritance discussed in Section \ref{s:poly}. Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
     83\CFA is not an object oriented language and it does not have run-time type information (RTTI).
     84As such all message sends and receives between actors occur using exact type matching.
     85To use actors in \CFA you must \code{\#include <actors.hfa>}.
     86To create an actor type one must define a struct which inherits from the base \code{actor} struct via the \code{inline} keyword.
     87This is the Plan-9 C-style nominal inheritance discussed in Section \ref{s:poly}.
     88Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
    5189
    5290\begin{cfacode}
    … …  
    82120\end{cfacode}
    83121
    84 The above code is a simple actor program in \CFA. There is one derived actor type and one derived message type. A single message containing a string is sent from the program main to an actor. Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}. To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
     122The above code is a simple actor program in \CFA.
     123There is one derived actor type and one derived message type.
     124A single message containing a string is sent from the program main to an actor.
     125Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}.
     126To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
    85127\begin{cfacode}
    86128Allocation receive( derived_actor & receiver, derived_msg & msg )
    87129\end{cfacode}
    88 Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively. The return value of \code{receive} must be a value from the \code{Allocation} enum:
     130Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively.
     131The return value of \code{receive} must be a value from the \code{Allocation} enum:
    89132\begin{cfacode}
    90133enum Allocation { Nodelete, Delete, Destroy, Finished };
    91134\end{cfacode}
    92 The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed. In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action. For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor. Message state can be updated via a call to:
     135The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed.
     136In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action.
     137For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor.
     138Message state can be updated via a call to:
    93139\begin{cfacode}
    94140void set_allocation( message & this, Allocation state )
    … …  
    99145\begin{description}
    100146\item[\LstBasicStyle{\textbf{Nodelete}}]
    101 tells the executor that no action is to be taken with regard to a message or actor with this status. This indicates that the actor will receive future behaviours, and that a message may be reused.
     147tells the executor that no action is to be taken with regard to a message or actor with this status.
     148This indicates that the actor will receive future behaviours, and that a message may be reused.
    102149
    103150\item[\LstBasicStyle{\textbf{Delete}}]
    104 tells the executor to call the appropriate destructor and then deallocate the respective actor or message. This status is typically used with dynamically allocated actors and messages.
     151tells the executor to call the appropriate destructor and then deallocate the respective actor or message.
     152This status is typically used with dynamically allocated actors and messages.
    105153
    106154\item[\LstBasicStyle{\textbf{Destroy}}]
    107 tells the executor to call the object's destructor. The executor will not deallocate the respective actor or message. This status is typically used with dynamically allocated actors and messages whose storage will be reused.
     155tells the executor to call the object's destructor.
     156The executor will not deallocate the respective actor or message.
     157This status is typically used with dynamically allocated actors and messages whose storage will be reused.
    108158
    109159\item[\LstBasicStyle{\textbf{Finished}}]
    110 tells the executor to mark the respective actor as being finished executing. In this case the executor will not call any destructors or deallocate any objects. This status is used when the actors are stack allocated or if the user wants to manage deallocation of actors themselves. In the case of messages, \code{Finished} is no different than \code{Nodelete} since the executor does not need to track if messages are done work. As such \code{Finished} is not supported for messages and is used internally by the executor to track if messages have been used for debugging purposes.
     160tells the executor to mark the respective actor as being finished executing.
     161In this case the executor will not call any destructors or deallocate any objects.
     162This status is used when the actors are stack allocated or if the user wants to manage deallocation of actors themselves.
     163In the case of messages, \code{Finished} is no different than \code{Nodelete} since the executor does not need to track if messages are done work.
     164As such \code{Finished} is not supported for messages and is used internally by the executor to track if messages have been used for debugging purposes.
    111165\end{description}
    112166
    113 For the actor system to gracefully terminate, all actors must have returned a status other than \code{Nodelete}. Once an actor's allocation status has been set to something other than \code{Nodelete}, it is erroneous for the actor to receive a message. Similarly messages cannot be safely reused after their related behaviour if their status is not \code{Nodelete}. Note, it is safe to construct a message with a non-\code{Nodelete} status since the executor will only take the appropriate allocation action after a message has been delivered.
    114 
    115 The calls to \code{start_actor_system}, and \code{stop_actor_system} mark the start and end of a \CFA actor system. The call to \code{start_actor_system} sets up the executor and worker threads for the actor system. \code{start_actor_system} has three overloaded signatures which all start the actor system, but vary in executor configuration:
     167For the actor system to gracefully terminate, all actors must have returned a status other than \code{Nodelete}.
     168Once an actor's allocation status has been set to something other than \code{Nodelete}, it is erroneous for the actor to receive a message.
     169Similarly messages cannot be safely reused after their related behaviour if their status is not \code{Nodelete}.
     170Note, it is safe to construct a message with a non-\code{Nodelete} status since the executor will only take the appropriate allocation action after a message has been delivered.
     171
     172The calls to \code{start_actor_system}, and \code{stop_actor_system} mark the start and end of a \CFA actor system.
     173The call to \code{start_actor_system} sets up the executor and worker threads for the actor system.
     174\code{start_actor_system} has three overloaded signatures which all start the actor system, but vary in executor configuration:
    116175
    117176\noindent\code{void start_actor_system()} configures the executor with one underlying worker thread and processor.
    118177
    119 \noindent\code{void start_actor_system( size_t num_thds )} configures the executor with \code{num_thds} underlying processors and \code{num_thds} worker threads. It chooses amount of queue sharding as a function of \code{num_thds}.
    120 
    121 \noindent\code{void start_actor_system( executor & this )} allows the user to allocate, configure, and pass an executor so that they have full control of executor parameterization. Executor configuration options include number of worker threads, number of queues, number of processors, and a few other toggles.
     178\noindent\code{void start_actor_system( size_t num_thds )} configures the executor with \code{num_thds} underlying processors and \code{num_thds} worker threads.
     179It chooses amount of queue sharding as a function of \code{num_thds}.
     180
     181\noindent\code{void start_actor_system( executor & this )} allows the user to allocate, configure, and pass an executor so that they have full control of executor parameterization.
     182Executor configuration options include number of worker threads, number of queues, number of processors, and a few other toggles.
    122183
    123184All actors must be created after calling \code{start_actor_system} so that the executor can keep track of the number of actors that have been allocated but have not yet terminated.
    124185
    125 All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output. The signature of the left shift operator is:
     186All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output.
     187The signature of the left shift operator is:
    126188\begin{cfacode}
    127189Allocation ?<<?( derived_actor & receiver, derived_msg & msg )
    128190\end{cfacode}
    129191
    130 An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence. The \CFA compiler generates a \code{?<<?} routine definition and forward declaration for each \code{receive} routine that has the appropriate signature. The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine. As part of packaging the envelope, the \code{?<<?} routine sets a function pointer in the envelope to point to the appropriate receive routine for given actor and message types.
     192An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence.
     193The \CFA compiler generates a \code{?<<?} routine definition and forward declaration for each \code{receive} routine that has the appropriate signature.
     194The generated routine packages the message and actor in an \hyperref[s:envelope]{envelope} and adds it to the executor's queues via an executor routine.
     195As part of packaging the envelope, the \code{?<<?} routine sets a function pointer in the envelope to point to the appropriate receive routine for given actor and message types.
     196
    131197
    132198\section{\CFA Executor}\label{s:executor}
    133 This section will describe the basic architecture of the \CFA executor. Any discussion of work stealing is omitted until Section \ref{s:steal}. The executor of an actor system is the scheduler that organizes where actors behaviours are run and how messages are sent and delivered. In \CFA the executor lays out actors across the sharded message queues in round robin order as they are created. The message queues are split across worker threads in equal chunks, or as equal as possible if the number of message queues is not divisible by the number of workers threads.
     199This section will describe the basic architecture of the \CFA executor.
     200Any discussion of work stealing is omitted until Section \ref{s:steal}.
     201The executor of an actor system is the scheduler that organizes where actors behaviours are run and how messages are sent and delivered.
     202In \CFA the executor lays out actors across the sharded message queues in round robin order as they are created.
     203The message queues are split across worker threads in equal chunks, or as equal as possible if the number of message queues is not divisible by the number of workers threads.
    134204
    135205\begin{figure}
    … …  
    141211\end{figure}
    142212
    143 Each worker thread iterates over its own message queues until it finds one that contains messages. At this point the worker thread \newterm{gulps} the queue. A \newterm{gulp} is a term for consuming the contents of message queue and transferring them to the local queue of worker thread. After the gulp is done atomically, this allows the worker thread to process the queue locally without any need for atomicity until the next gulp. Messages can be added to the queue that was gulped in parallel with the processing of the local queue. Additionally, prior to each gulp, the worker non-atomically checks if a queue is empty before attempting to gulp it. Between this and the gulp, the worker avoids many potentially costly lock acquisitions. An example of the queue gulping operation is shown in Figure \ref{f:gulp} where a worker thread gulps queue 0 and begins to process it locally.
    144 
    145 To process its local queue, a worker thread takes each unit of work off the queue and executes it. Since all messages to a given actor will be in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time. After running behaviour, the worker thread looks at the returned allocation status and takes the corresponding action. Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues. Once a worker thread sees a sentinel it stops running. After all workers stop running the actor system shutdown is complete.
     213Each worker thread iterates over its own message queues until it finds one that contains messages.
     214At this point the worker thread \textbf{gulps} the queue.
     215A \textbf{gulp} is a term for consuming the contents of message queue and transferring them to the local queue of worker thread.
     216After the gulp is done atomically, this allows the worker thread to process the queue locally without any need for atomicity until the next gulp.
     217Messages can be added to the queue that was gulped in parallel with the processing of the local queue.
     218Additionally, prior to each gulp, the worker non-atomically checks if a queue is empty before attempting to gulp it.
     219Between this and the gulp, the worker avoids many potentially costly lock acquisitions.
     220An example of the queue gulping operation is shown in Figure \ref{f:gulp} where a worker thread gulps queue 0 and begins to process it locally.
     221
     222To process its local queue, a worker thread takes each unit of work off the queue and executes it.
     223Since all messages to a given actor will be in the same queue, this guarantees atomicity across behaviours of that actor since it can only execute on one thread at a time.
     224After running behaviour, the worker thread looks at the returned allocation status and takes the corresponding action.
     225Once all actors have marked themselves as being finished the executor initiates shutdown by inserting a sentinel value into the message queues.
     226Once a worker thread sees a sentinel it stops running.
     227After all workers stop running the actor system shutdown is complete.
    146228
    147229\section{Envelopes}\label{s:envelope}
    148 In actor systems messages are sent and received by actors. When a actor receives a message it  executes its behaviour that is associated with that message type. However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive. Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor. All these requirements are fulfilled by a construct called an envelope. The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields. To meet the persistence requirement the envelope is dynamically allocated and cleaned up after it has been delivered and its payload has run.
    149 
    150 One may ask, "Could the link fields and other information be stored in the message?". This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers. However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time. Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse.
    151 
    152 This frequent allocation of envelopes with each message send between actors results in heavy contention on the memory allocator. As such, a way to alleviate contention on the memory allocator could result in performance improvement. Contention was reduced using a novel data structure that called a \newterm{copy queue}.
     230In actor systems messages are sent and received by actors.
     231When a actor receives a message it  executes its behaviour that is associated with that message type.
     232However the unit of work that stores the message, the receiving actor's address, and other pertinent information needs to persist between send and the receive.
     233Furthermore the unit of work needs to be able to be stored in some fashion, usually in a queue, until it is executed by an actor.
     234All these requirements are fulfilled by a construct called an envelope.
     235The envelope wraps up the unit of work and also stores any information needed by data structures such as link fields.
     236To meet the persistence requirement the envelope is dynamically allocated and cleaned up after it has been delivered and its payload has run.
     237
     238One may ask, "Could the link fields and other information be stored in the message?".
     239This is a good question to ask since messages also need to have a lifetime that persists beyond the work it delivers.
     240However, if one were to use messages as envelopes then a message would not be able to be sent to multiple actors at a time.
     241Therefore this approach would just push the allocation into another location, and require the user to dynamically allocate a message for every send, or require careful ordering to allow for message reuse.
     242
     243This frequent allocation of envelopes with each message send between actors results in heavy contention on the memory allocator.
     244As such, a way to alleviate contention on the memory allocator could result in performance improvement.
     245Contention was reduced using a novel data structure that is called a copy queue.
    153246
    154247\subsection{The Copy Queue}\label{s:copyQueue}
    155 The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind. A copy queue supports the typical queue operations of push/pop but in a different way than a typical array based queue. The copy queue is designed to take advantage of the \hyperref[s:executor]{gulping} pattern. As such the amortized rutime cost of each push/pop operation for the copy queue is $O(1)$. In contrast, a naive array based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since for at least one of the operations all the elements of the queue have to be shifted over. Since the worker threads gulp each queue to operate on locally, this creates a usage pattern of the queue where all elements are popped from the copy queue without any interleaved pushes. As such, during pop operations there is no need to shift array elements. An index is stored in the copy queue data structure which keeps track of which element to pop next allowing pop to be $O(1)$. Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic sized array.
     248The copy queue is a thin layer over a dynamically sized array that is designed with the envelope use case in mind.
     249A copy queue supports the typical queue operations of push/pop but in a different way than a typical array based queue.
     250The copy queue is designed to take advantage of the \hyperref[s:executor]{gulping} pattern.
     251As such the amortized rutime cost of each push/pop operation for the copy queue is $O(1)$.
     252In contrast, a naive array based queue often has either push or pop cost $O(n)$ and the other cost $O(1)$ since for at least one of the operations all the elements of the queue have to be shifted over.
     253Since the worker threads gulp each queue to operate on locally, this creates a usage pattern of the queue where all elements are popped from the copy queue without any interleaved pushes.
     254As such, during pop operations there is no need to shift array elements.
     255An index is stored in the copy queue data structure which keeps track of which element to pop next allowing pop to be $O(1)$.
     256Push operations are amortized $O(1)$ since pushes may cause doubling reallocations of the underlying dynamic sized array.
    156257
    157258% C_TODO: maybe make copy_queue diagram
    158259
    159 Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed. For a fixed message throughput workload, once the copy queues grow in size to facilitate the number of messages in flight, there are no longer any dynamic allocations occuring in the actor system. One problem that arises with this approach is that this array based approach will often allocate more storage than what is needed. Comparitively the individual envelope allocations of a list based queue mean that the actor system will always use the minimum amount of heap space needed and will clean up eagerly. Additionally, a workload with variable message throughput could cause copy queues to allocate large amounts of space to accomodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
    160 
    161 To mitigate this a memory reclamation scheme was introduced. Initially the memory reclamation naively reclaimed one index of the array per gulp if the array size was above a low fixed threshold. This approach had a problem. The high memory usage watermark nearly doubled with this change! The issue with this approach can easily be highlighted with an example. Say that there is a fixed throughput workload where a queue never has more than 19 messages at a time. If the copy queue starts with a size of 10, it will end up doubling at some point to size 20 to accomodate 19 messages. However, after 2 gulps and subsequent reclamations the array would be size 18. The next time 19 messages are enqueued, the array size is doubled to 36! To avoid this issue a second check was added to reclamation. Each copy queue started tracking the utilization of their array size. Reclamation would only occur if less than half of the array was being utilized. In doing this the reclamation scheme was able to achieve a lower high watermark and a lower overall memory utilization when compared to the non-reclamation copy queues. However, the use of copy queues still incurs a higher memory cost than the list based queueing. With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and will be discussed further in Section \ref{s:actor_perf}.
     260Since the copy queue is an array, envelopes are allocated first on the stack and then copied into the copy queue to persist until they are no longer needed.
     261For a fixed message throughput workload, once the copy queues grow in size to facilitate the number of messages in flight, there are no longer any dynamic allocations occuring in the actor system.
     262One problem that arises with this approach is that this array based approach will often allocate more storage than what is needed.
     263Comparitively the individual envelope allocations of a list based queue mean that the actor system will always use the minimum amount of heap space needed and will clean up eagerly.
     264Additionally, a workload with variable message throughput could cause copy queues to allocate large amounts of space to accomodate the peaks of the throughput, even if most of that storage is not needed for the rest of the workload's execution.
     265
     266
     267To mitigate this a memory reclamation scheme was introduced.
     268Initially the memory reclamation naively reclaimed one index of the array per gulp if the array size was above a low fixed threshold.
     269This approach had a problem.
     270The high memory usage watermark nearly doubled with this change! The issue with this approach can easily be highlighted with an example.
     271Say that there is a fixed throughput workload where a queue never has more than 19 messages at a time.
     272If the copy queue starts with a size of 10, it will end up doubling at some point to size 20 to accomodate 19 messages.
     273However, after 2 gulps and subsequent reclamations the array would be size 18.
     274The next time 19 messages are enqueued, the array size is doubled to 36! To avoid this issue a second check was added to reclamation.
     275Each copy queue started tracking the utilization of their array size.
     276Reclamation would only occur if less than half of the array was being utilized.
     277In doing this the reclamation scheme was able to achieve a lower high watermark and a lower overall memory utilization when compared to the non-reclamation copy queues.
     278However, the use of copy queues still incurs a higher memory cost than the list based queueing.
     279With the inclusion of a memory reclamation scheme the increase in memory usage is reasonable considering the performance gains and will be discussed further in Section \ref{s:actor_perf}.
    162280
    163281\section{Work Stealing}\label{s:steal}
    164 Work stealing is a scheduling strategy that attempts to load balance, and increase resource untilization by having idle threads steal work. There are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.
     282Work stealing is a scheduling strategy that attempts to load balance, and increase resource untilization by having idle threads steal work.
     283There are many parts that make up a work stealing actor scheduler, but the two that will be highlighted in this work are the stealing mechanism and victim selection.
    165284
    166285% C_TODO enter citation for langs
    167286\subsection{Stealing Mechanism}
    168 In this discussion of work stealing the worker being stolen from will be referred to as the \newterm{victim} and the worker stealing work will be called the \newterm{thief}. The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system. Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue. As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues). Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue. Workers then consume actors from the dequeue and execute their behaviours. To steal work, thieves take one or more actors from a victim's dequeue. This action creates contention on the dequeue, which can slow down the throughput of the victim. The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant. By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues.
     287In this discussion of work stealing the worker being stolen from will be referred to as the \textbf{victim} and the worker stealing work will be called the \textbf{thief}.
     288The stealing mechanism presented here differs from existing work stealing actor systems due the inverted actor system.
     289Other actor systems such as Akka \cite{} and CAF \cite{} have work stealing, but since they use an classic actor system that is actor-centric, stealing work is the act of stealing an actor from a dequeue.
     290As an example, in CAF, the sharded actor queue is a set of double ended queues (dequeues).
     291Whenever an actor is moved to a ready queue, it is inserted into a worker's dequeue.
     292Workers then consume actors from the dequeue and execute their behaviours.
     293To steal work, thieves take one or more actors from a victim's dequeue.
     294This action creates contention on the dequeue, which can slow down the throughput of the victim.
     295The notion of which end of the dequeue is used for stealing, consuming, and inserting is not discussed since it isn't relevant.
     296By the pigeon hole principle there are three dequeue operations (push/victim pop/thief pop) that can occur concurrently and only two ends to a dequeue, so work stealing being present in a dequeue based system will always result in a potential increase in contention on the dequeues.
    169297
    170298% C_TODO: maybe insert stealing diagram
    171299
    172 In \CFA, the actor work stealing implementation is unique. While other systems are concerned with stealing actors, the \CFA actor system steals queues. This is a result of \CFA's use of the inverted actor system.  The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism. This does not means that stealing has no cost. This goal is to ensure that stealing work does not impact the performance of victim workers. This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief. In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice. In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp. If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker. Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers. To steal a queue a worker does the following:
     300In \CFA, the actor work stealing implementation is unique.
     301While other systems are concerned with stealing actors, the \CFA actor system steals queues.
     302This is a result of \CFA's use of the inverted actor system.
     303 The goal of the \CFA actor work stealing mechanism is to have a zero-victim-cost stealing mechanism.
     304This does not means that stealing has no cost.
     305This goal is to ensure that stealing work does not impact the performance of victim workers.
     306This means that thieves can not contend with victims, and that victims should perform no stealing related work unless they become a thief.
     307In theory this goal is not achieved, but results will be presented that show the goal is achieved in practice.
     308In \CFA's actor system workers own a set of sharded queues which they iterate over and gulp.
     309If a worker has iterated over the queues they own twice without finding any work, they try to steal a queue from another worker.
     310Stealing a queue is done wait-free with a few atomic instructions that can only create contention with other stealing workers.
     311To steal a queue a worker does the following:
    173312\begin{enumerate}[topsep=5pt,itemsep=3pt,parsep=0pt]
    174313\item
    … …  
    176315
    177316\item
    178 The thief starts at a random index in the array of the victim's queues and searches for a candidate queue. A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim. These are not strictly enforced rules. The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen. However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped.
    179 
    180 \item
    181 Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues. This swap can fail. If the swap is successful the thief swaps the two queues. If the swap fails, another thief must have attempted to steal one of the two queues being swapped. Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue.
     317The thief starts at a random index in the array of the victim's queues and searches for a candidate queue.
     318A candidate queue is any queue that is not empty, is not being stolen by another thief, and is not being processed by the victim.
     319These are not strictly enforced rules.
     320The candidate is identified non-atomically and as such queues that do not satisfy these rules may be stolen.
     321However, steals that do not meet these requirements do not affect correctness so they are allowed and do not constitute failed steals as the queues will still be swapped.
     322
     323
     324\item
     325Once a candidate queue is chosen, the thief attempts a wait-free swap of the victim's queue and a random on of the thief's queues.
     326This swap can fail.
     327If the swap is successful the thief swaps the two queues.
     328If the swap fails, another thief must have attempted to steal one of the two queues being swapped.
     329Failing to steal is good in this case since stealing a queue that was just swapped would likely result in stealing an empty queue.
    182330\end{enumerate}
    183331
    184 Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again. It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work. The key to the stealing mechnism is that the queues can still be operated on while they are being swapped. This elimates any contention between thieves and victims. The first key to this is that actors and workers maintain two distinct arrays of references to queues. Actors will always receive messages via the same queues. Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own. Swapping queues is a matter of atomically swapping two pointers in the worker array. As such pushes to the queues can happen concurrently during the swap since pushes happen via the actor queue references.
    185 
    186 Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes. When a worker is not stealing it iterates across its own range of queues and gulps them one by one. When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable. It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array. This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue. If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees. As such this must be avoided. To avoid this each queue has a \code{being_processed} flag that is atomically set to \code{true} when a queue is gulped. The flag indicates that a queue is being processed locally and is set back to \code{false} once the local processing is finished. If a worker attempts to gulp a queue and finds that the \code{being_processed} flag is \code{true}, it does not gulp the queue and moves on to the next queue in its range. This is a source of contention between victims and thieves since a thief may steal a queue and set \code{being_processed} to \code{true} between a victim saving a pointer to a queue and gulping it. However, the window for this race is very small, making this contention rare. This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory. By collecting statistics on failed gulps due to the \code{being_processed} flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs. Hence, the claim is made that this stealing mechanism has zero-victim-cost in practice.
     332Once a thief fails or succeeds in stealing a queue, it goes back to its own set of queues and iterates over them again.
     333It will only try to steal again once it has completed two consecutive iterations over its owned queues without finding any work.
     334The key to the stealing mechnism is that the queues can still be operated on while they are being swapped.
     335This elimates any contention between thieves and victims.
     336The first key to this is that actors and workers maintain two distinct arrays of references to queues.
     337Actors will always receive messages via the same queues.
     338Workers, on the other hand will swap the pointers to queues in their shared array and operate on queues in the range of that array that they own.
     339Swapping queues is a matter of atomically swapping two pointers in the worker array.
     340As such pushes to the queues can happen concurrently during the swap since pushes happen via the actor queue references.
     341
     342Gulping can also occur during queue swapping, but the implementation requires more nuance than the pushes.
     343When a worker is not stealing it iterates across its own range of queues and gulps them one by one.
     344When a worker operates on a queue it first copies the current pointer from the worker array of references to a local variable.
     345It then uses that local variable for all queue operations until it moves to the next index of its range of the queue array.
     346This ensures that any swaps do not interrupt gulping operations, however this introduces a correctness issue.
     347If any behaviours from a queue are run by two workers at a time it violates both mutual exclusion and the actor ordering guarantees.
     348As such this must be avoided.
     349To avoid this each queue has a \code{being_processed} flag that is atomically set to \code{true} when a queue is gulped.
     350The flag indicates that a queue is being processed locally and is set back to \code{false} once the local processing is finished.
     351If a worker attempts to gulp a queue and finds that the \code{being_processed} flag is \code{true}, it does not gulp the queue and moves on to the next queue in its range.
     352This is a source of contention between victims and thieves since a thief may steal a queue and set \code{being_processed} to \code{true} between a victim saving a pointer to a queue and gulping it.
     353However, the window for this race is very small, making this contention rare.
     354This is why the claim is made that this mechanism is zero-victim-cost in practice but not in theory.
     355By collecting statistics on failed gulps due to the \code{being_processed} flag, it is found that this contention occurs ~0.05\% of the time when a gulp occurs.
     356Hence, the claim is made that this stealing mechanism has zero-victim-cost in practice.
    187357
    188358
    189359\subsection{Queue Swap Correctness}
    190 Given the wait-free swap used is novel, it is important to show that it is correct. Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping. There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief. In both cases it is apropos for a thief to given up on stealing. \CFA-style pseudocode for the queue swap is presented below. The swap uses compare-and-swap (\code{CAS}) which is just pseudocode for C's \code{__atomic_compare_exchange_n}. A pseudocode implementation of \code{CAS} is also shown below. The correctness of the wait-free swap will now be discussed in detail. To first verify sequential correctness, consider the equivalent sequential swap below:
     360Given the wait-free swap used is novel, it is important to show that it is correct.
     361Firstly, it is clear to show that the swap is wait-free since all workers will fail or succeed in swapping the queues in a finite number of steps since there are no locks or looping.
     362There is no retry mechanism in the case of a failed swap, since a failed swap either means the work was already stolen, or that work was stolen from the thief.
     363In both cases it is apropos for a thief to given up on stealing.
     364\CFA-style pseudocode for the queue swap is presented below.
     365The swap uses compare-and-swap (\code{CAS}) which is just pseudocode for C's \code{__atomic_compare_exchange_n}.
     366A pseudocode implementation of \code{CAS} is also shown below.
     367The correctness of the wait-free swap will now be discussed in detail.
     368To first verify sequential correctness, consider the equivalent sequential swap below:
    191369
    192370\begin{cfacode}
    … …  
    204382\end{cfacode}
    205383
    206 Step 1 is missing in the sequential example since in only matter in the concurrent context presented later. By looking at the sequential swap it is easy to see that it is correct. Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer.
     384Step 1 is missing in the sequential example since in only matter in the concurrent context presented later.
     385By looking at the sequential swap it is easy to see that it is correct.
     386Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer.
    207387
    208388\begin{cfacode}
    … …  
    254434Step 0 is the same as the sequential example, and the thief stores local copies of the two pointers to be swapped.
    255435\item
    256 Step 1 verifies that the stored copy of the victim queue pointer, \code{vic_queue}, is valid. If \code{vic_queue} is equal to \code{0p}, then the victim queue is part of another swap so the operation fails. No state has changed at this point so no fixups are needed. Note, \code{my_queue} can never be equal to \code{0p} at this point since thieves only set their own queues pointers to \code{0p} when stealing. At no other point will a queue pointer be set to \code{0p}. Since each worker owns a disjoint range of the queue array, it is impossible for \code{my_queue} to be \code{0p}.
    257 \item
    258 Step 2 attempts to set the thief's queue pointer to \code{0p} via \code{CAS}. The \code{CAS} will only fail if the thief's queue pointer is no longer equal to \code{my_queue}, which implies that this thief has become a victim and its queue has been stolen. At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false. If the \code{CAS} succeeds then the thief's queue pointer will now be \code{0p}. Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for \code{0p}.
    259 \item
    260 Step 3 attempts to set the victim's queue pointer to be \code{my_queue} via \code{CAS}. If the \code{CAS} succeeds then the victim's queue pointer has been set and swap can no longer fail. If the \code{CAS} fails then the thief's queue pointer must be restored to its previous value before returning.
     436Step 1 verifies that the stored copy of the victim queue pointer, \code{vic_queue}, is valid.
     437If \code{vic_queue} is equal to \code{0p}, then the victim queue is part of another swap so the operation fails.
     438No state has changed at this point so no fixups are needed.
     439Note, \code{my_queue} can never be equal to \code{0p} at this point since thieves only set their own queues pointers to \code{0p} when stealing.
     440At no other point will a queue pointer be set to \code{0p}.
     441Since each worker owns a disjoint range of the queue array, it is impossible for \code{my_queue} to be \code{0p}.
     442\item
     443Step 2 attempts to set the thief's queue pointer to \code{0p} via \code{CAS}.
     444The \code{CAS} will only fail if the thief's queue pointer is no longer equal to \code{my_queue}, which implies that this thief has become a victim and its queue has been stolen.
     445At this point the thief-turned-victim will fail and since it has not changed any state it just fails and returns false.
     446If the \code{CAS} succeeds then the thief's queue pointer will now be \code{0p}.
     447Nulling the pointer is safe since only thieves look at other worker's queue ranges, and whenever thieves need to dereference a queue pointer they check for \code{0p}.
     448\item
     449Step 3 attempts to set the victim's queue pointer to be \code{my_queue} via \code{CAS}.
     450If the \code{CAS} succeeds then the victim's queue pointer has been set and swap can no longer fail.
     451If the \code{CAS} fails then the thief's queue pointer must be restored to its previous value before returning.
    261452\item
    262453Step 4 sets the thief's queue pointer to be \code{vic_queue} completing the swap.
    … …  
    267458\end{theorem}
    268459
    269 Correctness of the swap is shown through the existence of an invariant. The invariant is that when a queue pointer is set to \code{0p} by a thief, then the next write to the pointer can only be performed by the same thief. To show that this invariant holds, it is shown that it is true at each step of the swap. Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves. In step 2 a thief attempts to write \code{0p} to one of their queue pointers. This queue pointer cannot be \code{0p}. As stated above, \code{my_queue} is never equal to \code{0p} since thieves will only write \code{0p} to queue pointers from their own queue range and all worker's queue ranges are disjoint. As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p. In step 3 the thief attempts to write \code{my_queue} to the victim's queue pointer. If the current value of the victim's queue pointer is \code{0p}, then the CAS will fail since \code{vic_queue} cannot be equal to \code{0p} because of the check in step 1. Therefore in the success case where the \code{CAS} succeeds, the value of the victim's queue pointer must not be \code{0p}. As such, the write will never overwrite a value of \code{0p}, hence the invariant is held in the \code{CAS} of step 3. The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a \code{0p} queue pointer and they are being set by the same thief that set the pointer to \code{0p}.
    270 
    271 Given this informal proof of invariance it can be shown that the successful swap is correct. Once a thief atomically sets their queue pointer to be \code{0p} in step 2, the invariant guarantees that pointer will not change. As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be \code{vic_queue} due to the use of \code{CAS}. Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed. By the invariant the write back in the successful case is correct since no other worker can write to the \code{0p} pointer.
    272 
    273 In the failed case the outcome is correct in steps 1 and 2 since no writes have occured so the program state is unchanged. In the failed case of step 3 the program state is safely restored to its state it had prior to the \code{0p} write in step 2, thanks to the invariant that makes the write back to the \code{0p} pointer safe.
     460Correctness of the swap is shown through the existence of an invariant.
     461The invariant is that when a queue pointer is set to \code{0p} by a thief, then the next write to the pointer can only be performed by the same thief.
     462To show that this invariant holds, it is shown that it is true at each step of the swap.
     463Step 0 and 1 do not write and as such they cannot invalidate the invariant of any other thieves.
     464In step 2 a thief attempts to write \code{0p} to one of their queue pointers.
     465This queue pointer cannot be \code{0p}.
     466As stated above, \code{my_queue} is never equal to \code{0p} since thieves will only write \code{0p} to queue pointers from their own queue range and all worker's queue ranges are disjoint.
     467As such step 2 upholds the invariant since in a failure case no write occurs, and in the success case, the value of the queue pointer is guaranteed to not be 0p.
     468In step 3 the thief attempts to write \code{my_queue} to the victim's queue pointer.
     469If the current value of the victim's queue pointer is \code{0p}, then the CAS will fail since \code{vic_queue} cannot be equal to \code{0p} because of the check in step 1.
     470Therefore in the success case where the \code{CAS} succeeds, the value of the victim's queue pointer must not be \code{0p}.
     471As such, the write will never overwrite a value of \code{0p}, hence the invariant is held in the \code{CAS} of step 3.
     472The write back to the thief's queue pointer that happens in the failure case of step three and in step 4 hold the invariant since they are the subsequent write to a \code{0p} queue pointer and they are being set by the same thief that set the pointer to \code{0p}.
     473
     474Given this informal proof of invariance it can be shown that the successful swap is correct.
     475Once a thief atomically sets their queue pointer to be \code{0p} in step 2, the invariant guarantees that pointer will not change.
     476As such, in the success case step 3 it is known that the value of the victim's queue pointer that was overwritten must be \code{vic_queue} due to the use of \code{CAS}.
     477Given that pointers all have unique memory locations, this first write of the successful swap is correct since it can only occur when the pointer has not changed.
     478By the invariant the write back in the successful case is correct since no other worker can write to the \code{0p} pointer.
     479
     480In the failed case the outcome is correct in steps 1 and 2 since no writes have occured so the program state is unchanged.
     481In the failed case of step 3 the program state is safely restored to its state it had prior to the \code{0p} write in step 2, thanks to the invariant that makes the write back to the \code{0p} pointer safe.
    274482
    275483\subsection{Stealing Guarantees}
    276484
    277485% C_TODO insert graphs for each proof
    278 Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation. Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue. Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge. A corollary that can be drawn from this, is that there are at most $V$ edges in this constructed set of connected directed graphs, where $V$ is the total number of vertices.
     486Given that the stealing operation can potentially fail, it is important to discuss the guarantees provided by the stealing implementation.
     487Given a set of $N$ swaps a set of connected directed graphs can be constructed where each vertex is a queue and each edge is a swap directed from a thief queue to a victim queue.
     488Since each thief can only steal from one victim at a time, each vertex can only have at most one outgoing edge.
     489A corollary that can be drawn from this, is that there are at most $V$ edges in this constructed set of connected directed graphs, where $V$ is the total number of vertices.
    279490
    280491\begin{figure}
    … …  
    291502A graph of the $M$ thieves swapping with one victim discussed in this theorem is presented in Figure~\ref{f:M_one_swap}.
    292503\\
    293 First it is important to state that a thief will not attempt to steal from themselves. As such, the victim here is not also a thief. Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be \code{0p}. Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves. In step 3 the first thief to \code{CAS} will win the race and successfully swap the queue pointer. Since it is the first one to \code{CAS} and \code{CAS} is atomic, there is no way for the \code{CAS} to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing. Hence at least one swap is guaranteed to succeed in this case.
     504First it is important to state that a thief will not attempt to steal from themselves.
     505As such, the victim here is not also a thief.
     506Stepping through the code in \ref{c:swap}, for all thieves steps 0-1 succeed since the victim is not stealing and will have no queue pointers set to be \code{0p}.
     507Similarly for all thieves step 2 will succeed since no one is stealing from any of the thieves.
     508In step 3 the first thief to \code{CAS} will win the race and successfully swap the queue pointer.
     509Since it is the first one to \code{CAS} and \code{CAS} is atomic, there is no way for the \code{CAS} to fail since no other thief could have written to the victim's queue pointer and the victim did not write to the pointer since they aren't stealing.
     510Hence at least one swap is guaranteed to succeed in this case.
    294511
    295512\begin{figure}
    … …  
    306523A graph of the chain of swaps discussed in this theorem is presented in Figure~\ref{f:chain_swap}.
    307524\\
    308 This is a proof by contradiction. Assume no swaps occur. Then all thieves must have failed at step 1, step 2 or step 3. For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeded at step 2 before $b$ executes step 0. Hence, not all thieves can fail at step 1. Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state. There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2. Hence, without loss of generality, whether thieves succeed or fail at step 1, this proof can proceed inductively.
    309 
    310 For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2. The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3. If $j$ finished step 3 then the at least one swap was successful. Therefore all thieves did not fail at step 2. Hence all thieves must successfully complete step 2 and fail at step 3. However, since the first worker, thief $0$, is solely a victim and not a thief, it does not change the state of any of its queue pointers. Hence, in this case thief $1$ will always succeed in step 3 if all thieves succeed in step 2. Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.
     525This is a proof by contradiction.
     526Assume no swaps occur.
     527Then all thieves must have failed at step 1, step 2 or step 3.
     528For a given thief $b$ to fail at step 1, thief $b + 1$ must have succeded at step 2 before $b$ executes step 0.
     529Hence, not all thieves can fail at step 1.
     530Furthermore if a thief $b$ fails at step 1 it logically splits the chain into two subchains $0 <- b$ and $b + 1 <- M - 1$, where $b$ has become solely a victim since its swap has failed and it did not modify any state.
     531There must exist at least one chain containing two or more queues after since it is impossible for a split to occur both before and after a thief, since that requires failing at step 1 and succeeding at step 2.
     532Hence, without loss of generality, whether thieves succeed or fail at step 1, this proof can proceed inductively.
     533
     534For a given thief $i$ to fail at step 2, it means that another thief $j$ had to have written to $i$'s queue pointer between $i$'s step 0 and step 2.
     535The only way for $j$ to write to $i$'s queue pointer would be if $j$ was stealing from $i$ and had successfully finished step 3.
     536If $j$ finished step 3 then the at least one swap was successful.
     537Therefore all thieves did not fail at step 2.
     538Hence all thieves must successfully complete step 2 and fail at step 3.
     539However, since the first worker, thief $0$, is solely a victim and not a thief, it does not change the state of any of its queue pointers.
     540Hence, in this case thief $1$ will always succeed in step 3 if all thieves succeed in step 2.
     541Thus, by contradiction with the earlier assumption that no swaps occur, at least one swap must succeed.
    311542
    312543% \raisebox{.1\height}{}
    … …  
    321552
    322553\begin{theorem}
    323 Given a set of $M > 1$ swaps occuring that form a single directed connected graph. At least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     554Given a set of $M > 1$ swaps occuring that form a single directed connected graph.
     555At least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
    324556\end{theorem}\label{t:vic_cycle}
    325557Representations of cyclic and acylic swap graphs discussed in this theorem are presented in Figures~\ref{f:cyclic_swap} and \ref{f:acyclic_swap}.
    326558\\
    327 First the reverse direction is proven. If the graph does not contain a cycle, then there must be at least one successful swap. Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges. The graph can then be formulated as a tree with $A$ at the top since each node only has at most one outgoing edge and there are no cycles. The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}. Assume no swaps occur. Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 1, so the proof proceeds without loss of generality. Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap. Hence, the only way forward is to assume all thieves successfully complete step 2. Hence for there to be no swaps all thieves must fail step 3. However, since $A$ has no outgoing edges, since the graph is connected there must be some $K$ such that $K < M - 1$ thieves are attempting to swap with $A$. Since all $K$ thieves have passed step 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed. Thus, by contradiction with the earlier assumption that no swaps occur, if the graph does not contain a cycle, at least one swap must succeed.
    328 
    329 The forward direction is proven by contrapositive. If the graph contains a cycle then there exists a situation where no swaps occur. This situation is constructed. Since all vertices have at most one outgoing edge the cycle must be directed. Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge. This is shown through construction of an aribtrary cyclic graph. The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle. Since the graph is connected, and each vertex has at most one outgoing edge, none of the vertices in the cycle have available outgoing edges to accomodate new vertices with no outgoing edges. Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges. Thus, by induction all vertices in the graph must have exactly one outgoing edge. Hence all vertices are thief queues. Now consider the case where all thieves successfully complete step 0-1, and then they all complete step 2. At this point all thieves are attempting to swap with a queue pointer whose value has changed to \code{0p}. If all thieves attempt the \code{CAS} before any write backs, then they will all fail. Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur. Hence, at least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
     559First the reverse direction is proven.
     560If the graph does not contain a cycle, then there must be at least one successful swap.
     561Since the graph contains no cycles and is finite in size, then there must be a vertex $A$ with no outgoing edges.
     562The graph can then be formulated as a tree with $A$ at the top since each node only has at most one outgoing edge and there are no cycles.
     563The forward direction is proven by contradiction in a similar fashion to \ref{t:vic_chain}.
     564Assume no swaps occur.
     565Similar to \ref{t:vic_chain}, this graph can be inductively split into subgraphs of the same type by failure at step 1, so the proof proceeds without loss of generality.
     566Similar to \ref{t:vic_chain} the conclusion is drawn that all thieves must successfully complete step 2 for no swaps to occur, since for step 2 to fail, a different thief has to successfully complete step 3, which would imply a successful swap.
     567Hence, the only way forward is to assume all thieves successfully complete step 2.
     568Hence for there to be no swaps all thieves must fail step 3.
     569However, since $A$ has no outgoing edges, since the graph is connected there must be some $K$ such that $K < M - 1$ thieves are attempting to swap with $A$.
     570Since all $K$ thieves have passed step 2, similar to \ref{t:one_vic} the first one of the $K$ thieves to attempt step 3 is guaranteed to succeed.
     571Thus, by contradiction with the earlier assumption that no swaps occur, if the graph does not contain a cycle, at least one swap must succeed.
     572
     573The forward direction is proven by contrapositive.
     574If the graph contains a cycle then there exists a situation where no swaps occur.
     575This situation is constructed.
     576Since all vertices have at most one outgoing edge the cycle must be directed.
     577Furthermore, since the graph contains a cycle all vertices in the graph must have exactly one outgoing edge.
     578This is shown through construction of an aribtrary cyclic graph.
     579The graph contains a directed cycle by definition, so the construction starts with $T$ vertices in a directed cycle.
     580Since the graph is connected, and each vertex has at most one outgoing edge, none of the vertices in the cycle have available outgoing edges to accomodate new vertices with no outgoing edges.
     581Any vertices added to the graph must have an outgoing edge to connect, leaving the resulting graph with no available outgoing edges.
     582Thus, by induction all vertices in the graph must have exactly one outgoing edge.
     583Hence all vertices are thief queues.
     584Now consider the case where all thieves successfully complete step 0-1, and then they all complete step 2.
     585At this point all thieves are attempting to swap with a queue pointer whose value has changed to \code{0p}.
     586If all thieves attempt the \code{CAS} before any write backs, then they will all fail.
     587Thus, by contrapositive, if the graph contains a cycle then there exists a situation where no swaps occur.
     588Hence, at least one swap is guaranteed to suceed if and only if the graph does not contain a cycle.
    330589
    331590% C_TODO: go through and use \paragraph to format to make it look nicer
    332591\subsection{Victim Selection}\label{s:victimSelect}
    333 In any work stealing algorithm thieves have some heuristic to determine which victim to choose from. Choosing this algorithm is difficult and can have implications on performance. There is no one selection heuristic that is known to be the best on all workloads. Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}. However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}. Since locality aware scheduling has been explored recently, this work introduces a heuristic called \newterm{longest victim} and compares it to randomized work stealing. The longest victim heuristic maintains a timestamp per worker thread that is updated every time a worker attempts to steal work. Thieves then attempt to steal from the thread with the oldest timestamp. This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim. This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue. Furthermore in the case they attempt to steal the same queue at least one of them is guaranteed to successfully steal the queue as shown in Theorem \ref{t:one_vic}. Additonally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem \ref{t:vic_cycle} manifests. Given the longest victim heuristic, for a cycle to manifest it would require all workers to attempt to steal in a short timeframe. This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal. In this case, the probability of lack of any successful swaps is a non issue, since it is likely that these steals were not important if all workers are trying to steal.
     592In any work stealing algorithm thieves have some heuristic to determine which victim to choose from.
     593Choosing this algorithm is difficult and can have implications on performance.
     594There is no one selection heuristic that is known to be the best on all workloads.
     595Recent work focuses on locality aware scheduling in actor systems\cite{barghi18}\cite{wolke17}.
     596However, while locality aware scheduling provides good performance on some workloads, something as simple as randomized selection performs better on other workloads\cite{barghi18}.
     597Since locality aware scheduling has been explored recently, this work introduces a heuristic called \textbf{longest victim} and compares it to randomized work stealing.
     598The longest victim heuristic maintains a timestamp per worker thread that is updated every time a worker attempts to steal work.
     599Thieves then attempt to steal from the thread with the oldest timestamp.
     600This means that if two thieves look to steal at the same time, they likely will attempt to steal from the same victim.
     601This does increase the chance at contention between thieves, however given that workers have multiple queues under them, often in the tens or hundreds of queues per worker it is rare for two queues to attempt so steal the same queue.
     602Furthermore in the case they attempt to steal the same queue at least one of them is guaranteed to successfully steal the queue as shown in Theorem \ref{t:one_vic}.
     603Additonally, the longest victim heuristic makes it very improbable that the no swap scenario presented in Theorem \ref{t:vic_cycle} manifests.
     604Given the longest victim heuristic, for a cycle to manifest it would require all workers to attempt to steal in a short timeframe.
     605This is the only way that more than one thief could choose another thief as a victim, since timestamps are only updated upon attempts to steal.
     606In this case, the probability of lack of any successful swaps is a non issue, since it is likely that these steals were not important if all workers are trying to steal.
    334607
    335608\section{Safety and Productivity}
    336 \CFA's actor system comes with a suite of safety and productivity features. Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode. The suit of features include the following.
     609\CFA's actor system comes with a suite of safety and productivity features.
     610Most of these features are present in \CFA's debug mode, but are removed when code is compiled in nodebug mode.
     611The suit of features include the following.
    337612
    338613\begin{itemize}
    339 \item Static-typed message sends. If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors.
    340 \item Detection of message sends to Finished/Destroyed/Deleted actors. All actors have a ticket that assigns them to a respective queue. The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error.
    341 \item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors. As such, this is detected and an error is printed.
    342 \item When an executor is created, the queues are handed out to worker threads in round robin order. If there are fewer queues than worker threads, then some workers will spin and never do any work. There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of worker threads.
    343 \item A warning is printed when messages are deallocated without being sent. Since the \code{Finished} allocation status is unused for messages, it is used internally to detect if a message has been sent. Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed.
     614\item Static-typed message sends.
     615If an actor does not support receiving a given message type, the actor program is rejected at compile time, allowing unsupported messages to never be sent to actors.
     616\item Detection of message sends to Finished/Destroyed/Deleted actors.
     617All actors have a ticket that assigns them to a respective queue.
     618The maximum integer value of the ticket is reserved to indicate that an actor is dead, and subsequent message sends result in an error.
     619\item Actors made before the executor can result in undefined behaviour since an executor needs to be created beforehand so it can give out the tickets to actors.
     620As such, this is detected and an error is printed.
     621\item When an executor is created, the queues are handed out to worker threads in round robin order.
     622If there are fewer queues than worker threads, then some workers will spin and never do any work.
     623There is no reasonable use case for this behaviour so an error is printed if the number of queues is fewer than the number of worker threads.
     624\item A warning is printed when messages are deallocated without being sent.
     625Since the \code{Finished} allocation status is unused for messages, it is used internally to detect if a message has been sent.
     626Deallocating a message without sending it could indicate to a user that they are touching freed memory later, or it could point out extra allocations that could be removed.
    344627\end{itemize}
    345628
    346 In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off. These statistics have minimal impact on the actor system's performance since they are counted on a per worker thread basis. During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown. The statistics measured are as follows.
     629In addition to these features, \CFA's actor system comes with a suite of statistics that can be toggled on and off.
     630These statistics have minimal impact on the actor system's performance since they are counted on a per worker thread basis.
     631During shutdown of the actor system they are aggregated, ensuring that the only atomic instructions used by the statistics counting happen at shutdown.
     632The statistics measured are as follows.
    347633
    348634\begin{description}
    349635\item[\LstBasicStyle{\textbf{Actors Created}}]
    350 Actors created. Includes both actors made by the main and ones made by other actors.
     636Actors created.
     637Includes both actors made by the main and ones made by other actors.
    351638\item[\LstBasicStyle{\textbf{Messages Sent}}]
    352 Messages sent and received. Includes termination messages send to the worker threads.
     639Messages sent and received.
     640Includes termination messages send to the worker threads.
    353641\item[\LstBasicStyle{\textbf{Gulps}}]
    354642Gulps that occured across the worker threads.
    … …  
    359647\item[\LstBasicStyle{\textbf{Steal attempts}}]
    360648Worker threads attempts to steal work.
     649
    361650\item[\LstBasicStyle{\textbf{Steal failures (no candidates)}}]
    362651Work stealing failures due to selected victim not having any non empty or non-being-processed queues.
    … …  
    369658\end{description}
    370659
    371 These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program. For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across worker threads. In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding.
     660These statistics enable a user of \CFA's actor system to make informed choices about how to configure their executor, or how to structure their actor program.
     661For example, if there is a lot of messages being stolen relative to the number of messages sent, it could indicate to a user that their workload is heavily imbalanced across worker threads.
     662In another example, if the average gulp size is very high, it could indicate that the executor could use more queue sharding.
    372663
    373664% C_TODO cite poison pill messages and add languages
    374 Another productivity feature that is included is a group of poison-pill messages. Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}. Poison-pill messages inform an actor to terminate. In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills. The messages that \CFA provides are \code{DeleteMsg}, \code{DestroyMsg}, and \code{FinishedMsg}. These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message. Note that any pending messages to the actor will still be sent. It is still the user's responsibility to ensure that an actor does not receive any messages after termination.
     665Another productivity feature that is included is a group of poison-pill messages.
     666Poison-pill messages are common across actor systems, including Akka and ProtoActor \cite{}.
     667Poison-pill messages inform an actor to terminate.
     668In \CFA, due to the allocation of actors and lack of garbage collection, there needs to be a suite of poison-pills.
     669The messages that \CFA provides are \code{DeleteMsg}, \code{DestroyMsg}, and \code{FinishedMsg}.
     670These messages are supported on all actor types via inheritance and when sent to an actor, the actor takes the corresponding allocation action after receiving the message.
     671Note that any pending messages to the actor will still be sent.
     672It is still the user's responsibility to ensure that an actor does not receive any messages after termination.
    375673
    376674\section{Performance}\label{s:actor_perf}
    377675The performance of \CFA's actor system is tested using a suite of microbenchmarks, and compared with other actor systems.
    378 Most of the benchmarks are the same as those presented in \ref{}, with a few additions. % C_TODO cite actor paper
    379 At the time of this work the versions of the actor systems are as follows. \CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07. Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed in.
     676Most of the benchmarks are the same as those presented in \ref{}, with a few additions.
     677% C_TODO cite actor paper
     678At the time of this work the versions of the actor systems are as follows.
     679\CFA 1.0, \uC 7.0.0, Akka Typed 2.7.0, CAF 0.18.6, and ProtoActor-Go v0.0.0-20220528090104-f567b547ea07.
     680Akka Classic is omitted as Akka Typed is their newest version and seems to be the direction they are headed in.
    380681The experiments are run on
    381682\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=5pt\parsep=5pt\itemsep=0pt}
    … …  
    386687\end{list}
    387688
    388 The benchmarks are run on up to 48 cores. On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads. Either choice will cause a blip in performance trends, which can be seen in the following performance figures. On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores.
    389 
    390 All benchmarks presented are run 5 times and the median is taken. Error bars showing the 95\% confidence intervals are drawn on each point on the graphs. If the confidence bars are small enough, they may be obscured by the point. In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system. As such the peformance differences that arise are largely due to the contributions of this work.
     689The benchmarks are run on up to 48 cores.
     690On the Intel, when going beyond 24 cores there is the choice to either hop sockets or to use hyperthreads.
     691Either choice will cause a blip in performance trends, which can be seen in the following performance figures.
     692On the Intel the choice was made to hyperthread instead of hopping sockets for experiments with more than 24 cores.
     693
     694All benchmarks presented are run 5 times and the median is taken.
     695Error bars showing the 95\% confidence intervals are drawn on each point on the graphs.
     696If the confidence bars are small enough, they may be obscured by the point.
     697In this section \uC will be compared to \CFA frequently, as the actor system in \CFA was heavily based off \uC's actor system.
     698As such the peformance differences that arise are largely due to the contributions of this work.
    391699
    392700\begin{table}[t]
    … …  
    420728
    421729\subsection{Message Sends}
    422 Message sending is the key component of actor communication. As such latency of a single message send is the fundamental unit of fast-path performance for an actor system. The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send. Static and dynamic refer to the allocation of the message and actor. In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times. The average latency per message send is then calculated by dividing the duration by the number of sends. This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution. The CAF static send benchmark only sends a message 10M times to avoid extensively long run times.
    423 
    424 In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated. This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size. Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration.
    425 
    426 The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively. \CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations. In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns. In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations. However,  Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA. This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation.
     730Message sending is the key component of actor communication.
     731As such latency of a single message send is the fundamental unit of fast-path performance for an actor system.
     732The following two microbenchmarks evaluate the average latency for a static actor/message send and a dynamic actor/message send.
     733Static and dynamic refer to the allocation of the message and actor.
     734In the static send benchmark a message and actor are allocated once and then the message is sent to the same actor repeatedly until it has been sent 100 million (100M) times.
     735The average latency per message send is then calculated by dividing the duration by the number of sends.
     736This benchmark evaluates the cost of message sends in the actor use case where all actors and messages are allocated ahead of time and do not need to be created dynamically during execution.
     737The CAF static send benchmark only sends a message 10M times to avoid extensively long run times.
     738
     739In the dynamic send benchmark the same experiment is performed, with the change that with each send a new actor and message is allocated.
     740This evaluates the cost of message sends in the other common actor pattern where actors and message are created on the fly as the actor program tackles a workload of variable or unknown size.
     741Since dynamic sends are more expensive, this benchmark repeats the actor/message creation and send 20M times (\uC, \CFA), or 2M times (Akka, CAF, ProtoActor), to give an appropriate benchmark duration.
     742
     743The results from the static/dynamic send benchmarks are shown in Figures~\ref{t:StaticActorMessagePerformance} and \ref{t:DynamicActorMessagePerformance} respectively.
     744\CFA leads the charts in both benchmarks, largely due to the copy queue removing the majority of the envelope allocations.
     745In the static send benchmark all systems except CAF have static send costs that are in the same ballpark, only varying by ~70ns.
     746In the dynamic send benchmark all systems experience slower message sends, as expected due to the extra allocations.
     747However,  Akka and ProtoActor, slow down by a more significant margin than the \uC and \CFA.
     748This is likely a result of Akka and ProtoActor's garbage collection, which can suffer from hits in performance for allocation heavy workloads, whereas \uC and \CFA have explicit allocation/deallocation.
    427749
    428750\subsection{Work Stealing}
    429 \CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}. In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing.
     751\CFA's actor system has a work stealing mechanism which uses the longest victim heuristic, introduced in Section~ref{s:victimSelect}.
     752In this performance section, \CFA with the longest victim heuristic is compared with other actor systems on the benchmark suite, and is separately compared with vanilla non-stealing \CFA and \CFA with randomized work stealing.
    430753
    431754\begin{figure}
    … …  
    463786\end{figure}
    464787
    465 There are two benchmarks in which \CFA's work stealing is solely evaluated. The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing. The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA. The balance benchmarks adversarily takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores. The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds. The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core). Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads. In the balance-multi case the ideal speedup is 0.5. Note that in the balance-one benchmark the workload is fixed so decreasing runtime is expected. In the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected.
    466 
    467 On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics. On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim. This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing. Additionally, a performance cost can be observed when hyperthreading kicks in in Figure~\ref{f:BalanceMultiIntel}.
    468 
    469 In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache. On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading. Note that the non stealing variation of balance-one will slow down marginally as the cores increase due to having to create more dummy actors on the inactive cores during startup.
     788There are two benchmarks in which \CFA's work stealing is solely evaluated.
     789The main goal of introducing work stealing to \CFA's actor system is to eliminate the pathological unbalanced cases that can present themselves in a system without some form of load balancing.
     790The following two microbenchmarks construct two such pathological cases, and compare the work stealing variations of \CFA.
     791The balance benchmarks adversarily takes advantage of the round robin assignment of actors to load all actors that will do work on specific cores and create 'dummy' actors that terminate after a single message send on all other cores.
     792The workload on the loaded cores is the same as the executor benchmark described in \ref{s:executorPerf}, but with fewer rounds.
     793The balance-one benchmark loads all the work on a single core, whereas the balance-multi loads all the work on half the cores (every other core).
     794Given this layout, one expects the ideal speedup of work stealing in the balance-one case to be $N / N - 1$ where $N$ is the number of threads.
     795In the balance-multi case the ideal speedup is 0.5.
     796Note that in the balance-one benchmark the workload is fixed so decreasing runtime is expected.
     797In the balance-multi experiment, the workload increases with the number of cores so an increasing or constant runtime is expected.
     798
     799On both balance microbenchmarks slightly less than ideal speedup compared to the non stealing variation is achieved by both the random and longest victim stealing heuristics.
     800On the balance-multi benchmark \ref{f:BalanceMultiAMD},\ref{f:BalanceMultiIntel} the random heuristic outperforms the longest victim.
     801This is likely a result of the longest victim heuristic having a higher stealing cost as it needs to maintain timestamps and look at all timestamps before stealing.
     802Additionally, a performance cost can be observed when hyperthreading kicks in in Figure~\ref{f:BalanceMultiIntel}.
     803
     804In the balance-one benchmark on AMD \ref{f:BalanceOneAMD}, the performance bottoms out at 32 cores onwards likely due to the amount of work becoming less than the cost to steal it and move it across cores and cache.
     805On Intel \ref{f:BalanceOneIntel}, above 32 cores the performance gets worse for all variants due to hyperthreading.
     806Note that the non stealing variation of balance-one will slow down marginally as the cores increase due to having to create more dummy actors on the inactive cores during startup.
    470807
    471808\subsection{Executor}\label{s:executorPerf}
    472 The microbenchmarks in this section are designed to stress the executor. The executor is the scheduler of an actor system and is responsible for organizing the interaction of worker threads to service the needs of a workload. In the executor benchmark, 40'000 actors are created and assigned a group. Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group. Each time an actor completes all their sends and receives, they are done a round. After all groups have completed 400 rounds the system terminates. This microbenchmark is designed to flood the executor with a large number of messages flowing between actors. Given there is no work associated with each message, other than sending more messages, the intended bottleneck of this experiment is the executor message send process.
     809The microbenchmarks in this section are designed to stress the executor.
     810The executor is the scheduler of an actor system and is responsible for organizing the interaction of worker threads to service the needs of a workload.
     811In the executor benchmark, 40'000 actors are created and assigned a group.
     812Each group of actors is a group of 100 actors who send and receive 100 messages from all other actors in their group.
     813Each time an actor completes all their sends and receives, they are done a round.
     814After all groups have completed 400 rounds the system terminates.
     815This microbenchmark is designed to flood the executor with a large number of messages flowing between actors.
     816Given there is no work associated with each message, other than sending more messages, the intended bottleneck of this experiment is the executor message send process.
    473817
    474818\begin{figure}
    … …  
    489833\end{figure}
    490834
    491 The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers. The difference in runtime between \uC and \CFA is largely due to the usage of the copy queue described in Section~\ref{s:copyQueue}. The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator. Additionally, due to the static typing in \CFA's actor system, it is able to get rid of expensive dynamic casts that occur in \uC to disciminate messages by type. Note that dynamic casts are ususally not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
     835The results of the executor benchmark in Figures~\ref{f:ExecutorIntel} and \ref{f:ExecutorAMD} show \CFA with the lowest runtime relative to its peers.
     836The difference in runtime between \uC and \CFA is largely due to the usage of the copy queue described in Section~\ref{s:copyQueue}.
     837The copy queue both reduces and consolidates allocations, heavily reducing contention on the memory allocator.
     838Additionally, due to the static typing in \CFA's actor system, it is able to get rid of expensive dynamic casts that occur in \uC to disciminate messages by type.
     839Note that dynamic casts are ususally not very expensive, but relative to the high performance of the rest of the implementation of the \uC actor system, the cost is significant.
    492840
    493841\begin{figure}
    … …  
    523871\end{figure}
    524872
    525 The repeat microbenchmark also evaluates the executor. It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client. After this scatter and gather repeats 200 times the benchmark terminates. The messages from the servers to the client will likely all come in on the same queue, resulting in high contention. As such this benchmark will not scale with the number of processors, since more processors will result in higher contention. In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark. One factor in this result is that the contention on the queues poses a significant bottleneck. As such the gains from using the copy queue are much less apparent.
     873The repeat microbenchmark also evaluates the executor.
     874It stresses the executor's ability to withstand contention on queues, as it repeatedly fans out messages from a single client to 100000 servers who then all respond to the client.
     875After this scatter and gather repeats 200 times the benchmark terminates.
     876The messages from the servers to the client will likely all come in on the same queue, resulting in high contention.
     877As such this benchmark will not scale with the number of processors, since more processors will result in higher contention.
     878In Figure~\ref{f:RepeatAMD} we can see that \CFA performs well compared to \uC, however by less of a margin than the executor benchmark.
     879One factor in this result is that the contention on the queues poses a significant bottleneck.
     880As such the gains from using the copy queue are much less apparent.
    526881
    527882\begin{figure}
    … …  
    541896
    542897In Figure~\ref{f:RepeatIntel} \uC and \CFA are very comparable.
    543 In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing. The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers. When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation. As such stealing the client can result in a hit in performance.
     898In comparison with the other systems \uC does well on the repeat benchmark since it does not have work stealing.
     899The client of this experiment is long running and maintains a lot of state, as it needs to know the handles of all the servers.
     900When stealing the client or its respective queue (in \CFA's inverted model), moving the client incurs a high cost due to cache invalidation.
     901As such stealing the client can result in a hit in performance.
     902
    544903This result is shown in Figure~\ref{f:cfaRepeatAMD} and \ref{f:cfaRepeatIntel} where the no-stealing version of \CFA performs better than both stealing variations.
    545 In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing). The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager.
    546 In both the executor and the repeat benchmark CAF performs poorly. It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal. This results in poor performance in benchmarks with small messages containing little work per message. On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster. This hypothesis stems from experimentation with \CFA. CAF uses a randomized work stealing heuristic. In \CFA if the system is tuned so that it steals work much more eagerly with a randomized it was able to replicate the results that CAF achieves in the matrix benchmark, but this tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message.
     904In particular on the Intel machine in Figure~\ref{f:cfaRepeatIntel}, the cost of stealing is higher, which can be seen in the vertical shift of Akka, CAF and CFA results in Figure~\ref{f:RepeatIntel} (\uC and ProtoActor do not have work stealing).
     905The shift for CAF is particularly large, which further supports the hypothesis that CAF's work stealing is particularly eager.
     906In both the executor and the repeat benchmark CAF performs poorly.
     907It is hypothesized that CAF has an aggressive work stealing algorithm, that eagerly attempts to steal.
     908This results in poor performance in benchmarks with small messages containing little work per message.
     909On the other hand, in \ref{f:MatrixAMD} CAF performs much better since each message has a large amount of work, and few messages are sent, so the eager work stealing allows for the clean up of loose ends to occur faster.
     910This hypothesis stems from experimentation with \CFA.
     911CAF uses a randomized work stealing heuristic.
     912In \CFA if the system is tuned so that it steals work much more eagerly with a randomized it was able to replicate the results that CAF achieves in the matrix benchmark, but this tuning performed much worse on all other microbenchmarks that we present, since they all perform a small amount of work per message.
    547913
    548914\begin{table}[t]
    … …  
    562928\end{table}
    563929
    564 Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores. \CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF. This is a result of the copy queue data structure, as it will overallocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
     930Figure~\ref{t:ExecutorMemory} shows the high memory watermark of the actor systems when running the executor benchmark on 48 cores.
     931\CFA has a high watermark relative to the other non-garbage collected systems \uC, and CAF.
     932This is a result of the copy queue data structure, as it will overallocate storage and not clean up eagerly, whereas the per envelope allocations will always allocate exactly the amount of storage needed.
    565933
    566934\subsection{Matrix Multiply}
    567 The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices. The majority of the computation in this benchmark involves computing the final matrix, so this benchmark stresses the actor systems' ability to have actors run work, rather than stressing the executor or message sending system.
     935The matrix benchmark evaluates the actor systems in a practical application, where actors concurrently multiplies two matrices.
     936The majority of the computation in this benchmark involves computing the final matrix, so this benchmark stresses the actor systems' ability to have actors run work, rather than stressing the executor or message sending system.
    568937
    569938Given $Z_{m,r} = X_{m,n} \cdot Y_{n,r}$, the matrix multiply is defined as:
    … …  
    572941\end{displaymath}
    573942
    574 The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size. An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$.
    575 
    576 Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments. In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead og \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading. As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation. In Figures~\ref{f:cfaMatrixAMD} and \ref{f:cfaMatrixIntel} there is little negligible performance difference across \CFA stealing heuristics.
     943The benchmark uses input matrices $X$ and $Y$ that are both $3072$ by $3072$ in size.
     944An actor is made for each row of $X$ and is passed via message the information needed to calculate a row of the result matrix $Z$.
     945
     946
     947Given that the bottleneck of the benchmark is the computation of the result matrix, it follows that the results in Figures~\ref{f:MatrixAMD} and \ref{f:MatrixIntel} are clustered closer than other experiments.
     948In Figure~\ref{f:MatrixAMD} \uC and \CFA have identical performance and in Figure~\ref{f:MatrixIntel} \uC pulls ahead og \CFA after 24 cores likely due to costs associated with work stealing while hyperthreading.
     949As mentioned in \ref{s:executorPerf}, it is hypothesized that CAF performs better in this benchmark compared to others due to its eager work stealing implementation.
     950In Figures~\ref{f:cfaMatrixAMD} and \ref{f:cfaMatrixIntel} there is little negligible performance difference across \CFA stealing heuristics.
    577951
    578952\begin{figure}

  • doc/theses/colby_parsons_MMAth/text/channels.tex

    rfa6ca1a r34b6a7b6  
    55% ======================================================================
    66
    7 Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data. Channels are a concurrent language feature used to perform message passing concurrency, a model of concurrency where threads communicate by sending data as messages, and synchronizing via the message passing mechanism. This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state. Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both. Channels as a programming language feature has been popularized in recent years due to the language Go, which encourages the use of channels as its fundamental concurrent feature.
     7Channels were first introduced by Hoare in his paper Communicating Sequentual Processes~\cite{Hoare78}, where he proposes a concurrent language that communicates across processes using input/output channels to send data.
     8Channels are a concurrent language feature used to perform message passing concurrency, a model of concurrency where threads communicate by sending data as messages, and synchronizing via the message passing mechanism.
     9This is an alternative to shared memory concurrency, where threads can communicate directly by changing shared memory state.
     10Most modern concurrent programming languages do not subscribe to just one style of communication between threads, and provide features that support both.
     11Channels as a programming language feature has been popularized in recent years due to the language Go, which encourages the use of channels as its fundamental concurrent feature.
    812
    913\section{Producer-Consumer Problem}
    10 Most channels in modern programming languages are built on top of a shared memory buffer. While it is possible to create a channel that contains an unbounded buffer, most implementations opt to only support a fixed size channel, where the size is given at the time of channel creation. This turns the implementation of a channel into the producer-consumer problem. The producer-consumer problem, also known as the bounded buffer problem, was introduced by Dijkstra in his book Cooperating Sequential Processes\cite{Dijkstra65}. In the problem threads interact with the buffer in two ways, either consuming values by removing them from the buffer, or producing values and inserting them in the buffer. The buffer needs to be protected from concurrent access since each item in the buffer should only be produced and consumed once. Additionally, a consumer can only remove from a non-empty buffer and a producer can only insert into a non-full buffer.
     14Most channels in modern programming languages are built on top of a shared memory buffer.
     15While it is possible to create a channel that contains an unbounded buffer, most implementations opt to only support a fixed size channel, where the size is given at the time of channel creation.
     16This turns the implementation of a channel into the producer-consumer problem.
     17The producer-consumer problem, also known as the bounded buffer problem, was introduced by Dijkstra in his book Cooperating Sequential Processes\cite{Dijkstra65}.
     18In the problem threads interact with the buffer in two ways, either consuming values by removing them from the buffer, or producing values and inserting them in the buffer.
     19The buffer needs to be protected from concurrent access since each item in the buffer should only be produced and consumed once.
     20Additionally, a consumer can only remove from a non-empty buffer and a producer can only insert into a non-full buffer.
    1121
    1222\section{First-Come First-Served}
    13 The channel implementations that will be discussed are \newterm{First-Come First-Served} (FCFS). This term was defined by Lamport~\cite{Lamport74}. FCFS is defined in relation to a \newterm{doorway}~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established. Given this doorway, a critical section is said to be FCFS, if threads access the shared resource in the order they proceed through the doorway. FCFS is a fairness property which prevents unequal access to the shared resource and prevents starvation, however it can come at a cost. Implementing an algorithm with FCFS can lead to \newterm{double blocking}, where entering threads may need to block to allow other threads to proceed first, resulting in blocking both inside and outside the doorway. As such algorithms that are not FCFS may be more performant but that performance comes with the downside of likely introducing starvation and unfairness.
     23The channel implementations that will be discussed are \gls{fcfs}.
     24This term was defined by Lamport~\cite{Lamport74}.
     25\gls{fcfs} is defined in relation to a doorway~\cite[p.~330]{Lamport86II}, which is the point at which an ordering among threads can be established.
     26Given this doorway, a critical section is said to be \gls{fcfs}, if threads access the shared resource in the order they proceed through the doorway.
     27\gls{fcfs} is a fairness property which prevents unequal access to the shared resource and prevents starvation, however it can come at a cost.
     28Implementing an algorithm with \gls{fcfs} can lead to double blocking, where entering threads may need to block to allow other threads to proceed first, resulting in blocking both inside and outside the doorway.
     29As such algorithms that are not \gls{fcfs} may be more performant but that performance comes with the downside of likely introducing starvation and unfairness.
    1430
    1531\section{Channel Implementation}
    16 The channel implementation in \CFA is a near carbon copy of the Go implementation. Experimentation was conducted that varied the producer-consumer problem algorithm and lock type used inside the channel. With the exception of non-FCFS algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation. As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.
     32The channel implementation in \CFA is a near carbon copy of the Go implementation.
     33Experimentation was conducted that varied the producer-consumer problem algorithm and lock type used inside the channel.
     34With the exception of non-\gls{fcfs} algorithms, no algorithm or lock usage in the channel implementation was found to be consistently more performant that Go's choice of algorithm and lock implementation.
     35As such the research contributions added by \CFA's channel implementation lie in the realm of safety and productivity features.
    1736
    1837\section{Safety and Productivity}
    19 Channels in \CFA come with safety and productivity features to aid users. The features include the following.
     38Channels in \CFA come with safety and productivity features to aid users.
     39The features include the following.
    2040
    2141\begin{itemize}
    22 \item Toggle-able statistic collection on channel behvaiour that counts channel operations, and the number of the operations that block. Tracking blocking operations helps users tune their channel size or channel usage when the channel is used for buffering, where the aim is to have as few blocking operations as possible.
    23 \item Deadlock detection on deallocation of the channel. If any threads are blocked inside the channel when it terminates it is detected and informs the user, as this would cause a deadlock.
    24 \item A \code{flush} routine that delivers copies of an element to all waiting consumers, flushing the buffer. Programmers can use this to easily to broadcast data to multiple consumers. Additionally, the \code{flush} routine is more performant then looping around the \code{insert} operation since it can deliver the elements without having to reaquire mutual exclusion for each element sent.
     42\item Toggle-able statistic collection on channel behvaiour that counts channel operations, and the number of the operations that block.
     43Tracking blocking operations helps users tune their channel size or channel usage when the channel is used for buffering, where the aim is to have as few blocking operations as possible.
     44\item Deadlock detection on deallocation of the channel.
     45If any threads are blocked inside the channel when it terminates it is detected and informs the user, as this would cause a deadlock.
     46\item A \code{flush} routine that delivers copies of an element to all waiting consumers, flushing the buffer.
     47Programmers can use this to easily to broadcast data to multiple consumers.
     48Additionally, the \code{flush} routine is more performant then looping around the \code{insert} operation since it can deliver the elements without having to reaquire mutual exclusion for each element sent.
    2549\end{itemize}
    2650
    27 The other safety and productivity feature of \CFA channels deals with concurrent termination. Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed. The difficulty of graceful termination often arises from the usage of synchronization primitives which need to be handled carefully during shutdown. It is easy to deadlock during termination if threads are left behind on synchronization primitives. Additionally, most synchronization primitives are prone to time-of-check to time-of-use (TOCTOU) issues where there is race between one thread checking the state of a concurrent object and another thread changing the state. TOCTOU issues with synchronization primitives often involve a race between one thread checking the primitive for blocked threads and another thread blocking on it. Channels are a particularly hard synchronization primitive to terminate since both sending and receiving off a channel can block. Thus, improperly handled TOCTOU issues with channels often result in deadlocks as threads trying to perform the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
     51The other safety and productivity feature of \CFA channels deals with concurrent termination.
     52Terminating concurrent programs is often one of the most difficult parts of writing concurrent code, particularly if graceful termination is needed.
     53The difficulty of graceful termination often arises from the usage of synchronization primitives which need to be handled carefully during shutdown.
     54It is easy to deadlock during termination if threads are left behind on synchronization primitives.
     55Additionally, most synchronization primitives are prone to \gls{toctou} issues where there is race between one thread checking the state of a concurrent object and another thread changing the state.
     56\gls{toctou} issues with synchronization primitives often involve a race between one thread checking the primitive for blocked threads and another thread blocking on it.
     57Channels are a particularly hard synchronization primitive to terminate since both sending and receiving off a channel can block.
     58Thus, improperly handled \gls{toctou} issues with channels often result in deadlocks as threads trying to perform the termination may end up unexpectedly blocking in their attempt to help other threads exit the system.
    2859
    2960% C_TODO: add reference to select chapter, add citation to go channels info
    30 Go channels provide a set of tools to help with concurrent shutdown. Channels in Go have a \code{close} operation and a \code{select} statement that both can be used to help threads terminate. The \code{select} statement will be discussed in \ref{}, where \CFA's \code{waituntil} statement will be compared with the Go \code{select} statement. The \code{close} operation on a channel in Go changes the state of the channel. When a channel is closed, sends to the channel will panic and additional calls to \code{close} will panic. Receives are handled differently where receivers will never block on a closed channel and will continue to remove elements from the channel. Once a channel is empty, receivers can continue to remove elements, but will receive the zero-value version of the element type. To aid in avoiding unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements. These design choices for Go channels enforce a specific interaction style with channels during termination, where careful thought is needed to ensure that additional \code{close} calls don't occur and that no sends occur after channels are closed. These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them. If errors need to occur in Go, return codes are used to pass error information where they are needed. Note that panics in Go can be caught, but it is not considered an idiomatic way to write Go programs.
    31 
    32 While Go's channel closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired. Since both closing and sending panic, once a channel is closed, a user often has to synchronize the senders to a channel before the channel can be closed to avoid panics. However, in doing so it renders the \code{close} operation nearly useless, as the only utilities it provides are the ability to ensure that receivers no longer block on the channel, and will receive zero-valued elements. This can be useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is preferred, then \code{close} only provides its non-blocking feature. To avoid TOCTOU issues during shutdown, a busy wait with a \code{select} statement is often used to add or remove elements from a channel. Due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
    33 
    34 In \CFA, exception handling is an encouraged paradigm and has full language support \cite{}.
    35 % \cite{Beach21}. TODO: this citation breaks when compiled. Need to fix and insert above
     61Go channels provide a set of tools to help with concurrent shutdown.
     62Channels in Go have a \code{close} operation and a \code{select} statement that both can be used to help threads terminate.
     63The \code{select} statement will be discussed in \ref{}, where \CFA's \code{waituntil} statement will be compared with the Go \code{select} statement.
     64The \code{close} operation on a channel in Go changes the state of the channel.
     65When a channel is closed, sends to the channel will panic and additional calls to \code{close} will panic.
     66Receives are handled differently where receivers will never block on a closed channel and will continue to remove elements from the channel.
     67Once a channel is empty, receivers can continue to remove elements, but will receive the zero-value version of the element type.
     68To aid in avoiding unwanted zero-value elements, Go provides the ability to iterate over a closed channel to remove the remaining elements.
     69These design choices for Go channels enforce a specific interaction style with channels during termination, where careful thought is needed to ensure that additional \code{close} calls don't occur and that no sends occur after channels are closed.
     70These design choices fit Go's paradigm of error management, where users are expected to explicitly check for errors, rather than letting errors occur and catching them.
     71If errors need to occur in Go, return codes are used to pass error information where they are needed.
     72Note that panics in Go can be caught, but it is not considered an idiomatic way to write Go programs.
     73
     74While Go's channel closing semantics are powerful enough to perform any concurrent termination needed by a program, their lack of ease of use leaves much to be desired.
     75Since both closing and sending panic, once a channel is closed, a user often has to synchronize the senders to a channel before the channel can be closed to avoid panics.
     76However, in doing so it renders the \code{close} operation nearly useless, as the only utilities it provides are the ability to ensure that receivers no longer block on the channel, and will receive zero-valued elements.
     77This can be useful if the zero-typed element is recognized as a sentinel value, but if another sentinel value is preferred, then \code{close} only provides its non-blocking feature.
     78To avoid \gls{toctou} issues during shutdown, a busy wait with a \code{select} statement is often used to add or remove elements from a channel.
     79Due to Go's asymmetric approach to channel shutdown, separate synchronization between producers and consumers of a channel has to occur during shutdown.
     80
     81In \CFA, exception handling is an encouraged paradigm and has full language support \cite{Beach21}.
    3682As such \CFA uses an exception based approach to channel shutdown that is symmetric for both producers and consumers, and supports graceful shutdown.Exceptions in \CFA support both termination and resumption.Termination exceptions operate in the same way as exceptions seen in many popular programming languages such as \CC, Python and Java.
    3783Resumption exceptions are a style of exception that when caught run the corresponding catch block in the same way that termination exceptions do.
    38 The difference between the exception handling mechanisms arises after the exception is handled. In termination handling, the control flow continues into the code following the catch after the exception is handled. In resumption handling, the control flow returns to the site of the \code{throw}, allowing the control to continue where it left off. Note that in resumption, since control can return to the point of error propagation, the stack is not unwound during resumption propagation. In \CFA if a resumption is not handled, it is reraised as a termination. This mechanism can be used to create a flexible and robust termination system for channels.
    39 
    40 When a channel in \CFA is closed, all subsequent calls to the channel will throw a resumption exception at the caller. If the resumption is handled, then the caller will proceed to attempt to complete their operation. If the resumption is not handled it is then rethrown as a termination exception. Or, if the resumption is handled, but the subsequent attempt at an operation would block, a termination exception is thrown. These termination exceptions allow for non-local transfer that can be used to great effect to eagerly and gracefully shut down a thread. When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them. The resumption exception, \code{channel_closed}, has a couple fields to aid in handling the exception. The exception contains a pointer to the channel it was thrown from, and a pointer to an element. In exceptions thrown from remove the element pointer will be null. In the case of insert the element pointer points to the element that the thread attempted to insert. This element pointer allows the handler to know which operation failed and also allows the element to not be lost on a failed insert since it can be moved elsewhere in the handler. Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based which channel and operation failed. Exception handlers in \CFA have an optional predicate after the exception type which can be used to optionally trigger or skip handlers based on the content of an exception. It is worth mentioning that the approach of exceptions for termination may incur a larger performance cost during termination that the approach used in Go. This should not be an issue, since termination is rarely an fast-path of an application and ensuring that termination can be implemented correctly with ease is the aim of the exception approach.
    41 
    42 To highlight the differences between \CFA's and Go's close semantics, an example program is presented. The program is a barrier implemented using two channels shown in Listings~\ref{l:cfa_chan_bar} and \ref{l:go_chan_bar}. Both of these exaples are implmented using \CFA syntax so that they can be easily compared. Listing~\ref{l:go_chan_bar} uses go-style channel close semantics and Listing~\ref{l:cfa_chan_bar} uses \CFA close semantics. In this problem it is infeasible to use the Go \code{close} call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable. As such in Listing~\ref{l:go_chan_bar} to implement a flush routine for the buffer, a sentinel value of $-1$ has to be used to indicate to threads that they need to leave the barrier. This sentinel value has to be checked at two points. Furthermore, an additional flag \code{done} is needed to communicate to threads once they have left the barrier that they are done. This use of an additional flag or communication method is common in Go channel shutdown code, since to avoid panics on a channel, the shutdown of a channel often has to be communicated with threads before it occurs. In the \CFA version~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, which informs the threads that they must terminate. This avoids the need to use a separate communication method other than the barrier, and avoids extra conditional checks on the fast path of the barrier implementation. Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
     84The difference between the exception handling mechanisms arises after the exception is handled.
     85In termination handling, the control flow continues into the code following the catch after the exception is handled.
     86In resumption handling, the control flow returns to the site of the \code{throw}, allowing the control to continue where it left off.
     87Note that in resumption, since control can return to the point of error propagation, the stack is not unwound during resumption propagation.
     88In \CFA if a resumption is not handled, it is reraised as a termination.
     89This mechanism can be used to create a flexible and robust termination system for channels.
     90
     91When a channel in \CFA is closed, all subsequent calls to the channel will throw a resumption exception at the caller.
     92If the resumption is handled, then the caller will proceed to attempt to complete their operation.
     93If the resumption is not handled it is then rethrown as a termination exception.
     94Or, if the resumption is handled, but the subsequent attempt at an operation would block, a termination exception is thrown.
     95These termination exceptions allow for non-local transfer that can be used to great effect to eagerly and gracefully shut down a thread.
     96When a channel is closed, if there are any blocked producers or consumers inside the channel, they are woken up and also have a resumption thrown at them.
     97The resumption exception, \code{channel_closed}, has a couple fields to aid in handling the exception.
     98The exception contains a pointer to the channel it was thrown from, and a pointer to an element.
     99In exceptions thrown from remove the element pointer will be null.
     100In the case of insert the element pointer points to the element that the thread attempted to insert.
     101This element pointer allows the handler to know which operation failed and also allows the element to not be lost on a failed insert since it can be moved elsewhere in the handler.
     102Furthermore, due to \CFA's powerful exception system, this data can be used to choose handlers based which channel and operation failed.
     103Exception handlers in \CFA have an optional predicate after the exception type which can be used to optionally trigger or skip handlers based on the content of an exception.
     104It is worth mentioning that the approach of exceptions for termination may incur a larger performance cost during termination that the approach used in Go.
     105This should not be an issue, since termination is rarely an fast-path of an application and ensuring that termination can be implemented correctly with ease is the aim of the exception approach.
     106
     107To highlight the differences between \CFA's and Go's close semantics, an example program is presented.
     108The program is a barrier implemented using two channels shown in Listings~\ref{l:cfa_chan_bar} and \ref{l:go_chan_bar}.
     109Both of these exaples are implmented using \CFA syntax so that they can be easily compared.
     110Listing~\ref{l:go_chan_bar} uses go-style channel close semantics and Listing~\ref{l:cfa_chan_bar} uses \CFA close semantics.
     111In this problem it is infeasible to use the Go \code{close} call since all tasks are both potentially producers and consumers, causing panics on close to be unavoidable.
     112As such in Listing~\ref{l:go_chan_bar} to implement a flush routine for the buffer, a sentinel value of $-1$ has to be used to indicate to threads that they need to leave the barrier.
     113This sentinel value has to be checked at two points.
     114Furthermore, an additional flag \code{done} is needed to communicate to threads once they have left the barrier that they are done.
     115This use of an additional flag or communication method is common in Go channel shutdown code, since to avoid panics on a channel, the shutdown of a channel often has to be communicated with threads before it occurs.
     116In the \CFA version~\ref{l:cfa_chan_bar}, the barrier shutdown results in an exception being thrown at threads operating on it, which informs the threads that they must terminate.
     117This avoids the need to use a separate communication method other than the barrier, and avoids extra conditional checks on the fast path of the barrier implementation.
     118Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
    43119
    44120\begin{cfacode}[tabsize=3,caption={\CFA channel barrier termination},label={l:cfa_chan_bar}]
    … …  
    163239\end{cfacode}
    164240
    165 In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used. This program uses resumption in the \code{Consumer} thread main to ensure that all elements in the channel are removed before the consumer thread terminates. The producer only has a \code{catch} so the moment it receives an exception it terminates, whereas the consumer will continue to remove from the closed channel via handling resumptions until the buffer is empty, which then throws a termination exception. If the same program was implemented in Go it would require explicit synchronization with both producers and consumers by some mechanism outside the channel to ensure that all elements were removed before task termination.
     241In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used.
     242This program uses resumption in the \code{Consumer} thread main to ensure that all elements in the channel are removed before the consumer thread terminates.
     243The producer only has a \code{catch} so the moment it receives an exception it terminates, whereas the consumer will continue to remove from the closed channel via handling resumptions until the buffer is empty, which then throws a termination exception.
     244If the same program was implemented in Go it would require explicit synchronization with both producers and consumers by some mechanism outside the channel to ensure that all elements were removed before task termination.
    166245
    167246\begin{cfacode}[tabsize=3,caption={\CFA channel resumption usage},label={l:cfa_resume}]
    … …  
    205284\section{Performance}
    206285
    207 Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show that the performance of the two implementations are comparable. One microbenchmark is conducted to compare Go and \CFA. The benchmark is a ten second experiment where producers and consumers operate on a channel in parallel and throughput is measured. The number of cores is varied to measure how throughtput scales. The cores are divided equally between producers and consumers, with one producer or consumer owning each core. The results of the benchmark are shown in Figure~\ref{f:chanPerf}. The performance of Go and \CFA channels on this microbenchmark is comparable. Note, it is expected for the performance to decline as the number of cores increases as the channel operations all occur in a critical section so an increase in cores results in higher contention with no increase in parallelism.
     286Given that the base implementation of the \CFA channels is very similar to the Go implementation, this section aims to show that the performance of the two implementations are comparable.
     287One microbenchmark is conducted to compare Go and \CFA.
     288The benchmark is a ten second experiment where producers and consumers operate on a channel in parallel and throughput is measured.
     289The number of cores is varied to measure how throughtput scales.
     290The cores are divided equally between producers and consumers, with one producer or consumer owning each core.
     291The results of the benchmark are shown in Figure~\ref{f:chanPerf}.
     292The performance of Go and \CFA channels on this microbenchmark is comparable.
     293Note, it is expected for the performance to decline as the number of cores increases as the channel operations all occur in a critical section so an increase in cores results in higher contention with no increase in parallelism.
    208294
    209295

  • doc/theses/colby_parsons_MMAth/text/frontpgs.tex

    rfa6ca1a r34b6a7b6  
    11% T I T L E   P A G E
    22% -------------------
    3 % Last updated May 24, 2011, by Stephen Carr, IST-Client Services
     3% Last updated August 16, 2022, by IST-Client Services
    44% The title page is counted as page `i' but we need to suppress the
    5 % page number.  We also don't want any headers or footers.
     5% page number. Also, we don't want any headers or footers.
    66\pagestyle{empty}
    77\pagenumbering{roman}
    … …  
    3030        \normalsize
    3131        A thesis \\
    32         presented to the University of Waterloo \\
     32        presented to the University of Waterloo \\ 
    3333        in fulfillment of the \\
    3434        thesis requirement for the degree of \\
    … …  
    5353\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
    5454% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.
    55 
    56 
     55\phantomsection    % allows hyperref to link to the correct page
    5756
    5857% D E C L A R A T I O N   P A G E
    5958% -------------------------------
    60   % The following is the sample Delaration Page as provided by the GSO
     59  % The following is a sample Declaration Page as provided by the GSO
    6160  % December 13th, 2006.  It is designed for an electronic thesis.
     61 \addcontentsline{toc}{chapter}{Author's Declaration}
     62 \begin{center}\textbf{Author's Declaration}\end{center}
     63 
     64 \noindent
     65I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
     66
     67  \bigskip
     68 
    6269  \noindent
    63   I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
    64   \bigskip
    65 
    66   \noindent
    67   I understand that my thesis may be made electronically available to the public.
     70I understand that my thesis may be made electronically available to the public.
    6871
    6972\cleardoublepage
    70 %\newpage
     73\phantomsection    % allows hyperref to link to the correct page
    7174
    7275% A B S T R A C T
    7376% ---------------
    74 
     77\addcontentsline{toc}{chapter}{Abstract}
    7578\begin{center}\textbf{Abstract}\end{center}
    7679
    77 Concurrent programs are notoriously hard to program and even harder to debug. Furthermore concurrent programs must be performant, as the introduction of concurrency into a program is often done to achieve some form of speedup. This thesis presents a suite of high level concurrent language features in \CFA, all of which are implemented with the aim of improving the performance, productivity, and safety of concurrent programs. \CFA is a non object-oriented programming language that extends C. The foundation for concurrency in \CFA was laid by Thierry Delisle, who implemented coroutines, user-level threads, and monitors\cite{Delisle18}. This thesis builds upon that groundwork and introduces a suite of concurrent features as its main contribution. The features include Go-like channels, mutex statements (similar to \CC scoped locks or Java synchronized statement), an actor system, and a Go-like select statement. The root idea behind these features are not new, but the \CFA implementations improve upon the original ideas in performance, productivity, and safety.
     80Concurrent programs are notoriously hard to program and even harder to debug. Furthermore concurrent programs must be performant, as the introduction of concurrency into a program is often done to achieve some form of speedup.
     81
     82This thesis presents a suite of high-level concurrent-language features in the new programming language \CFA, all of which are implemented with the aim of improving the performance, productivity, and safety of concurrent programs. \CFA is a non object-oriented programming language that extends C. The foundation for concurrency in \CFA was laid by Thierry Delisle~\cite{Delisle18}, who implemented coroutines, user-level threads, and monitors. This thesis builds upon that work and introduces a suite of new concurrent features as its main contribution. The features include Go-like channels, mutex statements (similar to \CC scoped locks or Java synchronized statement), an actor system, and a Go-like select statement. The root ideas behind these features are not new, but the \CFA implementations extends the original ideas in performance, productivity, and safety.
    7883
    7984\cleardoublepage
    80 %\newpage
     85\phantomsection    % allows hyperref to link to the correct page
    8186
    8287% A C K N O W L E D G E M E N T S
    8388% -------------------------------
    84 
     89\addcontentsline{toc}{chapter}{Acknowledgements}
    8590\begin{center}\textbf{Acknowledgements}\end{center}
    8691
    … …  
    99104\noindent
    100105Finally, this work could not have happened without the financial support of David R. Cheriton School of Computer Science and the corporate partnership with Huawei Ltd.
    101 
    102106\cleardoublepage
    103 %\newpage
     107\phantomsection    % allows hyperref to link to the correct page
    104108
    105109% % D E D I C A T I O N
    106110% % -------------------
    107 
     111% \addcontentsline{toc}{chapter}{Dedication}
    108112% \begin{center}\textbf{Dedication}\end{center}
    109113
    110 %
     114% This is dedicated to the one I love.
    111115% \cleardoublepage
    112 % %\newpage
     116% \phantomsection    % allows hyperref to link to the correct page
    113117
    114118% T A B L E   O F   C O N T E N T S
    … …  
    117121\tableofcontents
    118122\cleardoublepage
    119 \phantomsection
    120 %\newpage
     123\phantomsection    % allows hyperref to link to the correct page
     124
     125% L I S T   O F   F I G U R E S
     126% -----------------------------
     127\addcontentsline{toc}{chapter}{List of Figures}
     128\listoffigures
     129\cleardoublepage
     130\phantomsection         % allows hyperref to link to the correct page
    121131
    122132% L I S T   O F   T A B L E S
    … …  
    126136\cleardoublepage
    127137\phantomsection         % allows hyperref to link to the correct page
    128 %\newpage
    129138
    130 % L I S T   O F   F I G U R E S
    131 % -----------------------------
    132 \addcontentsline{toc}{chapter}{List of Figures}
    133 \listoffigures
     139% L I S T   O F   A B B R E V I A T I O N S
     140% ---------------------------
     141\renewcommand*{\abbreviationsname}{List of Abbreviations}
     142\printglossary[type=abbreviations]
    134143\cleardoublepage
    135144\phantomsection         % allows hyperref to link to the correct page
    136 %\newpage
    137145
    138 % L I S T   O F   L I S T I N G S
    139 % -----------------------------
    140 \addcontentsline{toc}{chapter}{List of Listings}
    141 \lstlistoflistings
    142 \cleardoublepage
    143 \phantomsection         % allows hyperref to link to the correct page
    144 %\newpage
     146% % L I S T   O F   S Y M B O L S
     147% % ---------------------------
     148% \printglossary[type=symbols]
     149% \cleardoublepage
     150% \phantomsection               % allows hyperref to link to the correct page
    145151
    146 % L I S T   O F   S Y M B O L S
    147 % -----------------------------
    148 % To include a Nomenclature section
    149 % \addcontentsline{toc}{chapter}{\textbf{Nomenclature}}
    150 % \renewcommand{\nomname}{Nomenclature}
    151 % \printglossary
    152 % \cleardoublepage
    153 % \phantomsection % allows hyperref to link to the correct page
    154 % \newpage
    155 
    156 % L I S T   O F   T A B L E S
    157 % -----------------------------
    158 \addcontentsline{toc}{chapter}{List of Acronyms}
    159 \printglossary[type=\acronymtype,title={List of Acronyms}]
    160 \cleardoublepage
    161 \phantomsection         % allows hyperref to link to the correct page
    162152
    163153% Change page numbering back to Arabic numerals

  • doc/theses/colby_parsons_MMAth/text/intro.tex

    rfa6ca1a r34b6a7b6  
    11% ======================================================================
    22% ======================================================================
    3 \chapter{Introduction}\label{s:cfa}
     3\chapter{Introduction}\label{s:intro}
    44% ======================================================================
    55% ======================================================================
    66
    7 Concurrent programs are the wild west of programming. Determinism and simple ordering of program operations go out the window. To seize the reins and write performant and safe concurrent code, concurrent language features are needed. Like any other craftsmen, programmers are only as good as their tools, and concurrent tooling and features are no exception. This thesis presents a set of concurrent features implemened in \CFA. These features aim to improve the performance of concurrent programs, aid in writing safe programs, and assist user productivity by improving the ease of concurrent programming. The groundwork for concurrent features in \CFA was implemented by Thierry Delisle, who contributed the threading system, coroutines, monitors and other tools\cite{Delisle18}. This thesis builds on top of that foundation by providing a suite of high-level concurrent features. These features include mutex statements, channels, an actor system and a waituntil statement. All of these features exist in other programming in some shape or form, however this thesis contributes upon the original ideas by improving performance, productivity, and safety.
     7Concurrent programs are the wild west of programming because determinism and simple ordering of program operations go out the window.
     8To seize the reins and write performant and safe concurrent code, high-level concurrent-language features are needed.
     9Like any other craftsmen, programmers are only as good as their tools, and concurrent tooling and features are no exception.
     10This thesis presents a set of concurrent features implemented in the new programming-language \CFA.
     11These features aim to improve the performance of concurrent programs, aid in writing safe programs, and assist user productivity by improving the ease of concurrent programming.
     12The groundwork for concurrent features in \CFA was implemented by Thierry Delisle~\cite{Delisle18}, who contributed the threading system, coroutines, monitors and other tools.
     13This thesis builds on top of that foundation by providing a suite of high-level concurrent features.
     14These features include mutex statements, channels, an actor system and a waituntil statement.
     15All of these features exist in other programming in some shape or form, however this thesis extends the original ideas by improving performance, productivity, and safety.

  • doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

    rfa6ca1a r34b6a7b6  
    55% ======================================================================
    66
    7 The mutex statement is a concurrent language feature that aims to support easy lock usage. The mutex statement is in the form of a clause and following statement, similar to a loop or conditional statement. In the clause the mutex statement accepts a number of \newterm{lockable} objects, and then locks them for the duration of the following statement. The locks are acquired in a deadlock free manner and released using RAII. The mutex statement provides an avenue for easy lock usage in the common case where locks are used to wrap a critical section. Additionally, it provides the safety guarantee of deadlock-freedom, both by acquiring the locks in a deadlock-free manner, and by ensuring that the locks release on error, or normal program execution via RAII.
     7The mutex statement is a concurrent language feature that aims to support easy lock usage.
     8The mutex statement is in the form of a clause and following statement, similar to a loop or conditional statement.
     9In the clause the mutex statement accepts a number of lockable objects, and then locks them for the duration of the following statement.
     10The locks are acquired in a deadlock free manner and released using \gls{raii}.
     11The mutex statement provides an avenue for easy lock usage in the common case where locks are used to wrap a critical section.
     12Additionally, it provides the safety guarantee of deadlock-freedom, both by acquiring the locks in a deadlock-free manner, and by ensuring that the locks release on error, or normal program execution via \gls{raii}.
    813
    914\begin{cfacode}[tabsize=3,caption={\CFA mutex statement usage},label={l:cfa_mutex_ex}]
    … …  
    1823
    1924\section{Other Languages}
    20 There are similar concepts to the mutex statement that exist in other languages. Java has a feature called a synchronized statement, which looks identical to \CFA's mutex statement, but it has some differences. The synchronized statement only accepts a single object in its clause. Any object can be passed to the synchronized statement in Java since all objects in Java are monitors, and the synchronized statement acquires that object's monitor. In \CC there is a feature in the standard library \code{<mutex>} header called scoped\_lock, which is also similar to the mutex statement. The scoped\_lock is a class that takes in any number of locks in its constructor, and acquires them in a deadlock-free manner. It then releases them when the scoped\_lock object is deallocated, thus using RAII. An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}.
     25There are similar concepts to the mutex statement that exist in other languages.
     26Java has a feature called a synchronized statement, which looks identical to \CFA's mutex statement, but it has some differences.
     27The synchronized statement only accepts a single object in its clause.
     28Any object can be passed to the synchronized statement in Java since all objects in Java are monitors, and the synchronized statement acquires that object's monitor.
     29In \CC there is a feature in the standard library \code{<mutex>} header called scoped\_lock, which is also similar to the mutex statement.
     30The scoped\_lock is a class that takes in any number of locks in its constructor, and acquires them in a deadlock-free manner.
     31It then releases them when the scoped\_lock object is deallocated, thus using \gls{raii}.
     32An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}.
    2133
    2234\begin{cppcode}[tabsize=3,caption={\CC scoped\_lock usage},label={l:cc_scoped_lock}]
    … …  
    2941
    3042\section{\CFA implementation}
    31 The \CFA mutex statement takes some ideas from both the Java and \CC features. The mutex statement can acquire more that one lock in a deadlock-free manner, and releases them via RAII like \CC, however the syntax is identical to the Java synchronized statement. This syntactic choice was made so that the body of the mutex statement is its own scope. Compared to the scoped\_lock, which relies on its enclosing scope, the mutex statement's introduced scope can provide visual clarity as to what code is being protected by the mutex statement, and where the mutual exclusion ends. \CFA's mutex statement and \CC's scoped\_lock both use parametric polymorphism to allow user defined types to work with the feature. \CFA's implementation requires types to support the routines \code{lock()} and \code{unlock()}, whereas \CC requires those routines, plus \code{try_lock()}. The scoped\_lock requires an additional routine since it differs from the mutex statement in how it implements deadlock avoidance.
     43The \CFA mutex statement takes some ideas from both the Java and \CC features.
     44The mutex statement can acquire more that one lock in a deadlock-free manner, and releases them via \gls{raii} like \CC, however the syntax is identical to the Java synchronized statement.
     45This syntactic choice was made so that the body of the mutex statement is its own scope.
     46Compared to the scoped\_lock, which relies on its enclosing scope, the mutex statement's introduced scope can provide visual clarity as to what code is being protected by the mutex statement, and where the mutual exclusion ends.
     47\CFA's mutex statement and \CC's scoped\_lock both use parametric polymorphism to allow user defined types to work with the feature.
     48\CFA's implementation requires types to support the routines \code{lock()} and \code{unlock()}, whereas \CC requires those routines, plus \code{try_lock()}.
     49The scoped\_lock requires an additional routine since it differs from the mutex statement in how it implements deadlock avoidance.
    3250
    33 The parametric polymorphism allows for locking to be defined for types that may want convenient mutual exclusion. An example of one such use case in \CFA is \code{sout}. The output stream in \CFA is called \code{sout}, and functions similarly to \CC's \code{cout}. \code{sout} has routines that satisfy the mutex statement trait, so the mutex statement can be used to lock the output stream while producing output. In this case, the mutex statement allows the programmer to acquire mutual exclusion over an object without having to know the internals of the object or what locks need to be acquired. The ability to do so provides both improves safety and programmer productivity since it abstracts away the concurrent details and provides an interface for optional thread-safety. This is a commonly used feature when producing output from a concurrent context, since producing output is not thread safe by default. This use case is shown in Listing~\ref{l:sout}.
     51The parametric polymorphism allows for locking to be defined for types that may want convenient mutual exclusion.
     52An example of one such use case in \CFA is \code{sout}.
     53The output stream in \CFA is called \code{sout}, and functions similarly to \CC's \code{cout}.
     54\code{sout} has routines that satisfy the mutex statement trait, so the mutex statement can be used to lock the output stream while producing output.
     55In this case, the mutex statement allows the programmer to acquire mutual exclusion over an object without having to know the internals of the object or what locks need to be acquired.
     56The ability to do so provides both improves safety and programmer productivity since it abstracts away the concurrent details and provides an interface for optional thread-safety.
     57This is a commonly used feature when producing output from a concurrent context, since producing output is not thread safe by default.
     58This use case is shown in Listing~\ref{l:sout}.
    3459
    3560\begin{cfacode}[tabsize=3,caption={\CFA sout with mutex statement},label={l:sout}]
    … …  
    3964
    4065\section{Deadlock Avoidance}
    41 The mutex statement uses the deadlock prevention technique of lock ordering, where the circular-wait condition of a deadlock cannot occur if all locks are acquired in the same order. The scoped\_lock uses a deadlock avoidance algorithm where all locks after the first are acquired using \code{try_lock} and if any of the attempts to lock fails, all locks so far are released. This repeats until all locks are acquired successfully. The deadlock avoidance algorithm used by scoped\_lock is shown in Listing~\ref{l:cc_deadlock_avoid}. The algorithm presented is taken directly from the source code of the \code{<mutex>} header, with some renaming and comments for clarity.
     66The mutex statement uses the deadlock prevention technique of lock ordering, where the circular-wait condition of a deadlock cannot occur if all locks are acquired in the same order.
     67The scoped\_lock uses a deadlock avoidance algorithm where all locks after the first are acquired using \code{try_lock} and if any of the attempts to lock fails, all locks so far are released.
     68This repeats until all locks are acquired successfully.
     69The deadlock avoidance algorithm used by scoped\_lock is shown in Listing~\ref{l:cc_deadlock_avoid}.
     70The algorithm presented is taken directly from the source code of the \code{<mutex>} header, with some renaming and comments for clarity.
    4271
    43 \begin{cppcode}[tabsize=3,caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}]
     72\begin{cppcode}[caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}]
    4473int first = 0;  // first lock to attempt to lock
    4574do {
    … …  
    5988\end{cppcode}
    6089
    61 The algorithm in \ref{l:cc_deadlock_avoid} successfully avoids deadlock, however there is a potential livelock scenario. Given two threads $A$ and $B$, who create a scoped\_lock with two locks $L1$ and $L2$, a livelock can form as follows. Thread $A$ creates a scoped\_lock with $L1$, $L2$, and $B$ creates a scoped lock with the order $L2$, $L1$. Both threads acquire the first lock in their order and then fail the try\_lock since the other lock is held. They then reset their start lock to be their 2nd lock and try again. This time $A$ has order $L2$, $L1$, and $B$ has order $L1$, $L2$. This is identical to the starting setup, but with the ordering swapped among threads. As such, if they each acquire their first lock before the other acquires their second, they can livelock indefinitely.
     90The algorithm in \ref{l:cc_deadlock_avoid} successfully avoids deadlock, however there is a potential livelock scenario.
     91Given two threads $A$ and $B$, who create a scoped\_lock with two locks $L1$ and $L2$, a livelock can form as follows.
     92Thread $A$ creates a scoped\_lock with $L1$, $L2$, and $B$ creates a scoped lock with the order $L2$, $L1$.
     93Both threads acquire the first lock in their order and then fail the try\_lock since the other lock is held.
     94They then reset their start lock to be their 2nd lock and try again.
     95This time $A$ has order $L2$, $L1$, and $B$ has order $L1$, $L2$.
     96This is identical to the starting setup, but with the ordering swapped among threads.
     97As such, if they each acquire their first lock before the other acquires their second, they can livelock indefinitely.
    6298
    63 The lock ordering algorithm used in the mutex statement in \CFA is both deadlock and livelock free. It sorts the locks based on memory address and then acquires them. For locks fewer than 7, it sorts using hard coded sorting methods that perform the minimum number of swaps for a given number of locks. For 7 or more locks insertion sort is used. These sorting algorithms were chosen since it is rare to have to hold more than  a handful of locks at a time. It is worth mentioning that the downside to the sorting approach is that it is not fully compatible with usages of the same locks outside the mutex statement. If more than one lock is held by a mutex statement, if more than one lock is to be held elsewhere, it must be acquired via the mutex statement, or else the required ordering will not occur. Comparitively, if the scoped\_lock is used and the same locks are acquired elsewhere, there is no concern of the scoped\_lock deadlocking, due to its avoidance scheme, but it may livelock.
     99The lock ordering algorithm used in the mutex statement in \CFA is both deadlock and livelock free.
     100It sorts the locks based on memory address and then acquires them.
     101For locks fewer than 7, it sorts using hard coded sorting methods that perform the minimum number of swaps for a given number of locks.
     102For 7 or more locks insertion sort is used.
     103These sorting algorithms were chosen since it is rare to have to hold more than  a handful of locks at a time.
     104It is worth mentioning that the downside to the sorting approach is that it is not fully compatible with usages of the same locks outside the mutex statement.
     105If more than one lock is held by a mutex statement, if more than one lock is to be held elsewhere, it must be acquired via the mutex statement, or else the required ordering will not occur.
     106Comparitively, if the scoped\_lock is used and the same locks are acquired elsewhere, there is no concern of the scoped\_lock deadlocking, due to its avoidance scheme, but it may livelock.
    64107
    65108\begin{figure}
    … …  
    102145
    103146\section{Performance}
    104 Performance is compared between \CC's scoped\_lock and \CFA's mutex statement. Comparison with Java is omitted, since it only takes a single lock. To ensure that the comparison between \CC and \CFA exercises the implementation of each feature, an identical spinlock is implemented in each language using a set of builtin atomics available in both \CFA and \CC. Each feature is evaluated on a benchmark which acquires a fixed number of locks in a random order and then releases them. A baseline is included that acquires the locks directly without a mutex statement or scoped\_lock in a fixed ordering and then releases them. The baseline helps highlight the cost of the deadlock avoidance/prevention algorithms for each implementation. The benchmarks are run for a fixed duration of 10 seconds and then terminate and return the total number of times the group of locks were acquired. Each variation is run 11 times on a variety up to 32 cores and with 2, 4, and 8 locks being acquired. The median is calculated and is plotted alongside the 95\% confidence intervals for each point.
     147Performance is compared between \CC's scoped\_lock and \CFA's mutex statement.
     148Comparison with Java is omitted, since it only takes a single lock.
     149To ensure that the comparison between \CC and \CFA exercises the implementation of each feature, an identical spinlock is implemented in each language using a set of builtin atomics available in both \CFA and \CC.
     150Each feature is evaluated on a benchmark which acquires a fixed number of locks in a random order and then releases them.
     151A baseline is included that acquires the locks directly without a mutex statement or scoped\_lock in a fixed ordering and then releases them.
     152The baseline helps highlight the cost of the deadlock avoidance/prevention algorithms for each implementation.
     153The benchmarks are run for a fixed duration of 10 seconds and then terminate and return the total number of times the group of locks were acquired.
     154Each variation is run 11 times on a variety up to 32 cores and with 2, 4, and 8 locks being acquired.
     155The median is calculated and is plotted alongside the 95\% confidence intervals for each point.
    105156
    106 Figure~\ref{f:mutex_bench} shows the results of the benchmark. The baseline runs for both languages are mostly comparable, except for the 8 locks results in \ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel}, where the \CFA baseline is slower. \CFA's mutex statement achieves throughput that is magnitudes higher than \CC's scoped\_lock. This is likely due to the scoped\_lock deadlock avoidance implementation. Since it uses a retry based mechanism, it can take a long time for threads to progress. Additionally the potential for livelock in the algorithm can result in very little throughput under high contention. It was observed on the AMD machine that with 32 threads and 8 locks the benchmarks would occasionally livelock indefinitely, with no threads making any progress for 3 hours before the experiment was terminated manually. It is likely that shorter bouts of livelock occured in many of the experiments, which would explain large confidence intervals for some of the data points in the \CC data. In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} the mutex statement performs better than the baseline. At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort. It is likely that the improvement in throughput compared to baseline is due to the time spent in the insertion sort, which decreases contention on the locks.
     157Figure~\ref{f:mutex_bench} shows the results of the benchmark.
     158The baseline runs for both languages are mostly comparable, except for the 8 locks results in \ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel}, where the \CFA baseline is slower.
     159\CFA's mutex statement achieves throughput that is magnitudes higher than \CC's scoped\_lock.
     160This is likely due to the scoped\_lock deadlock avoidance implementation.
     161Since it uses a retry based mechanism, it can take a long time for threads to progress.
     162Additionally the potential for livelock in the algorithm can result in very little throughput under high contention.
     163It was observed on the AMD machine that with 32 threads and 8 locks the benchmarks would occasionally livelock indefinitely, with no threads making any progress for 3 hours before the experiment was terminated manually.
     164It is likely that shorter bouts of livelock occured in many of the experiments, which would explain large confidence intervals for some of the data points in the \CC data.
     165In Figures~\ref{f:mutex_bench8_AMD} and \ref{f:mutex_bench8_Intel} the mutex statement performs better than the baseline.
     166At 7 locks and above the mutex statement switches from a hard coded sort to insertion sort.
     167It is likely that the improvement in throughput compared to baseline is due to the time spent in the insertion sort, which decreases contention on the locks.

  • doc/theses/colby_parsons_MMAth/thesis.tex

    rfa6ca1a r34b6a7b6  
    1 % requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
    2 
    3 % inline code �...� (copyright symbol) emacs: C-q M-)
    4 % red highlighting �...� (registered trademark symbol) emacs: C-q M-.
    5 % blue highlighting �...� (sharp s symbol) emacs: C-q M-_
    6 % green highlighting �...� (cent symbol) emacs: C-q M-"
    7 % LaTex escape �...� (section symbol) emacs: C-q M-'
    8 % keyword escape �...� (pilcrow symbol) emacs: C-q M-^
    9 % math escape $...$ (dollar symbol)
    10 
     1%======================================================================
     2% University of Waterloo Thesis Template for LaTeX
     3% Last Updated August 2022
     4% by IST Client Services,
     5% University of Waterloo, 200 University Ave. W., Waterloo, Ontario, Canada
     6% FOR ASSISTANCE, please send mail to helpdesk@uwaterloo.ca
     7
     8% DISCLAIMER
     9% To the best of our knowledge, this template satisfies the current uWaterloo thesis requirements.
     10% However, it is your responsibility to assure that you have met all requirements of the University and your particular department.
     11
     12% Many thanks for the feedback from many graduates who assisted the development of this template.
     13% Also note that there are explanatory comments and tips throughout this template.
     14%======================================================================
     15% Some important notes on using this template and making it your own...
     16
     17% The University of Waterloo has required electronic thesis submission since October 2006.
     18% See the uWaterloo thesis regulations at
     19% https://uwaterloo.ca/graduate-studies/thesis.
     20% This thesis template is geared towards generating a PDF version optimized for viewing on an electronic display, including hyperlinks within the PDF.
     21
     22% DON'T FORGET TO ADD YOUR OWN NAME AND TITLE in the "hyperref" package configuration below.
     23% Search for: PDFTITLE, PDFAUTHOR, PDFSUBJECT, and PDFKEYWORDS.
     24% THIS INFORMATION GETS EMBEDDED IN THE FINAL PDF DOCUMENT.
     25% You can view the information if you view properties of the PDF document.
     26
     27% Many faculties/departments also require one or more printed copies.
     28% This template attempts to satisfy both types of output.
     29% See additional notes below.
     30% It is based on the standard "book" document class which provides all necessary sectioning structures and allows multi-part theses.
     31
     32% If you are using this template in Overleaf (cloud-based collaboration service), then it is automatically processed and previewed for you as you edit.
     33
     34% For people who prefer to install their own LaTeX distributions on their own computers, and process the source files manually, the following notes provide the sequence of tasks:
     35 
     36% E.g. to process a thesis called "mythesis.tex" based on this template, run:
     37
     38% pdflatex mythesis     -- first pass of the pdflatex processor
     39% bibtex mythesis       -- generates bibliography from .bib data file(s)
     40% makeindex         -- should be run only if an index is used
     41% pdflatex mythesis     -- fixes numbering in cross-references, bibliographic references, glossaries, index, etc.
     42% pdflatex mythesis     -- it takes a couple of passes to completely process all cross-references
     43
     44% If you use the recommended LaTeX editor, Texmaker, you would open the mythesis.tex file, then click the PDFLaTeX button. Then run BibTeX (under the Tools menu).
     45% Then click the PDFLaTeX button two more times.
     46% If you have an index as well,you'll need to run MakeIndex from the Tools menu as well, before running pdflatex
     47% the last two times.
     48
     49% N.B. The "pdftex" program allows graphics in the following formats to be included with the "\includegraphics" command: PNG, PDF, JPEG, TIFF
     50% Tip: Generate your figures and photos in the size you want them to appear in your thesis, rather than scaling them with \includegraphics options.
     51% Tip: Any drawings you do should be in scalable vector graphic formats: SVG, PNG, WMF, EPS and then converted to PNG or PDF, so they are scalable in the final PDF as well.
     52% Tip: Photographs should be cropped and compressed so as not to be too large.
     53
     54% To create a PDF output that is optimized for double-sided printing:
     55% 1) comment-out the \documentclass statement in the preamble below, and un-comment the second \documentclass line.
     56% 2) change the value assigned below to the boolean variable "PrintVersion" from " false" to "true".
     57
     58%======================================================================
     59%   D O C U M E N T   P R E A M B L E
     60% Specify the document class, default style attributes, and page dimensions, etc.
     61% For hyperlinked PDF, suitable for viewing on a computer, use this:
    1162\documentclass[letterpaper,12pt,titlepage,oneside,final]{book}
    12 
    13 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    14 
    15 % Latex packages used in the document.
    16 \usepackage[T1]{fontenc}                                        % allow Latin1 (extended ASCII) characters
     63 
     64% For PDF, suitable for double-sided printing, change the PrintVersion variable below to "true" and use this \documentclass line instead of the one above:
     65%\documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book}
     66
     67% Some LaTeX commands I define for my own nomenclature.
     68% If you have to, it's easier to make changes to nomenclature once here than in a million places throughout your thesis!
     69\newcommand{\package}[1]{\textbf{#1}} % package names in bold text
     70\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font
     71\newcommand{\href}[1]{#1} % does nothing, but defines the command so the print-optimized version will ignore \href tags (redefined by hyperref pkg).
     72%\newcommand{\texorpdfstring}[2]{#1} % does nothing, but defines the command
     73% Anything defined here may be redefined by packages added below...
     74
     75% This package allows if-then-else control structures.
     76\usepackage{ifthen}
     77\newboolean{PrintVersion}
     78\setboolean{PrintVersion}{false}
     79% CHANGE THIS VALUE TO "true" as necessary, to improve printed results for hard copies by overriding some options of the hyperref package, called below.
     80
     81%\usepackage{nomencl} % For a nomenclature (optional; available from ctan.org)
     82\usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments
     83
     84\usepackage{tikz} % for diagrams and figures
     85\def\checkmark{\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;}
     86\usepackage{subcaption}
     87\usepackage{fullpage,times,comment}
    1788\usepackage{textcomp}
    18 \usepackage[latin1]{inputenc}
    19 \usepackage{fullpage,times,comment}
    20 \usepackage{epic,eepic}
    21 \usepackage{upquote}                                            % switch curled `'" to straight
    22 \usepackage{dirtytalk}
    23 \usepackage{calc}
    24 \usepackage{xspace}
    25 % \usepackage[labelformat=simple]{subfig}
    26 % \renewcommand{\thesubfigure}{(\alph{subfigure})}
    27 \usepackage{subcaption}
    28 % \usepackage{subfigure}
    2989\usepackage{graphicx}
    3090\usepackage{tabularx}
    31 \usepackage{multicol}
    32 \usepackage[acronym]{glossaries}
    33 \usepackage{varioref}
    34 \usepackage{listings}                                           % format program code
    35 \usepackage[flushmargin]{footmisc}                              % support label/reference in footnote
    36 \usepackage{latexsym}                                           % \Box glyph
    37 \usepackage{mathptmx}                                           % better math font with "times"
    38 \usepackage[usenames]{color}
    39 \usepackage[pagewise]{lineno}
    40 \renewcommand{\linenumberfont}{\scriptsize\sffamily}
    41 \usepackage{fancyhdr}
    42 \usepackage{float}
    43 \usepackage{siunitx}
    44 \sisetup{ binary-units=true }
    45 \input{style}                                                   % bespoke macros used in the document
    46 \usepackage{url}
    47 \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    48 \usepackage{breakurl}
    49 \urlstyle{rm}
    50 
    51 \usepackage{tikz}
    52 \def\checkmark{\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;}
    53 
    54 \setlength{\topmargin}{-0.45in}                         % move running title into header
    55 \setlength{\headsep}{0.25in}
    56 
    57 \newsavebox{\myboxA}                                    % used with subfigure
    58 \newsavebox{\myboxB}
    59 
    60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    61 
    62 % Names used in the document.
    63 
    64 \newcommand{\Version}{1.0.0}
    65 \newcommand{\CS}{C\raisebox{-0.9ex}{\large$^\sharp$}\xspace}
    66 
    67 \newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
    68 \newcommand{\Emph}[2][red]{{\color{#1}\textbf{\emph{#2}}}}
    69 \newcommand{\R}[1]{\Textbf{#1}}
    70 \newcommand{\B}[1]{{\Textbf[blue]{#1}}}
    71 \newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
    72 \newcommand{\uC}{$\mu$\CC}
    73 \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
    74 \newcommand{\TODO}{{\Textbf{TODO}}}
    75 
     91\input{style}
     92
     93% Hyperlinks make it very easy to navigate an electronic document.
     94% In addition, this is where you should specify the thesis title and author as they appear in the properties of the PDF document.
     95% Use the "hyperref" package
     96% N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE
     97\usepackage[dvips,pagebackref=false]{hyperref} % with basic options
     98\hypersetup{
     99    plainpages=false,       % needed if Roman numbers in frontpages
     100    unicode=false,          % non-Latin characters in Acrobat’s bookmarks
     101    pdftoolbar=true,        % show Acrobat’s toolbar?
     102    pdfmenubar=true,        % show Acrobat’s menu?
     103    pdffitwindow=false,     % window fit to page when opened
     104    pdfstartview={FitH},    % fits the width of the page to the window
     105    pdftitle={High Level Concurrency in \CFA},
     106    pdfauthor={Colby Parsons},
     107    pdfsubject={Cforall},
     108%    pdfkeywords={keyword1} {key2} {key3}, % list of keywords, and uncomment this line if desired
     109    pdfnewwindow=true,      % links in new window
     110    colorlinks=true,        % false: boxed links; true: colored links
     111    linkcolor=blue,         % color of internal links
     112    citecolor=green,        % color of links to bibliography
     113    filecolor=magenta,      % color of file links
     114    urlcolor=cyan           % color of external links
     115}
     116\ifthenelse{\boolean{PrintVersion}}{   % for improved print quality, change some hyperref options
     117\hypersetup{    % override some previously defined hyperref options
     118%    colorlinks,%
     119    citecolor=black,%
     120    filecolor=black,%
     121    linkcolor=black,%
     122    urlcolor=black}
     123}{} % end of ifthenelse (no else)
     124
     125% \usepackage[acronym]{glossaries}
     126\usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package
     127% If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra),
     128% although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and
     129% installation instructions there.
     130
     131% Setting up the page margins...
     132% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the
     133% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter margin (on binding side).
     134% While this is not an issue for electronic viewing, a PDF may be printed, and so we have the same page layout for both printed and electronic versions, we leave the gutter margin in.
     135% Set margins to minimum permitted by uWaterloo thesis regulations:
     136\setlength{\marginparwidth}{0pt} % width of margin notes
     137% N.B. If margin notes are used, you must adjust \textwidth, \marginparwidth
     138% and \marginparsep so that the space left between the margin notes and page
     139% edge is less than 15 mm (0.6 in.)
     140\setlength{\marginparsep}{0pt} % width of space between body text and margin notes
     141\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all
     142% even-numbered pages when the "twoside" printing option is selected
     143\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages when "oneside" printing is selected, and to the left of all odd-numbered pages when "twoside" printing is selected
     144\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and side margins as above
     145\raggedbottom
     146
     147% The following statement specifies the amount of space between paragraphs. Other reasonable specifications are \bigskipamount and \smallskipamount.
     148\setlength{\parskip}{\medskipamount}
     149
     150% The following statement controls the line spacing. 
     151% The default spacing corresponds to good typographic conventions and only slight changes (e.g., perhaps "1.2"), if any, should be made.
     152\renewcommand{\baselinestretch}{1} % this is the default line space setting
     153
     154% By default, each chapter will start on a recto (right-hand side) page.
     155% We also force each section of the front pages to start on a recto page by inserting \cleardoublepage commands.
     156% In many cases, this will require that the verso (left-hand) page be blank, and while it should be counted, a page number should not be printed.
     157% The following statements ensure a page number is not printed on an otherwise blank verso page.
     158\let\origdoublepage\cleardoublepage
     159\newcommand{\clearemptydoublepage}{%
     160  \clearpage{\pagestyle{empty}\origdoublepage}}
     161\let\cleardoublepage\clearemptydoublepage
     162
     163% Define Glossary terms (This is properly done here, in the preamble and could also be \input{} from a separate file...)
    76164\input{glossary}
    77 
    78 \newsavebox{\LstBox}
    79 
    80 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    81 
    82 \setcounter{secnumdepth}{2}                           % number subsubsections
    83 \setcounter{tocdepth}{2}                              % subsubsections in table of contents
    84 % \linenumbers                                          % comment out to turn off line numbering
    85 \makeindex
    86 \pagestyle{fancy}
    87 \fancyhf{}
    88 \cfoot{\thepage}
    89 \rfoot{v\input{version}}
    90 
    91 
    92 
    93 %======================================================================
    94 %   L O G I C A L    D O C U M E N T -- the content of your thesis
     165\makeglossaries
     166
     167%======================================================================
     168%   L O G I C A L    D O C U M E N T
     169% The logical document contains the main content of your thesis.
     170% Being a large document, it is a good idea to divide your thesis into several files, each one containing one chapter or other significant chunk of content, so you can easily shuffle things around later if desired.
    95171%======================================================================
    96172\begin{document}
    97173\newtheorem{theorem}{Theorem}
    98174
    99 % For a large document, it is a good idea to divide your thesis
    100 % into several files, each one containing one chapter.
    101 % To illustrate this idea, the "front pages" (i.e., title page,
    102 % declaration, borrowers' page, abstract, acknowledgements,
    103 % dedication, table of contents, list of tables, list of figures,
    104 % nomenclature) are contained within the file "thesis-frontpgs.tex" which is
    105 % included into the document by the following statement.
    106175%----------------------------------------------------------------------
    107176% FRONT MATERIAL
    108 %----------------------------------------------------------------------
    109 \input{frontpgs}
     177% title page,declaration, borrowers' page, abstract, acknowledgements,
     178% dedication, table of contents, list of tables, list of figures, nomenclature, etc.
     179%----------------------------------------------------------------------
     180\input{frontpgs}
    110181
    111182%----------------------------------------------------------------------
    112183% MAIN BODY
    113 %----------------------------------------------------------------------
    114 
     184% We suggest using a separate file for each chapter of your thesis.
     185% Start each chapter file with the \chapter command.
     186% Only use \documentclass or \begin{document} and \end{document} commands in this master document.
     187% Tip: Putting each sentence on a new line is a way to simplify later editing.
     188%----------------------------------------------------------------------
    115189\input{intro}
    116190
    … …  
    125199\input{actors}
    126200
    127 \clearpage
    128 
    129 % B I B L I O G R A P H Y
     201%----------------------------------------------------------------------
     202% END MATERIAL
     203% Bibliography, Appendices, Index, etc.
     204%----------------------------------------------------------------------
     205
     206% Bibliography
     207
     208% The following statement selects the style to use for references. 
     209% It controls the sort order of the entries in the bibliography and also the formatting for the in-text labels.
     210\bibliographystyle{plain}
     211% This specifies the location of the file containing the bibliographic information. 
     212% It assumes you're using BibTeX to manage your references (if not, why not?).
     213\cleardoublepage % This is needed if the "book" document class is used, to place the anchor in the correct page, because the bibliography will start on its own page.
     214% Use \clearpage instead if the document class uses the "oneside" argument
     215\phantomsection  % With hyperref package, enables hyperlinking from the table of contents to bibliography             
     216% The following statement causes the title "References" to be used for the bibliography section:
     217\renewcommand*{\bibname}{References}
     218
     219% Add the References to the Table of Contents
     220\addcontentsline{toc}{chapter}{\textbf{References}}
     221
     222\bibliography{pl,local}
     223% Tip: You can create multiple .bib files to organize your references.
     224% Just list them all in the \bibliogaphy command, separated by commas (no spaces).
     225
     226% The following statement causes the specified references to be added to the bibliography even if they were not cited in the text.
     227% The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional).
     228% \nocite{*}
     229%----------------------------------------------------------------------
     230
     231% Appendices
     232
     233% The \appendix statement indicates the beginning of the appendices.
     234% \appendix
     235% % Add an un-numbered title page before the appendices and a line in the Table of Contents
     236% \chapter*{APPENDICES}
     237% \addcontentsline{toc}{chapter}{APPENDICES}
     238% % Appendices are just more chapters, with different labeling (letters instead of numbers).
     239% \input{appendix-matlab_plots.tex}
     240
     241% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
    130242% -----------------------------
    131 \addcontentsline{toc}{chapter}{Bibliography}
    132 \bibliographystyle{plain}
    133 \bibliography{pl,local}
    134 \cleardoublepage
    135 \phantomsection         % allows hyperref to link to the correct page
    136 
    137 % G L O S S A R Y
    138 % -----------------------------
    139 \addcontentsline{toc}{chapter}{Glossary}
    140243\printglossary
    141244\cleardoublepage
    142245\phantomsection         % allows hyperref to link to the correct page
    143246
    144 
    145 \end{document}
     247%----------------------------------------------------------------------
     248\end{document} % end of logical document

  • doc/theses/colby_parsons_MMAth/version

    rfa6ca1a r34b6a7b6  
    1 0.0.0
     10.0.15

  • tests/concurrent/channels/churn.cfa

    rfa6ca1a r34b6a7b6  
    33#include <stdio.h>
    44#include <string.h>
    5 #include "channel.hfa"
     5#include <channel.hfa>
    66#include <thread.hfa>
    77#include <time.hfa>
    8 #include <stats.hfa>
     8
    99size_t Processors = 1, Channels = 4, Producers = 2, Consumers = 2, ChannelSize = 128;
    1010
Note: See TracChangeset for help on using the changeset viewer.