Ignore:
Timestamp:
Apr 22, 2018, 9:49:50 AM (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:
22bdc34, da7fe39
Parents:
58caf150
Message:

updates

File:
1 edited

Legend:

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

    r58caf150 rc8ad5d9  
    1919\usepackage{listings}                                           % format program code
    2020\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
    21 \renewcommand{\thesubfigure}{(\alph{subfigure})}
     21\renewcommand{\thesubfigure}{(\Alph{subfigure})}
     22\captionsetup{justification=raggedright,singlelinecheck=false}
    2223\usepackage{siunitx}
    2324\sisetup{ binary-units=true }
     
    9899\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
    99100\@ifundefined{eg}{
    100 \newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
     101\newcommand{\EG}{\abbrevFont{e}\abbrevFont{g}}
    101102\newcommand*{\eg}{%
    102103        \@ifnextchar{,}{\EG}%
     
    105106}}{}%
    106107\@ifundefined{ie}{
    107 \newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
     108\newcommand{\IE}{\abbrevFont{i}\abbrevFont{e}}
    108109\newcommand*{\ie}{%
    109110        \@ifnextchar{,}{\IE}%
     
    143144                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
    144145                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
    145                 coroutine, disable, dtype, enable, __extension__, exception, fallthrough, fallthru, finally,
     146                coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally,
    146147                __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
    147148                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
     
    169170literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1
    170171        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    171         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2,
     172        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2,
    172173moredelim=**[is][\color{red}]{`}{`},
    173174}% lstset
     
    216217\author[1]{Thierry Delisle}
    217218\author[1]{Peter A. Buhr*}
    218 \authormark{Thierry Delisle \textsc{et al}}
    219 
    220 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
    221 
    222 \corres{*Peter A. Buhr, \email{pabuhr{\char`\@}uwaterloo.ca}}
    223 \presentaddress{Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
    224 
     219\authormark{DELISLE \textsc{et al.}}
     220
     221\address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, ON}, \country{Canada}}}
     222
     223\corres{*Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON, N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}}
     224
     225\fundingInfo{Natural Sciences and Engineering Research Council of Canada}
    225226
    226227\abstract[Summary]{
    227228\CFA is a modern, polymorphic, \emph{non-object-oriented} extension of the C programming language.
    228229This paper discusses the design of the concurrency and parallelism features in \CFA, and the concurrent runtime-system.
    229 These features are created from scratch as ISO C lacks concurrency, relying largely on pthreads.
     230These features are created from scratch as ISO C lacks concurrency, relying largely on pthreads library.
    230231Coroutines and lightweight (user) threads are introduced into the language.
    231232In addition, monitors are added as a high-level mechanism for mutual exclusion and synchronization.
     
    255256Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}.
    256257
    257 This paper used the following terminology.
     258This paper uses the following terminology.
    258259A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state.
    259 Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data.
     260Multiple simultaneous threads give rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data.
    260261% Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, \etc) concurrent threads are introduced.
    261262\newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety.
    262263\newterm{Parallelism} is running multiple threads simultaneously.
    263264Parallelism implies \emph{actual} simultaneous execution, where concurrency only requires \emph{apparent} simultaneous execution.
    264 As such, parallelism is only observable in differences in performance, which is observed through differences in timing.
     265As such, parallelism only affects performance, which is observed through differences in space and/or time.
    265266
    266267Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism.
    267 While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
     268While these two concepts are often combined, they are distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
    268269Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization.
    269270
     
    278279
    279280The following is a quick introduction to the \CFA language, specifically tailored to the features needed to support concurrency.
    280 
    281 \CFA is an extension of ISO-C and therefore supports all of the same paradigms as C.
    282 It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily.
     281Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
     282
     283\CFA is an extension of ISO-C, and therefore, supports all of the same paradigms as C.
     284%It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily.
    283285Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code.
    284286The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C.
    285 Interestingly, 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
     287Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (\eg @this@) and inheritance, 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
    286288values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects.
    287 Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
    288289
    289290
     
    293294In regards to concurrency, the semantic difference between pointers and references are not particularly relevant, but since this document uses mostly references, here is a quick overview of the semantics:
    294295\begin{cfa}
    295 int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
    296         &r1 = x,    &&r2 = r1,   &&&r3 = r2;
    297 ***p3 = 3;                                                      $\C{// change x}$
    298 r3    = 3;                                                      $\C{// change x, ***r3}$
    299 **p3  = ...;                                            $\C{// change p1}$
    300 *p3   = ...;                                            $\C{// change p2}$
    301 int y, z, & ar[3] = {x, y, z};          $\C{// initialize array of references}$
    302 typeof( ar[1]) p;                                       $\C{// is int, referenced object type}$
    303 typeof(&ar[1]) q;                                       $\C{// is int \&, reference type}$
    304 sizeof( ar[1]) == sizeof(int);          $\C{// is true, referenced object size}$
    305 sizeof(&ar[1]) == sizeof(int *);        $\C{// is true, reference size}$
     296int x, y, z;
     297int * p1 = &x, ** p2 = &p1, *** p3 = &p2,       $\C{// pointers to x}$
     298        & r1 = x,   && r2 = r1, &&& r3 = r2;    $\C{// references to x}$
     299
     300*p1 = 3; **p2 = 3; ***p3 = 3;                           $\C{// change x}$
     301  r1 = 3;    r2 = 3;      r3 = 3;                       $\C{// change x}$
     302**p3 = &y; *p3 = &z;                                            $\C{// change p1, p2}$
     303&&r3 = &y; &r3 = &z;                                            $\C{// change p1, p2}$
     304int & ar[3] = {x, y, z};                                        $\C{// initialize array of references}$
     305
     306typeof( ar[1]) p;                                                       $\C{// is int, referenced object type}$
     307typeof(&ar[1]) q;                                                       $\C{// is int \&, reference type}$
     308sizeof( ar[1]) == sizeof(int);                          $\C{// is true, referenced object size}$
     309sizeof(&ar[1]) == sizeof(int *);                        $\C{// is true, reference size}$
    306310\end{cfa}
    307311The important take away from this code example is that a reference offers a handle to an object, much like a pointer, but which is automatically dereferenced for convenience.
     
    626630\end{lrbox}
    627631\subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
    628 \qquad
     632\qquad\qquad
    629633\subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
    630634\caption{\CFA Coroutine Fibonacci Implementations}
     
    653657
    654658\begin{figure}
    655 \centering
    656 \begin{cfa}
     659\begin{cfa}[xleftmargin=4\parindentlnth]
    657660`coroutine` Format {
    658661        char ch;                                                                $\C{// used for communication}$
Note: See TracChangeset for help on using the changeset viewer.