Changeset 0a89a8f


Ignore:
Timestamp:
Apr 14, 2018, 7:13:15 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, with_gc
Children:
81bb114
Parents:
82df430
Message:

numerous updates

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Paper.tex

    r82df430 r0a89a8f  
    1717\usepackage{upquote}                                            % switch curled `'" to straight
    1818\usepackage{listings}                                           % format program code
    19 \usepackage[labelformat=simple]{subfig}
     19\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
    2020\renewcommand{\thesubfigure}{(\alph{subfigure})}
    2121\usepackage{siunitx}
     
    9595% Latin abbreviation
    9696\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
     97\@ifundefined{eg}{
    9798\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
    9899\newcommand*{\eg}{%
     
    100101                {\@ifnextchar{:}{\EG}%
    101102                        {\EG,\xspace}}%
    102 }%
     103}}{}%
     104\@ifundefined{ie}{
    103105\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
    104106\newcommand*{\ie}{%
     
    106108                {\@ifnextchar{:}{\IE}%
    107109                        {\IE,\xspace}}%
    108 }%
     110}}{}%
     111\@ifundefined{etc}{
    109112\newcommand{\ETC}{\abbrevFont{etc}}
    110113\newcommand*{\etc}{%
    111114        \@ifnextchar{.}{\ETC}%
    112115        {\ETC.\xspace}%
    113 }%
     116}}{}%
     117\@ifundefined{etal}{
    114118\newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
    115 \renewcommand*{\etal}{%
     119\newcommand*{\etal}{%
    116120        \@ifnextchar{.}{\protect\ETAL}%
    117121                {\protect\ETAL.\xspace}%
    118 }%
     122}}{}%
     123\@ifundefined{viz}{
    119124\newcommand{\VIZ}{\abbrevFont{viz}}
    120125\newcommand*{\viz}{%
    121126        \@ifnextchar{.}{\VIZ}%
    122127                {\VIZ.\xspace}%
    123 }%
     128}}{}%
    124129\makeatother
    125130
     
    134139\lstdefinelanguage{CFA}[ANSI]{C}{
    135140        morekeywords={
    136                 _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, _At, __attribute,
    137                 __attribute__, auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__,
    138                 __const, __const__, disable, dtype, enable, exception, __extension__, fallthrough, fallthru,
    139                 finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t,
    140                 otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof,
    141                 __typeof__, virtual, with, zero_t},
    142         morekeywords=[2]{
    143                 _Atomic, coroutine, is_coroutine, is_monitor, is_thread, monitor, mutex, nomutex, or,
    144                 resume, suspend, thread, _Thread_local, waitfor, when, yield},
     141                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
     142                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
     143                coroutine, disable, dtype, enable, __extension__, exception, fallthrough, fallthru, finally,
     144                __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
     145                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
     146                otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
     147                _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
     148                virtual, __volatile, __volatile__, waitfor, when, with, zero_t},
    145149        moredirectives={defined,include_next}%
    146150}
     
    212216\authormark{Thierry Delisle \textsc{et al}}
    213217
    214 \address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
     218\address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
    215219
    216220\corres{*Peter A. Buhr, \email{pabuhr{\char`\@}uwaterloo.ca}}
    217 \presentaddress{David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
     221\presentaddress{Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
    218222
    219223
     
    229233}%
    230234
    231 \keywords{concurrency, runtime, coroutines, threads, C, Cforall}
     235\keywords{concurrency, parallelism, coroutines, threads, monitors, runtime, C, Cforall}
    232236
    233237
     
    243247% ======================================================================
    244248
    245 This paper provides a minimal concurrency \newterm{API} that is simple, efficient and can be used to build other concurrency features.
     249This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
    246250While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
    247251An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
     
    249253Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}.
    250254
    251 The terminology used in this paper is as follows.
     255This paper used the following terminology.
    252256A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state.
    253 Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe access to shared data.
    254 % Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced.
     257Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data.
     258% Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, \etc) concurrent threads are introduced.
    255259\newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety.
    256260\newterm{Parallelism} is running multiple threads simultaneously.
     
    259263
    260264Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism.
    261 While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}.
    262 Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost and resource utilization.
     265While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
     266Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization.
    263267
    264268The proposed concurrency API is implemented in a dialect of C, called \CFA.
     
    277281Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code.
    278282The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C.
    279 Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (e.g., {\tt this}), it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent
     283Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (\eg {\tt this}), it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent
    280284values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects.
    281285Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
     
    329333\subsection{Operators}
    330334Overloading also extends to operators.
    331 The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, e.g.:
     335The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, \eg:
    332336\begin{cfa}
    333337int ++? (int op);                       $\C{// unary prefix increment}$
     
    420424
    421425Note that the type use for assertions can be either an @otype@ or a @dtype@.
    422 Types declared as @otype@ refer to ``complete'' objects, i.e., objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
     426Types declared as @otype@ refer to ``complete'' objects, \ie objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
    423427Using @dtype@, on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.
    424428
     
    458462% ======================================================================
    459463% ======================================================================
    460 Before any detailed discussion of the concurrency and parallelism in \CFA, it is important to describe the basics of concurrency and how they are expressed in \CFA user code.
    461 
    462 \section{Basics of concurrency}
     464
    463465At its core, concurrency is based on having multiple call-stacks and scheduling among threads of execution executing on these stacks.
    464 Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution.
    465 
    466 Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining.
    467 Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency.
    468 
    469 Therefore, a minimal concurrency system can be achieved by creating coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always ask an oracle where to context-switch next.
     466Multiple call stacks (or contexts) and a single thread of execution does \emph{not} imply concurrency.
     467Execution with a single thread and multiple stacks where the thread is deterministically self-scheduling across the stacks is called \newterm{coroutining};
     468execution with a single thread and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency~\cite[\S~3]{Buhr05a}.
     469Therefore, a minimal concurrency system can be achieved using coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always defer to an oracle for where to context-switch next.
     470
    470471While coroutines can execute on the caller's stack-frame, stack-full coroutines allow full generality and are sufficient as the basis for concurrency.
    471472The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a., non-preemptive scheduling).
     
    480481
    481482
    482 \section{\protect\CFA's Thread Building Blocks}
     483\subsection{\protect\CFA's Thread Building Blocks}
    483484
    484485One of the important features that are missing in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional.
     
    490491
    491492
    492 \section{Coroutines: A Stepping Stone}\label{coroutine}
    493 
    494 While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. \textbf{Coroutine}s are generalized routines which have predefined points where execution is suspended and can be resumed at a later time.
    495 Therefore, they need to deal with context switches and other context-management operations.
    496 This proposal includes coroutines both as an intermediate step for the implementation of threads, and a first-class feature of \CFA.
    497 Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant.
    498 The core \textbf{api} of coroutines revolves around two features: independent call-stacks and @suspend@/@resume@.
     493\subsection{Coroutines: A Stepping Stone}\label{coroutine}
     494
     495While the focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system.
     496\newterm{Coroutine}s are generalized routines with points where execution is suspended and resumed at a later time.
     497Suspend/resume is a context switche and coroutines have other context-management operations.
     498Many design challenges of threads are partially present in designing coroutines, which makes the design effort relevant.
     499The core \textbf{api} of coroutines has two features: independent call-stacks and @suspend@/@resume@.
     500
     501A coroutine handles the class of problems that need to retain state between calls (\eg plugin, device driver, finite-state machine).
     502For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers:
     503\begin{displaymath}
     504f(n) = \left \{
     505\begin{array}{ll}
     5060                               & n = 0         \\
     5071                               & n = 1         \\
     508f(n-1) + f(n-2) & n \ge 2       \\
     509\end{array}
     510\right.
     511\end{displaymath}
     512Figure~\ref{f:C-fibonacci} shows conventional approaches for writing a Fibonacci generator in C.
     513
     514Figure~\ref{f:GlobalVariables} illustrates the following problems:
     515unencapsulated global variables necessary to retain state between calls;
     516only one fibonacci generator can run at a time;
     517execution state must be explicitly retained.
     518Figure~\ref{f:ExternalState} addresses these issues:
     519unencapsulated program global variables become encapsulated structure variables;
     520multiple fibonacci generators can run at a time by declaring multiple fibonacci objects;
     521explicit execution state is removed by precomputing the first two Fibonacci numbers and returning $f(n-2)$.
    499522
    500523\begin{figure}
    501 \begin{center}
    502 \begin{tabular}{@{}lll@{}}
    503 \multicolumn{1}{c}{\textbf{callback}} & \multicolumn{1}{c}{\textbf{output array}} & \multicolumn{1}{c}{\textbf{external state}} \\
    504 \begin{cfa}
    505 void fib_func(
    506         int n, void (* callback)( int )
    507 ) {
    508         int fn, f1 = 0, f2 = 1;
    509         for ( int i = 0; i < n; i++ ) {
    510                 callback( f1 );
    511                 fn = f1 + f2;
    512                 f1 = f2;  f2 = fn;
     524\centering
     525\newbox\myboxA
     526\begin{lrbox}{\myboxA}
     527\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     528`int f1, f2, state = 1;`   // single global variables
     529int fib() {
     530        int fn;
     531        `switch ( state )` {  // explicit execution state
     532          case 1: fn = 0;  f1 = fn;  state = 2;  break;
     533          case 2: fn = 1;  f2 = f1;  f1 = fn;  state = 3;  break;
     534          case 3: fn = f1 + f2;  f2 = f1;  f1 = fn;  break;
    513535        }
     536        return fn;
    514537}
    515538int main() {
    516         void print_fib( int n ) {
    517                 printf( "%d\n", n );
     539
     540        for ( int i = 0; i < 10; i += 1 ) {
     541                printf( "%d\n", fib() );
    518542        }
    519         fib_func( 10, print_fib );
    520 }
    521 
    522 \end{cfa}
    523 &
    524 \begin{cfa}
    525 void fib_array(
    526         int n, int * array
    527 ) {
    528         int fn, f1 = 0, f2 = 1;
    529         for ( int i = 0; i < n; i++ ) {
    530                 array[i] = f1;
    531                 fn = f1 + f2;
    532                 f1 = f2;  f2 = fn;
     543}
     544\end{lstlisting}
     545\end{lrbox}
     546
     547\newbox\myboxB
     548\begin{lrbox}{\myboxB}
     549\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     550#define FIB_INIT `{ 0, 1 }`
     551typedef struct { int f2, f1; } Fib;
     552int fib( Fib * f ) {
     553
     554        int ret = f->f2;
     555        int fn = f->f1 + f->f2;
     556        f->f2 = f->f1; f->f1 = fn;
     557
     558        return ret;
     559}
     560int main() {
     561        Fib f1 = FIB_INIT, f2 = FIB_INIT;
     562        for ( int i = 0; i < 10; i += 1 ) {
     563                printf( "%d %d\n", fib( &f1 ), fib( &f2 ) );
    533564        }
    534565}
     566\end{lstlisting}
     567\end{lrbox}
     568
     569\subfloat[3 States: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
     570\qquad
     571\subfloat[1 State: external variables]{\label{f:ExternalState}\usebox\myboxB}
     572\caption{C Fibonacci Implementations}
     573\label{f:C-fibonacci}
     574
     575\bigskip
     576
     577\newbox\myboxA
     578\begin{lrbox}{\myboxA}
     579\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     580`coroutine` Fib { int fn; };
     581void main( Fib & f ) with( f ) {
     582        int f1, f2;
     583        fn = 0;  f1 = fn;  `suspend()`;
     584        fn = 1;  f2 = f1;  f1 = fn;  `suspend()`;
     585        for ( ;; ) {
     586                fn = f1 + f2;  f2 = f1;  f1 = fn;  `suspend()`;
     587        }
     588}
     589int next( Fib & fib ) with( fib ) {
     590        `resume( fib );`
     591        return fn;
     592}
    535593int main() {
    536         int a[10];
    537         fib_array( 10, a );
    538         for ( int i = 0; i < 10; i++ ) {
    539                 printf( "%d\n", a[i] );
     594        Fib f1, f2;
     595        for ( int i = 1; i <= 10; i += 1 ) {
     596                sout | next( f1 ) | next( f2 ) | endl;
    540597        }
    541598}
    542 \end{cfa}
    543 &
    544 \begin{cfa}
    545 
    546 typedef struct { int f1, f2; } Fib;
    547 int fib_state(
    548         Fib * fib
    549 ) {
    550         int ret = fib->f1;
    551         int fn = fib->f1 + fib->f2;
    552         fib->f2 = fib->f1; fib->f1 = fn;
     599\end{lstlisting}
     600\end{lrbox}
     601\newbox\myboxB
     602\begin{lrbox}{\myboxB}
     603\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
     604`coroutine` Fib { int ret; };
     605void main( Fib & f ) with( f ) {
     606        int fn, f1 = 1, f2 = 0;
     607        for ( ;; ) {
     608                ret = f2;
     609
     610                fn = f1 + f2;  f2 = f1;  f1 = fn; `suspend();`
     611        }
     612}
     613int next( Fib & fib ) with( fib ) {
     614        `resume( fib );`
    553615        return ret;
    554616}
    555 int main() {
    556         Fib fib = { 0, 1 };
    557 
    558         for ( int i = 0; i < 10; i++ ) {
    559                 printf( "%d\n", fib_state( &fib ) );
    560         }
    561 }
    562 \end{cfa}
    563 \end{tabular}
    564 \end{center}
    565 \caption{Fibonacci Implementations in C}
    566 \label{lst:fib-c}
     617
     618
     619
     620
     621
     622
     623\end{lstlisting}
     624\end{lrbox}
     625\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
     626\qquad
     627\subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
     628\caption{\CFA Coroutine Fibonacci Implementations}
     629\label{f:fibonacci-cfa}
    567630\end{figure}
    568631
    569 A good example of a problem made easier with coroutines is generators, e.g., generating the Fibonacci sequence.
    570 This problem comes with the challenge of decoupling how a sequence is generated and how it is used.
    571 Listing \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C.
    572 All three of these approach suffer from strong coupling.
    573 The left and centre approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed.
    574 
    575 Listing \ref{lst:fibonacci-cfa} is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
     632Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, which provides communication for multiple interface functions, and the \newterm{coroutine main}, which runs on the coroutine stack.
     633\begin{cfa}
     634`coroutine C { char c; int i; _Bool s; };`      $\C{// used for communication}$
     635void ?{}( C & c ) { s = false; }                        $\C{// constructor}$
     636void main( C & cor ) with( cor ) {                      $\C{// actual coroutine}$
     637        while ( ! s ) // process c
     638        if ( v == ... ) s = false;
     639}
     640// interface functions
     641char cont( C & cor, char ch ) { c = ch; resume( cor ); return c; }
     642_Bool stop( C & cor, int v ) { s = true; i = v; resume( cor ); return s; }
     643\end{cfa}
     644
     645encapsulates the Fibonacci state in the  shows is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
    576646This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used.
    577647Indeed, this version is as easy to use as the @fibonacci_state@ solution, while the implementation is very similar to the @fibonacci_func@ example.
    578648
     649Figure~\ref{f:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
     650The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
     651
    579652\begin{figure}
    580 \begin{cfa}
    581 coroutine Fibonacci { int fn; };                                $\C{// used for communication}$
    582 
    583 void ?{}( Fibonacci & fib ) with( fib ) { fn = 0; } $\C{// constructor}$
    584 
    585 void main( Fibonacci & fib ) with( fib ) {              $\C{// main called on first resume}$
    586         int fn1, fn2;                                                           $\C{// retained between resumes}$
    587         fn = 0;  fn1 = fn;                                                      $\C{// 1st case}$
    588         suspend();                                                                      $\C{// restart last resume}$
    589         fn = 1;  fn2 = fn1;  fn1 = fn;                          $\C{// 2nd case}$
    590         suspend();                                                                      $\C{// restart last resume}$
    591         for ( ;; ) {
    592                 fn = fn1 + fn2; fn2 = fn1;  fn1 = fn;   $\C{// general case}$
    593                 suspend();                                                              $\C{// restart last resume}$
     653\centering
     654\begin{cfa}
     655`coroutine` Format {
     656        char ch;                                                                $\C{// used for communication}$
     657        int g, b;                                                               $\C{// global because used in destructor}$
     658};
     659void ?{}( Format & fmt ) { `resume( fmt );` } $\C{// prime (start) coroutine}$
     660void ^?{}( Format & fmt ) with( fmt ) { if ( g != 0 || b != 0 ) sout | endl; }
     661void main( Format & fmt ) with( fmt ) {
     662        for ( ;; ) {                                                    $\C{// for as many characters}$
     663                for ( g = 0; g < 5; g += 1 ) {          $\C{// groups of 5 blocks}$
     664                        for ( b = 0; b < 4; b += 1 ) {  $\C{// blocks of 4 characters}$
     665                                `suspend();`
     666                                sout | ch;                                      $\C{// print character}$
     667                        }
     668                        sout | "  ";                                    $\C{// print block separator}$
     669                }
     670                sout | endl;                                            $\C{// print group separator}$
    594671        }
    595672}
    596 int next( Fibonacci & fib ) with( fib ) {
    597         resume( fib );                                                          $\C{// restart last suspend}$
    598         return fn;
    599 }
    600 int main() {
    601         Fibonacci f1, f2;
    602         for ( int i = 1; i <= 10; i++ ) {
    603                 sout | next( f1 ) | next( f2 ) | endl;
    604         }
    605 }
    606 \end{cfa}
    607 \caption{Coroutine Fibonacci }
    608 \label{lst:fibonacci-cfa}
    609 \end{figure}
    610 
    611 Listing \ref{lst:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
    612 The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
    613 
    614 \begin{figure}
    615 \begin{cfa}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
    616 // format characters into blocks of 4 and groups of 5 blocks per line
    617 coroutine Format {
    618         char ch;                                                                        // used for communication
    619         int g, b;                                                               // global because used in destructor
    620 };
    621 
    622 void  ?{}(Format& fmt) {
    623         resume( fmt );                                                  // prime (start) coroutine
    624 }
    625 
    626 void ^?{}(Format& fmt) with fmt {
    627         if ( fmt.g != 0 || fmt.b != 0 )
    628         sout | endl;
    629 }
    630 
    631 void main(Format& fmt) with fmt {
    632         for ( ;; ) {                                                    // for as many characters
    633                 for(g = 0; g < 5; g++) {                // groups of 5 blocks
    634                         for(b = 0; b < 4; fb++) {       // blocks of 4 characters
    635                                 suspend();
    636                                 sout | ch;                                      // print character
    637                         }
    638                         sout | "  ";                                    // print block separator
    639                 }
    640                 sout | endl;                                            // print group separator
    641         }
    642 }
    643 
    644 void prt(Format & fmt, char ch) {
     673void prt( Format & fmt, char ch ) {
    645674        fmt.ch = ch;
    646         resume(fmt);
    647 }
    648 
     675        `resume( fmt );`
     676}
    649677int main() {
    650678        Format fmt;
    651679        char ch;
    652         Eof: for ( ;; ) {                                               // read until end of file
    653                 sin | ch;                                                       // read one character
    654                 if(eof(sin)) break Eof;                 // eof ?
    655                 prt(fmt, ch);                                           // push character for formatting
     680        for ( ;; ) {                                                    $\C{// read until end of file}$
     681                sin | ch;                                                       $\C{// read one character}$
     682          if ( eof( sin ) ) break;                              $\C{// eof ?}$
     683                prt( fmt, ch );                                         $\C{// push character for formatting}$
    656684        }
    657685}
    658686\end{cfa}
     687\caption{Formatting text into lines of 5 blocks of 4 characters.}
     688\label{f:fmt-line}
    659689\end{figure}
    660690
    661 \subsection{Construction}
     691\begin{figure}
     692\centering
     693\lstset{language=CFA,escapechar={},moredelim=**[is][\protect\color{red}]{`}{`}}
     694\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
     695\begin{cfa}
     696`coroutine` Prod {
     697        Cons & c;
     698        int N, money, receipt;
     699};
     700void main( Prod & prod ) with( prod ) {
     701        // 1st resume starts here
     702        for ( int i = 0; i < N; i += 1 ) {
     703                int p1 = random( 100 ), p2 = random( 100 );
     704                sout | p1 | " " | p2 | endl;
     705                int status = delivery( c, p1, p2 );
     706                sout | " $" | money | endl | status | endl;
     707                receipt += 1;
     708        }
     709        stop( c );
     710        sout | "prod stops" | endl;
     711}
     712int payment( Prod & prod, int money ) {
     713        prod.money = money;
     714        `resume( prod );`
     715        return prod.receipt;
     716}
     717void start( Prod & prod, int N, Cons &c ) {
     718        &prod.c = &c;
     719        prod.[N, receipt] = [N, 0];
     720        `resume( prod );`
     721}
     722int main() {
     723        Prod prod;
     724        Cons cons = { prod };
     725        srandom( getpid() );
     726        start( prod, 5, cons );
     727}
     728\end{cfa}
     729&
     730\begin{cfa}
     731`coroutine` Cons {
     732        Prod & p;
     733        int p1, p2, status;
     734        _Bool done;
     735};
     736void ?{}( Cons & cons, Prod & p ) {
     737        &cons.p = &p;
     738        cons.[status, done ] = [0, false];
     739}
     740void ^?{}( Cons & cons ) {}
     741void main( Cons & cons ) with( cons ) {
     742        // 1st resume starts here
     743        int money = 1, receipt;
     744        for ( ; ! done; ) {
     745                sout | p1 | " " | p2 | endl | " $" | money | endl;
     746                status += 1;
     747                receipt = payment( p, money );
     748                sout | " #" | receipt | endl;
     749                money += 1;
     750        }
     751        sout | "cons stops" | endl;
     752}
     753int delivery( Cons & cons, int p1, int p2 ) {
     754        cons.[p1, p2] = [p1, p2];
     755        `resume( cons );`
     756        return cons.status;
     757}
     758void stop( Cons & cons ) {
     759        cons.done = true;
     760        `resume( cons );`
     761}
     762
     763\end{cfa}
     764\end{tabular}
     765\caption{Producer / consumer: resume-resume cycle, bi-directional communication}
     766\label{f:ProdCons}
     767\end{figure}
     768
     769
     770\subsubsection{Construction}
     771
    662772One important design challenge for implementing coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system.
    663773In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling.
     
    702812}
    703813\end{cfa}
    704 The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; i.e., the stack-based thunk being destroyed before it can be used.
     814The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; \ie the stack-based thunk being destroyed before it can be used.
    705815This challenge is an extension of challenges that come with second-class routines.
    706816Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope.
    707817The case of coroutines and threads is simply an extension of this problem to multiple call stacks.
    708818
    709 \subsection{Alternative: Composition}
     819
     820\subsubsection{Alternative: Composition}
     821
    710822One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
    711823
     
    731843This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically.
    732844
    733 \subsection{Alternative: Reserved keyword}
     845
     846\subsubsection{Alternative: Reserved keyword}
     847
    734848The next alternative is to use language support to annotate coroutines as follows:
    735 
    736849\begin{cfa}
    737850coroutine Fibonacci {
     
    746859The reserved keywords are only present to improve ease of use for the common cases.
    747860
    748 \subsection{Alternative: Lambda Objects}
     861
     862\subsubsection{Alternative: Lambda Objects}
    749863
    750864For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
     
    776890As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity.
    777891
    778 \subsection{Alternative: Trait-Based Coroutines}
     892
     893\subsubsection{Alternative: Trait-Based Coroutines}
    779894
    780895Finally, the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines.
     
    821936The combination of these two approaches allows users new to coroutining and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.
    822937
    823 \section{Thread Interface}\label{threads}
     938\subsection{Thread Interface}\label{threads}
    824939The basic building blocks of multithreading in \CFA are \textbf{cfathread}.
    825940Both user and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism.
     
    9291044\end{cfa}
    9301045
    931 However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, i.e., they are always destroyed in the opposite order of construction because of C scoping rules.
     1046However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, \ie they are always destroyed in the opposite order of construction because of C scoping rules.
    9321047This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created.
    9331048
     
    9701085Since many of these challenges appear with the use of mutable shared state, some languages and libraries simply disallow mutable shared state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}).
    9711086In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (channels~\cite{CSP,Go} for example).
    972 However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine calls).
     1087However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (\ie message passing versus routine calls).
    9731088This distinction in turn means that, in order to be effective, programmers need to learn two sets of design patterns.
    9741089While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
     
    9841099One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared-memory systems, is the \emph{monitor}.
    9851100Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}.
    986 Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
     1101Many programming languages---\eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
    9871102In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors.
    9881103For these reasons, this project proposes monitors as the core concurrency construct.
    9891104
    990 \section{Basics}
     1105
     1106\subsection{Basics}
     1107
    9911108Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization.
    9921109Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access.
    9931110On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads.
    9941111
    995 \subsection{Mutual-Exclusion}
     1112
     1113\subsubsection{Mutual-Exclusion}
     1114
    9961115As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once.
    9971116However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
    9981117Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to  higher-level concurrency techniques, which sacrifice some performance in order to improve ease of use.
    999 Ease of use comes by either guaranteeing some problems cannot occur (e.g., being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
    1000 For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (e.g., reading/writing large types atomically).
     1118Ease of use comes by either guaranteeing some problems cannot occur (\eg being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
     1119For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically).
    10011120Another challenge with low-level locks is composability.
    10021121Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
    10031122Easing composability is another feature higher-level mutual-exclusion mechanisms often offer.
    10041123
    1005 \subsection{Synchronization}
     1124
     1125\subsubsection{Synchronization}
     1126
    10061127As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.
    1007 Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (e.g., message passing) or offering a simpler solution to otherwise involved challenges.
     1128Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (\eg message passing) or offering a simpler solution to otherwise involved challenges.
    10081129As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}.
    10091130Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order.
     
    10161137Algorithms that use flag variables to detect barging threads are said to be using barging avoidance, while algorithms that baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
    10171138
     1139
    10181140% ======================================================================
    10191141% ======================================================================
     
    10491171Another aspect to consider is when a monitor acquires its mutual exclusion.
    10501172For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry.
    1051 Passthrough can occur for generic helper routines (@swap@, @sort@, etc.) or specific helper routines like the following to implement an atomic counter:
     1173Passthrough can occur for generic helper routines (@swap@, @sort@, \etc) or specific helper routines like the following to implement an atomic counter:
    10521174
    10531175\begin{cfa}
     
    12071329
    12081330The call semantics discussed above have one software engineering issue: only a routine can acquire the mutual-exclusion of a set of monitor. \CFA offers the @mutex@ statement to work around the need for unnecessary names, avoiding a major software engineering problem~\cite{2FTwoHardThings}.
    1209 Table \ref{lst:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
     1331Table \ref{f:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
    12101332Beyond naming, the @mutex@ statement has no semantic difference from a routine call with @mutex@ parameters.
    12111333
     
    12371359\end{center}
    12381360\caption{Regular call semantics vs. \protect\lstinline|mutex| statement}
    1239 \label{lst:mutex-stmt}
     1361\label{f:mutex-stmt}
    12401362\end{table}
    12411363
     
    12861408In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronization.
    12871409With monitors, this capability is generally achieved with internal or external scheduling as in~\cite{Hoare74}.
    1288 With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (i.e., with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (i.e., without access to the shared state).
     1410With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (\ie with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (\ie without access to the shared state).
    12891411Since internal scheduling within a single monitor is mostly a solved problem, this paper concentrates on extending internal scheduling to multiple monitors.
    12901412Indeed, like the \textbf{bulk-acq} semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
     
    13131435There are two details to note here.
    13141436First, @signal@ is a delayed operation; it only unblocks the waiting thread when it reaches the end of the critical section.
    1315 This semantics is needed to respect mutual-exclusion, i.e., the signaller and signalled thread cannot be in the monitor simultaneously.
     1437This semantics is needed to respect mutual-exclusion, \ie the signaller and signalled thread cannot be in the monitor simultaneously.
    13161438The alternative is to return immediately after the call to @signal@, which is significantly more restrictive.
    13171439Second, in \CFA, while it is common to store a @condition@ as a field of the monitor, a @condition@ variable can be stored/created independently of a monitor.
     
    14311553
    14321554A larger example is presented to show complex issues for \textbf{bulk-acq} and its implementation options are analyzed.
    1433 Listing \ref{lst:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{lst:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{lst:int-bulk-cfa}.
    1434 For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, e.g., @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
     1555Figure~\ref{f:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{f:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{f:int-bulk-cfa}.
     1556For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, \eg @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
    14351557
    14361558\begin{figure}
     
    14621584\end{cfa}
    14631585\end{multicols}
    1464 \begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={lst:int-bulk-cfa}]
     1586\begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={f:int-bulk-cfa}]
    14651587\end{cfa}
    14661588\begin{center}
     
    14981620\end{cfa}
    14991621\end{multicols}
    1500 \begin{cfa}[caption={Equivalent \CFA code for listing \ref{lst:int-bulk-cfa}},label={lst:int-bulk-cfa}]
     1622\begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
    15011623\end{cfa}
    15021624\begin{multicols}{2}
     
    15231645\end{cfa}
    15241646\end{multicols}
    1525 \begin{cfa}[caption={Listing \ref{lst:int-bulk-cfa}, with delayed signalling comments},label={lst:int-secret}]
     1647\begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
    15261648\end{cfa}
    15271649\end{figure}
    15281650
    1529 The complexity begins at code sections 4 and 8 in listing \ref{lst:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
     1651The complexity begins at code sections 4 and 8 in listing \ref{f:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
    15301652The root of the problem is that \textbf{bulk-acq} is used in a context where one of the monitors is already acquired, which is why it is important to define the behaviour of the previous cfa-code.
    1531 When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{lst:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
     1653When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{f:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
    15321654This ownership transfer is required in order to prevent barging into @B@ by another thread, since both the signalling and signalled threads still need monitor @A@.
    15331655There are three options:
     
    15381660This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from multiple objects to a single group of objects, effectively making the existing single-monitor semantic viable by simply changing monitors to monitor groups.
    15391661This solution releases the monitors once every monitor in a group can be released.
    1540 However, since some monitors are never released (e.g., the monitor of a thread), this interpretation means a group might never be released.
     1662However, since some monitors are never released (\eg the monitor of a thread), this interpretation means a group might never be released.
    15411663A more interesting interpretation is to transfer the group until all its monitors are released, which means the group is not passed further and a thread can retain its locks.
    15421664
    1543 However, listing \ref{lst:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
    1544 Listing \ref{lst:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
     1665However, listing \ref{f:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
     1666Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
    15451667Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
    1546 Depending on the order of signals (listing \ref{lst:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
     1668Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    15471669
    15481670\paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
     
    15511673
    15521674Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order.
    1553 However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{lst:dependency}.
     1675However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
    15541676
    15551677In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
     
    15861708\end{cfa}
    15871709\end{multicols}
    1588 \begin{cfa}[caption={Pseudo-code for the three thread example.},label={lst:dependency}]
     1710\begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
    15891711\end{cfa}
    15901712\begin{center}
    15911713\input{dependency}
    15921714\end{center}
    1593 \caption{Dependency graph of the statements in listing \ref{lst:dependency}}
     1715\caption{Dependency graph of the statements in listing \ref{f:dependency}}
    15941716\label{fig:dependency}
    15951717\end{figure}
    15961718
    1597 In listing \ref{lst:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
     1719In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
    15981720If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
    15991721Dynamically finding the correct order is therefore the second possible solution.
    16001722The problem is effectively resolving a dependency graph of ownership requirements.
    16011723Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
    1602 This complexity can be seen in listing \ref{lst:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
     1724This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
    16031725Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
    16041726\begin{figure}
     
    16261748\end{cfa}
    16271749\end{multicols}
    1628 \begin{cfa}[caption={Extension to three monitors of listing \ref{lst:int-bulk-cfa}},label={lst:explosion}]
     1750\begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
    16291751\end{cfa}
    16301752\end{figure}
    16311753
    1632 Given the three threads example in listing \ref{lst:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (e.g., $\alpha1$ must happen before $\alpha2$).
     1754Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
    16331755The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
    16341756Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
     
    16361758\subsubsection{Partial Signalling} \label{partial-sig}
    16371759Finally, the solution that is chosen for \CFA is to use partial signalling.
    1638 Again using listing \ref{lst:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
     1760Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
    16391761Only when it reaches line \ref{line:lastRelease} does it actually wake up the waiting thread.
    16401762This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
     
    16421764Furthermore, after being fully implemented, this solution does not appear to have any significant downsides.
    16431765
    1644 Using partial signalling, listing \ref{lst:dependency} can be solved easily:
     1766Using partial signalling, listing \ref{f:dependency} can be solved easily:
    16451767\begin{itemize}
    16461768        \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
     
    18071929This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    18081930Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
    1809 External scheduling can generally be done either in terms of control flow (e.g., Ada with @accept@, \uC with @_Accept@) or in terms of data (e.g., Go with channels).
     1931External scheduling can generally be done either in terms of control flow (\eg Ada with @accept@, \uC with @_Accept@) or in terms of data (\eg Go with channels).
    18101932Of course, both of these paradigms have their own strengths and weaknesses, but for this project, control-flow semantics was chosen to stay consistent with the rest of the languages semantics.
    18111933Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
     
    18731995
    18741996There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy.
    1875 Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (e.g., 128) of mutex members.
     1997Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (\eg 128) of mutex members.
    18761998This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units.
    18771999For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance.
     
    18832005Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
    18842006Storing an array of accepted function pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
    1885 Furthermore, supporting nested external scheduling (e.g., listing \ref{lst:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
     2007Furthermore, supporting nested external scheduling (\eg listing \ref{f:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
    18862008
    18872009\begin{figure}
    1888 \begin{cfa}[caption={Example of nested external scheduling},label={lst:nest-ext}]
     2010\begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
    18892011monitor M {};
    18902012void foo( M & mutex a ) {}
     
    19912113While the set of monitors can be any list of expressions, the function name is more restricted because the compiler validates at compile time the validity of the function type and the parameters used with the @waitfor@ statement.
    19922114It checks that the set of monitors passed in matches the requirements for a function call.
    1993 Listing \ref{lst:waitfor} shows various usages of the waitfor statement and which are acceptable.
     2115Figure~\ref{f:waitfor} shows various usages of the waitfor statement and which are acceptable.
    19942116The choice of the function type is made ignoring any non-@mutex@ parameter.
    19952117One limitation of the current implementation is that it does not handle overloading, but overloading is possible.
    19962118\begin{figure}
    1997 \begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={lst:waitfor}]
     2119\begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={f:waitfor}]
    19982120monitor A{};
    19992121monitor B{};
     
    20322154A @waitfor@ chain can also be followed by a @timeout@, to signify an upper bound on the wait, or an @else@, to signify that the call should be non-blocking, which checks for a matching function call already arrived and otherwise continues.
    20332155Any and all of these clauses can be preceded by a @when@ condition to dynamically toggle the accept clauses on or off based on some current state.
    2034 Listing \ref{lst:waitfor2} demonstrates several complex masks and some incorrect ones.
     2156Figure~\ref{f:waitfor2} demonstrates several complex masks and some incorrect ones.
    20352157
    20362158\begin{figure}
     
    20822204\end{cfa}
    20832205\caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement}
    2084 \label{lst:waitfor2}
     2206\label{f:waitfor2}
    20852207\end{figure}
    20862208
     
    20962218However, a more expressive approach is to flip ordering of execution when waiting for the destructor, meaning that waiting for the destructor allows the destructor to run after the current @mutex@ routine, similarly to how a condition is signalled.
    20972219\begin{figure}
    2098 \begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={lst:dtor-order}]
     2220\begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={f:dtor-order}]
    20992221monitor Executer {};
    21002222struct  Action;
     
    21122234\end{cfa}
    21132235\end{figure}
    2114 For example, listing \ref{lst:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
     2236For example, listing \ref{f:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
    21152237Switching the semantic meaning introduces an idiomatic way to terminate a task and/or wait for its termination via destruction.
    21162238
     
    21282250In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism.
    21292251Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization.
    2130 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, etc.
     2252The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, \etc.
    21312253However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one.
    21322254There are several alternatives to solve these issues that all have strengths and weaknesses.
     
    21662288While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
    21672289Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
    2168 Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (i.e., no thread stack per job).
     2290Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (\ie no thread stack per job).
    21692291However, interactions among jobs can easily exacerbate contention.
    21702292User-level threads allow fine-grain context switching, which results in better resource utilization, but a context switch is more expensive and the extra control means users need to tweak more variables to get the desired performance.
     
    22182340
    22192341The first step towards the monitor implementation is simple @mutex@ routines.
    2220 In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{lst:entry1}.
     2342In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{f:entry1}.
    22212343The entry/exit procedures do not have to be extended to support multiple monitors.
    22222344Indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlock~\cite{Havender68}.
     
    22462368\end{cfa}
    22472369\end{multicols}
    2248 \begin{cfa}[caption={Initial entry and exit routine for monitors},label={lst:entry1}]
     2370\begin{cfa}[caption={Initial entry and exit routine for monitors},label={f:entry1}]
    22492371\end{cfa}
    22502372\end{figure}
     
    22562378First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
    22572379Therefore, the main question is how to support @dtype@ polymorphism.
    2258 It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, i.e., acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
     2380It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, \ie acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
    22592381For example:
    22602382\begin{table}
     
    23132435\end{table}
    23142436
    2315 Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, e.g.:
     2437Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, \eg:
    23162438\begin{cfa}
    23172439// Incorrect: T may not be monitor
     
    23262448Both entry point and \textbf{callsite-locking} are feasible implementations.
    23272449The current \CFA implementation uses entry-point locking because it requires less work when using \textbf{raii}, effectively transferring the burden of implementation to object construction/destruction.
    2328 It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, i.e., the function body.
     2450It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, \ie the function body.
    23292451For example, the monitor call can appear in the middle of an expression.
    23302452Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
     
    23592481Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
    23602482Normally, coroutines also create their own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the \textbf{kthread} stack, effectively stealing the processor stack.
    2361 The exception to this rule is the Main Processor, i.e., the initial \textbf{kthread} that is given to any program.
     2483The exception to this rule is the Main Processor, \ie the initial \textbf{kthread} that is given to any program.
    23622484In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
    23632485
     
    23902512When the preemption system receives a change in preemption, it inserts the time in a sorted order and sets a kernel timer for the closest one, effectively stepping through preemption events on each signal sent by the timer.
    23912513These timers use the Linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread.
    2392 This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, i.e.:
     2514This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, \ie:
    23932515\begin{quote}
    23942516A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked.
     
    24062528However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks.
    24072529For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption.
    2408 One final detail about the alarm thread is how to wake it when additional communication is required (e.g., on thread termination).
     2530One final detail about the alarm thread is how to wake it when additional communication is required (\eg on thread termination).
    24092531This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@.
    24102532Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
     
    24452567\end{figure}
    24462568
    2447 This picture and the proper entry and leave algorithms (see listing \ref{lst:entry2}) is the fundamental implementation of internal scheduling.
     2569This picture and the proper entry and leave algorithms (see listing \ref{f:entry2}) is the fundamental implementation of internal scheduling.
    24482570Note that when a thread is moved from the condition to the AS-stack, it is conceptually split into N pieces, where N is the number of monitors specified in the parameter list.
    24492571The thread is woken up when all the pieces have popped from the AS-stacks and made active.
     
    24782600\end{cfa}
    24792601\end{multicols}
    2480 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={lst:entry2}]
     2602\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={f:entry2}]
    24812603\end{cfa}
    24822604\end{figure}
    24832605
    2484 The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{lst:entry2}.
     2606The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{f:entry2}.
    24852607Basically, the solution boils down to having a separate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership.
    24862608This solution is deadlock safe as well as preventing any potential barging.
     
    24982620The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors.
    24992621The @condition node@ is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each @condition criterion@ is moved to the AS-stack.
    2500 Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{lst:entry2}.
     2622Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{f:entry2}.
    25012623
    25022624% ======================================================================
     
    25062628% ======================================================================
    25072629Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentioned in section \ref{extsched}.
    2508 For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (i.e., no signal statement uses multiple conditions).
     2630For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (\ie no signal statement uses multiple conditions).
    25092631However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements.
    25102632This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired.
     
    25332655Note that if a thread has acquired two monitors but executes a @waitfor@ with only one monitor as a parameter, setting the mask of acceptable routines to both monitors will not cause any problems since the extra monitor will not change ownership regardless.
    25342656This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement.
    2535         \item The entry/exit routines need to be updated as shown in listing \ref{lst:entry3}.
     2657        \item The entry/exit routines need to be updated as shown in listing \ref{f:entry3}.
    25362658\end{itemize}
    25372659
     
    25412663Indeed, when waiting for the destructors, storage is needed for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for.
    25422664For regular @waitfor@ statements, the call stack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later.
    2543 The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
     2665The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{f:entry-dtor}
    25442666
    25452667\begin{figure}
     
    25752697\end{cfa}
    25762698\end{multicols}
    2577 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={lst:entry3}]
     2699\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={f:entry3}]
    25782700\end{cfa}
    25792701\end{figure}
     
    26212743\end{cfa}
    26222744\end{multicols}
    2623 \begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={lst:entry-dtor}]
     2745\begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={f:entry-dtor}]
    26242746\end{cfa}
    26252747\end{figure}
     
    26372759For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine:
    26382760\begin{figure}
    2639 \begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={lst:engine-v1}]
     2761\begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={f:engine-v1}]
    26402762// Visualization declaration
    26412763thread Renderer {} renderer;
     
    26692791Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner:
    26702792\begin{figure}
    2671 \begin{cfa}[caption={Same toy simulator with proper termination condition.},label={lst:engine-v2}]
     2793\begin{cfa}[caption={Same toy simulator with proper termination condition.},label={f:engine-v2}]
    26722794// Visualization declaration
    26732795thread Renderer {} renderer;
     
    27182840}
    27192841\end{cfa}
    2720 This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, i.e., no preemption.
    2721 However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{lst:fiber-uthread}
     2842This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, \ie no preemption.
     2843However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{f:fiber-uthread}
    27222844\begin{figure}
    27232845\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
    2724 \begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={lst:fiber-uthread}]
     2846\begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={f:fiber-uthread}]
    27252847// Cluster forward declaration
    27262848struct cluster;
     
    28312953Yielding causes the thread to context-switch to the scheduler and back, more precisely: from the \textbf{uthread} to the \textbf{kthread} then from the \textbf{kthread} back to the same \textbf{uthread} (or a different one in the general case).
    28322954In order to make the comparison fair, coroutines also execute a 2-step context-switch by resuming another coroutine which does nothing but suspending in a tight loop, which is a resume/suspend cycle instead of a yield.
    2833 Listing \ref{lst:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
     2955Figure~\ref{f:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
    28342956All omitted tests are functionally identical to one of these tests.
    28352957The difference between coroutines and threads can be attributed to the cost of scheduling.
     
    28742996\end{cfa}
    28752997\end{multicols}
    2876 \begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={lst:ctx-switch}]
     2998\begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={f:ctx-switch}]
    28772999\end{cfa}
    28783000\end{figure}
     
    29023024The next interesting benchmark is to measure the overhead to enter/leave a critical-section.
    29033025For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine.
    2904 Listing \ref{lst:mutex} shows the code for \CFA.
     3026Figure~\ref{f:mutex} shows the code for \CFA.
    29053027To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured.
    29063028The results can be shown in table \ref{tab:mutex}.
    29073029
    29083030\begin{figure}
    2909 \begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={lst:mutex}]
     3031\begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={f:mutex}]
    29103032monitor M {};
    29113033void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
     
    29483070\subsection{Internal Scheduling}
    29493071The internal-scheduling benchmark measures the cost of waiting on and signalling a condition variable.
    2950 Listing \ref{lst:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
     3072Figure~\ref{f:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
    29513073As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    29523074
    29533075\begin{figure}
    2954 \begin{cfa}[caption={Benchmark code for internal scheduling},label={lst:int-sched}]
     3076\begin{cfa}[caption={Benchmark code for internal scheduling},label={f:int-sched}]
    29553077volatile int go = 0;
    29563078condition c;
     
    30073129\subsection{External Scheduling}
    30083130The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC).
    3009 Listing \ref{lst:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
     3131Figure~\ref{f:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
    30103132As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    30113133
    30123134\begin{figure}
    3013 \begin{cfa}[caption={Benchmark code for external scheduling},label={lst:ext-sched}]
     3135\begin{cfa}[caption={Benchmark code for external scheduling},label={f:ext-sched}]
    30143136volatile int go = 0;
    30153137monitor M {};
     
    30613183\end{table}
    30623184
     3185
    30633186\subsection{Object Creation}
    30643187Finally, the last benchmark measures the cost of creation for concurrent objects.
    3065 Listing \ref{lst:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
     3188Figure~\ref{f:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
    30663189As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    30673190The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
     
    31073230\end{center}
    31083231\caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation}
    3109 \label{lst:creation}
     3232\label{f:creation}
    31103233\end{figure}
    31113234
     
    31693292While most of the parallelism tools are aimed at data parallelism and control-flow parallelism, many modern workloads are not bound on computation but on IO operations, a common case being web servers and XaaS (anything as a service).
    31703293These types of workloads often require significant engineering around amortizing costs of blocking IO operations.
    3171 At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (e.g., network operations) and registering for notifications instead of waiting for requests to complete.
     3294At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (\eg network operations) and registering for notifications instead of waiting for requests to complete.
    31723295In this context, the role of the language makes Non-Blocking IO easily available and with low overhead.
    31733296The current trend is to use asynchronous programming using tools like callbacks and/or futures and promises, which can be seen in frameworks like Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java and Django~\cite{Django} for Python.
     
    31843307This type of parallelism can be achieved both at the language level and at the library level.
    31853308The canonical example of implicit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithms~\cite{uC++book}.
    3186 Table \ref{lst:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
     3309Table \ref{f:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
    31873310Note that none of these examples explicitly declare any concurrency or parallelism objects.
    31883311
     
    32673390\end{center}
    32683391\caption{For loop to sum numbers: Sequential, using library parallelism and language parallelism.}
    3269 \label{lst:parfor}
     3392\label{f:parfor}
    32703393\end{table}
    32713394
Note: See TracChangeset for help on using the changeset viewer.