Changes in / [281806b6:4ab3d68e]


Ignore:
Location:
doc
Files:
6 added
5 deleted
18 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/OOPSLA17/.gitignore

    r281806b6 r4ab3d68e  
    11# generated by latex
    2 build/*
     2*.aux
     3*.bbl
     4*.blg
     5*.brf
     6*.dvi
     7*.idx
     8*.ilg
     9*.ind
     10*.log
     11*.out
    312*.pdf
    413*.ps
     14*.toc
     15*.lof
     16*.lot
     17*.synctex.gz
     18comment.cut
     19timing.tex

  • doc/papers/OOPSLA17/Makefile

    r281806b6 r4ab3d68e  
    1 ## Define the configuration variables.
     1## Define the appropriate configuration variables.
    22
    3 Build = build
    4 Figures = figures
    5 Macros = ../../LaTeXmacros
    6 TeXLIB = .:${Macros}:${Build}:../../bibliography:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     3TeXLIB = .:../LaTeXmacros:../LaTeXmacros/listings:../LaTeXmacros/enumitem:../bibliography/:
     4LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
    85BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    9 
    10 MAKEFLAGS = --no-print-directory --silent #
    11 VPATH = ${Figures} evaluation
    126
    137## Define the text source files.
    … …  
    3933
    4034clean :
    41         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     35        rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
     36                ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
    4237
    4338# File Dependencies #
    … …  
    4742
    4843${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    49         dvips ${Build}/$< -o $@
     44        dvips $< -o $@
    5045
    51 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../../bibliography/pl.bib
     46#${DOCUMENT} : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
     47
     48${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../bibliography/cfa.bib
     49        # Conditionally create an empty *.idx (index) file for inclusion until makeindex is run.
     50        if [ ! -r ${basename $@}.idx ] ; then touch ${basename $@}.idx ; fi
    5251        # Must have *.aux file containing citations for bibtex
    5352        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    54         -${BibTeX} ${Build}/${basename $@}
    55         # Some citations reference others so run again to resolve these citations
     53        -${BibTeX} ${basename $@}
     54        # Some citations reference others so run steps again to resolve these citations
    5655        ${LaTeX} ${basename $@}.tex
    57         -${BibTeX} ${Build}/${basename $@}
    58         # Run again to finish citations
     56        -${BibTeX} ${basename $@}
     57        # Make index from *.aux entries and input index at end of document
     58        makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx
    5959        ${LaTeX} ${basename $@}.tex
     60        # Run again to get index title into table of contents
     61        ${LaTeX} ${basename $@}.tex
     62
     63predefined :
     64        sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf
    6065
    6166## Define the default recipes.
    6267
    63 ${Build}:
    64         mkdir -p ${Build}
    65 
    66 ${GRAPHS} : timing.gp timing.dat
    67         gnuplot -e Build="'${Build}/'" evaluation/timing.gp
     68${GRAPHS} : evaluation/timing.gp evaluation/timing.dat
     69        gnuplot evaluation/timing.gp
    6870
    6971%.tex : %.fig
    70         fig2dev -L eepic $< > ${Build}/$@
     72        fig2dev -L eepic $< > $@
    7173
    7274%.ps : %.fig
    73         fig2dev -L ps $< > ${Build}/$@
     75        fig2dev -L ps $< > $@
    7476
    7577%.pstex : %.fig
    76         fig2dev -L pstex $< > ${Build}/$@
    77         fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
     78        fig2dev -L pstex $< > $@
     79        fig2dev -L pstex_t -p $@ $< > $@_t
    7880
    7981# Local Variables: #

  • doc/papers/OOPSLA17/evaluation/timing.gp

    r281806b6 r4ab3d68e  
    22# set output "timing.pdf"
    33set terminal pslatex size 6.25,2.125 color solid
    4 set output Build."timing.tex"
     4set output "timing.tex"
    55
    66set pointsize 2.0

  • doc/papers/OOPSLA17/generic_types.tex

    r281806b6 r4ab3d68e  
    11091109
    11101110\bibliographystyle{ACM-Reference-Format}
    1111 \bibliography{pl}
     1111\bibliography{cfa}
    11121112
    11131113

  • doc/papers/concurrency/.gitignore

    r281806b6 r4ab3d68e  
    1 # generated by latex
    21build/*
    32*.pdf

  • doc/papers/concurrency/Makefile

    r281806b6 r4ab3d68e  
    22
    33Build = build
    4 Figures = figures
    54Macros = ../../LaTeXmacros
    6 TeXLIB = .:style:annex:${Macros}:${Build}:../../bibliography:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     5TeXLIB = .:style:annex:${Macros}:${Build}:/usr/local/bibliographies:
     6LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -interaction=nonstopmode
    87BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    98
    109MAKEFLAGS = --no-print-directory --silent #
    11 VPATH = ${Figures}
    1210
    1311## Define the text source files.
    … …  
    4341# Directives #
    4442
    45 .PHONY : all clean                                      # not file names
     43.PHONY : all clean                                                                              # not file names
    4644
    4745all : ${DOCUMENT}
    … …  
    5957
    6058${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    61                 ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib ../../bibliography/pl.bib
    62         # Must have *.aux file containing citations for bibtex
    63         if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    64         -${BibTeX} ${Build}/${basename $@}
    65         # Some citations reference others so run again to resolve these citations
     59                        ${Macros}/common.tex ${Macros}/indexstyle annex/local.bib /usr/local/bibliographies/pl.bib
     60        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi # Must have *.aux file containing citations for bibtex
     61        -${BibTeX} ${Build}/${basename $@}                                      # Some citations reference others so run again to resolve these citations
    6662        ${LaTeX} ${basename $@}.tex
    6763        -${BibTeX} ${Build}/${basename $@}
    68         # Run again to finish citations
    69         ${LaTeX} ${basename $@}.tex
     64        ${LaTeX} ${basename $@}.tex                                                     # Finish citations
    7065
    7166## Define the default recipes.
     67
     68vpath %.tex ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
     69vpath %.fig ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    7270
    7371${Build}:
    7472        mkdir -p ${Build}
    7573
    76 %.tex : %.fig
     74%.tex : figures/%.fig
    7775        fig2dev -L eepic $< > ${Build}/$@
    7876
    79 %.ps : %.fig
     77%.ps : figures/%.fig
    8078        fig2dev -L ps $< > ${Build}/$@
    8179
    82 %.pstex : %.fig
     80%.pstex : figures/%.fig
    8381        fig2dev -L pstex $< > ${Build}/$@
    8482        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    8583
    8684# Local Variables: #
     85# tab-width : 4 #
    8786# compile-command: "make" #
    8887# End: #

  • doc/papers/concurrency/Paper.tex

    r281806b6 r4ab3d68e  
    1 % inline code ©...© (copyright symbol) emacs: C-q M-)
    2 % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    3 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    4 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    5 % LaTex escape §...§ (section symbol) emacs: C-q M-'
    6 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
     1% requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
     2
     3% inline code �...� (copyright symbol) emacs: C-q M-)
     4% red highlighting �...� (registered trademark symbol) emacs: C-q M-.
     5% blue highlighting �...� (sharp s symbol) emacs: C-q M-_
     6% green highlighting �...� (cent symbol) emacs: C-q M-"
     7% LaTex escape �...� (section symbol) emacs: C-q M-'
     8% keyword escape �...� (pilcrow symbol) emacs: C-q M-^
    79% math escape $...$ (dollar symbol)
    810
    … …  
    1820\usepackage{epic,eepic}
    1921\usepackage{upquote}                                            % switch curled `'" to straight
     22\usepackage{dirtytalk}
    2023\usepackage{calc}
    2124\usepackage{xspace}
    … …  
    4346\urlstyle{rm}
    4447
     48\usepackage{tikz}
     49\def\checkmark{\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;}
     50
    4551\setlength{\topmargin}{-0.45in}                         % move running title into header
    4652\setlength{\headsep}{0.25in}
    … …  
    7278
    7379\title{Concurrency in \CFA}
    74 \author{Thierry Delisle and Peter A. Buhr, Waterloo, Ontario, Canada}
     80\author{Thierry Delisle, Waterloo, Ontario, Canada, 2018}
    7581
    7682
    … …  
    7985
    8086\begin{abstract}
    81 \CFA is a modern, \emph{non-object-oriented} extension of the C programming language.
    82 This paper serves as a definition and an implementation for the concurrency and parallelism \CFA offers. These features are created from scratch due to the lack of concurrency in ISO C. Lightweight threads are introduced into the language. In addition, monitors are introduced as a high-level tool for control-flow based synchronization and mutual-exclusion. The main contributions of this paper are two-fold: it extends the existing semantics of monitors introduce by~\cite{Hoare74} to handle monitors in groups and also details the engineering effort needed to introduce these features as core language features. Indeed, these features are added with respect to expectations of C programmers, and integrate with the \CFA type-system and other language features.
     87\CFA is a modern, non-object-oriented extension of the C programming language. This thesis serves as a definition and an implementation for the concurrency and parallelism \CFA offers. These features are created from scratch due to the lack of concurrency in ISO C. Lightweight threads are introduced into the language. In addition, monitors are introduced as a high-level tool for control-flow based synchronization and mutual-exclusion. The main contributions of this thesis are two-fold: it extends the existing semantics of monitors introduce by~\cite{Hoare74} to handle monitors in groups and also details the engineering effort needed to introduce these features as core language features. Indeed, these features are added with respect to expectations of C programmers, and integrate with the \CFA type-system and other language features.
    8388\end{abstract}
    8489
    … …  
    9095\section{Introduction}
    9196% ======================================================================
    92 
    93 This paper provides a minimal concurrency \textbf{api} that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of concurrency. Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. The high-level approach and its minimal \textbf{api} are tested in a dialect of C, called \CFA. Furthermore, the proposed \textbf{api} doubles as an early definition of the \CFA language and library. This paper also provides an implementation of the concurrency library for \CFA as well as all the required language features added to the source-to-source translator.
     97This thesis provides a minimal concurrency \textbf{api} that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of concurrency. Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. The high-level approach and its minimal \textbf{api} are tested in a dialect of C, called \CFA. Furthermore, the proposed \textbf{api} doubles as an early definition of the \CFA language and library. This thesis also provides an implementation of the concurrency library for \CFA as well as all the required language features added to the source-to-source translator.
    9498
    9599There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency and which parallelism tools are available to the programmer. While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}. Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization.
    96100
    97 In the context of this paper, a \textbf{thread} is a fundamental unit of execution that runs a sequence of code, generally on a program stack. Having multiple simultaneous threads gives rise to concurrency and generally requires some kind of locking mechanism to ensure proper execution. Correspondingly, \textbf{concurrency} is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced. Accordingly, \textbf{locking} (and by extension locks) are defined as a mechanism that prevents the progress of certain threads in order to avoid problems due to concurrency. Finally, in this paper \textbf{parallelism} is distinct from concurrency and is defined as running multiple threads simultaneously. More precisely, parallelism implies \emph{actual} simultaneous execution as opposed to concurrency which only requires \emph{apparent} simultaneous execution. As such, parallelism is only observable in the differences in performance or, more generally, differences in timing.
     101In the context of this thesis, a \textbf{thread} is a fundamental unit of execution that runs a sequence of code, generally on a program stack. Having multiple simultaneous threads gives rise to concurrency and generally requires some kind of locking mechanism to ensure proper execution. Correspondingly, \textbf{concurrency} is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced. Accordingly, \textbf{locking} (and by extension locks) are defined as a mechanism that prevents the progress of certain threads in order to avoid problems due to concurrency. Finally, in this thesis \textbf{parallelism} is distinct from concurrency and is defined as running multiple threads simultaneously. More precisely, parallelism implies \emph{actual} simultaneous execution as opposed to concurrency which only requires \emph{apparent} simultaneous execution. As such, parallelism is only observable in the differences in performance or, more generally, differences in timing.
    98102
    99103% ======================================================================
    … …  
    109113
    110114% ======================================================================
    111 \subsection{References}
     115\section{References}
    112116
    113117Like \CC, \CFA introduces rebind-able references providing multiple dereferencing as an alternative to pointers. In 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:
    … …  
    128132
    129133% ======================================================================
    130 \subsection{Overloading}
     134\section{Overloading}
    131135
    132136Another important feature of \CFA is function overloading as in Java and \CC, where routines with the same name are selected based on the number and type of the arguments. As well, \CFA uses the return type as part of the selection criteria, as in Ada~\cite{Ada}. For routines with multiple parameters and returns, the selection is complex.
    … …  
    149153
    150154% ======================================================================
    151 \subsection{Operators}
     155\section{Operators}
    152156Overloading also extends to operators. 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.:
    153157\begin{cfacode}
    … …  
    169173
    170174% ======================================================================
    171 \subsection{Constructors/Destructors}
     175\section{Constructors/Destructors}
    172176Object lifetime is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object lifetime as a means of synchronization and/or mutual exclusion. Since \CFA relies heavily on the lifetime of objects, constructors and destructors is a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors:
    173177\begin{cfacode}
    … …  
    204208
    205209% ======================================================================
    206 \subsection{Parametric Polymorphism}
     210\section{Parametric Polymorphism}
    207211\label{s:ParametricPolymorphism}
    208212Routines in \CFA can also be reused for multiple types. This capability is done using the \code{forall} clauses, which allow separately compiled routines to support generic usage over multiple types. For example, the following sum function works for any type that supports construction from 0 and addition:
    … …  
    237241
    238242% ======================================================================
    239 \subsection{with Clause/Statement}
     243\section{with Clause/Statement}
    240244Since \CFA lacks the concept of a receiver, certain functions end up needing to repeat variable names often. To remove this inconvenience, \CFA provides the \code{with} statement, which opens an aggregate scope making its fields directly accessible (like Pascal).
    241245\begin{cfacode}
    … …  
    282286
    283287\section{\protect\CFA's Thread Building Blocks}
    284 One 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. As such, library support for threading is far from widespread. At the time of writing the paper, neither \texttt{gcc} nor \texttt{clang} support ``threads.h'' in their respective standard libraries.}. On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write efficient concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.
     288One 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. As such, library support for threading is far from widespread. At the time of writing the thesis, neither \texttt{gcc} nor \texttt{clang} support ``threads.h'' in their respective standard libraries.}. On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write efficient concurrent programs to take advantage of parallelism. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.
    285289
    286290\section{Coroutines: A Stepping Stone}\label{coroutine}
    … …  
    660664\end{cfacode}
    661665
    662 In this example, threads of type \code{foo} start execution in the \code{void main(foo &)} routine, which prints \code{"Hello World!".} While this paper encourages this approach to enforce strongly typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity. With the static semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously.
     666In this example, threads of type \code{foo} start execution in the \code{void main(foo &)} routine, which prints \code{"Hello World!".} While this thesis encourages this approach to enforce strongly typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity. With the static semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously.
    663667\begin{cfacode}
    664668typedef void (*voidFunc)(int);
    … …  
    995999% ======================================================================
    9961000% ======================================================================
    997 In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronization. With monitors, this capability is generally achieved with internal or external scheduling as in~\cite{Hoare74}. 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). Since internal scheduling within a single monitor is mostly a solved problem, this paper concentrates on extending internal scheduling to multiple monitors. Indeed, 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.
     1001In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronization. With monitors, this capability is generally achieved with internal or external scheduling as in~\cite{Hoare74}. 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). Since internal scheduling within a single monitor is mostly a solved problem, this thesis concentrates on extending internal scheduling to multiple monitors. Indeed, 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.
    9981002
    9991003First, here is a simple example of internal scheduling:
    … …  
    17961800A \textbf{cfacluster} is a group of \textbf{kthread} executed in isolation. \textbf{uthread} are scheduled on the \textbf{kthread} of a given \textbf{cfacluster}, allowing organization between \textbf{uthread} and \textbf{kthread}. It is important that \textbf{kthread} belonging to a same \textbf{cfacluster} have homogeneous settings, otherwise migrating a \textbf{uthread} from one \textbf{kthread} to the other can cause issues. A \textbf{cfacluster} also offers a pluggable scheduler that can optimize the workload generated by the \textbf{uthread}.
    17971801
    1798 \textbf{cfacluster} have not been fully implemented in the context of this paper. Currently \CFA only supports one \textbf{cfacluster}, the initial one.
     1802\textbf{cfacluster} have not been fully implemented in the context of this thesis. Currently \CFA only supports one \textbf{cfacluster}, the initial one.
    17991803
    18001804\subsection{Future Work: Machine Setup}\label{machine}
    1801 While this was not done in the context of this paper, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups. For example, a system using \textbf{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certain CPU cores. OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
     1805While this was not done in the context of this thesis, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heterogeneous setups. For example, a system using \textbf{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certain CPU cores. OS support for CPU affinity is now common~\cite{affinityLinux, affinityWindows, affinityFreebsd, affinityNetbsd, affinityMacosx}, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
    18021806
    18031807\subsection{Paradigms}\label{cfaparadigms}
    … …  
    18111815The main memory concern for concurrency is queues. All blocking operations are made by parking threads onto queues and all queues are designed with intrusive nodes, where each node has pre-allocated link fields for chaining, to avoid the need for memory allocation. Since several concurrency operations can use an unbound amount of memory (depending on \textbf{bulk-acq}), statically defining information in the intrusive fields of threads is insufficient.The only way to use a variable amount of memory without requiring memory allocation is to pre-allocate large buffers of memory eagerly and store the information in these buffers. Conveniently, the call stack fits that description and is easy to use, which is why it is used heavily in the implementation of internal scheduling, particularly variable-length arrays. Since stack allocation is based on scopes, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable-length array. The threads and the condition both have a fixed amount of memory, while \code{mutex} routines and blocking calls allow for an unbound amount, within the stack size.
    18121816
    1813 Note that since the major contributions of this paper are extending monitor semantics to \textbf{bulk-acq} and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
     1817Note that since the major contributions of this thesis are extending monitor semantics to \textbf{bulk-acq} and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
    18141818
    18151819% ======================================================================
    … …  
    26112615
    26122616\section{Conclusion}
    2613 This paper has achieved a minimal concurrency \textbf{api} that is simple, efficient and usable as the basis for higher-level features. The approach presented is based on a lightweight thread-system for parallelism, which sits on top of clusters of processors. This M:N model is judged to be both more efficient and allow more flexibility for users. Furthermore, this document introduces monitors as the main concurrency tool for users. This paper also offers a novel approach allowing multiple monitors to be accessed simultaneously without running into the Nested Monitor Problem~\cite{Lister77}. It also offers a full implementation of the concurrency runtime written entirely in \CFA, effectively the largest \CFA code base to date.
     2617This thesis has achieved a minimal concurrency \textbf{api} that is simple, efficient and usable as the basis for higher-level features. The approach presented is based on a lightweight thread-system for parallelism, which sits on top of clusters of processors. This M:N model is judged to be both more efficient and allow more flexibility for users. Furthermore, this document introduces monitors as the main concurrency tool for users. This thesis also offers a novel approach allowing multiple monitors to be accessed simultaneously without running into the Nested Monitor Problem~\cite{Lister77}. It also offers a full implementation of the concurrency runtime written entirely in \CFA, effectively the largest \CFA code base to date.
    26142618
    26152619
    … …  
    26212625
    26222626\subsection{Performance} \label{futur:perf}
    2623 This paper presents a first implementation of the \CFA concurrency runtime. Therefore, there is still significant work to improve performance. Many of the data structures and algorithms may change in the future to more efficient versions. For example, the number of monitors in a single \textbf{bulk-acq} is only bound by the stack size, this is probably unnecessarily generous. It may be possible that limiting the number helps increase performance. However, it is not obvious that the benefit would be significant.
     2627This thesis presents a first implementation of the \CFA concurrency runtime. Therefore, there is still significant work to improve performance. Many of the data structures and algorithms may change in the future to more efficient versions. For example, the number of monitors in a single \textbf{bulk-acq} is only bound by the stack size, this is probably unnecessarily generous. It may be possible that limiting the number helps increase performance. However, it is not obvious that the benefit would be significant.
    26242628
    26252629\subsection{Flexible Scheduling} \label{futur:sched}
    … …  
    27252729\section{Acknowledgements}
    27262730
    2727 Thanks to Aaron Moss, Rob Schluntz and Andrew Beach for their work on the \CFA project as well as all the discussions which helped concretize the ideas in this paper.
    2728 Partial funding was supplied by the Natural Sciences and Engineering Research Council of Canada and a corporate partnership with Huawei Ltd.
     2731I would like to thank my supervisor, Professor Peter Buhr, for his guidance through my degree as well as the editing of this document.
     2732
     2733I would like to thank Professors Martin Karsten and Gregor Richards, for reading my thesis and providing helpful feedback.
     2734
     2735Thanks to Aaron Moss, Rob Schluntz and Andrew Beach for their work on the \CFA project as well as all the discussions which have helped me concretize the ideas in this thesis.
     2736
     2737Finally, I acknowledge that this has been possible thanks to the financial help offered by the David R. Cheriton School of Computer Science and the corporate partnership with Huawei Ltd.
    27292738
    27302739
    … …  
    27352744
    27362745\end{document}
    2737 
    2738 % Local Variables: %
    2739 % tab-width: 4 %
    2740 % fill-column: 120 %
    2741 % compile-command: "make" %
    2742 % End: %

  • doc/papers/general/.gitignore

    r281806b6 r4ab3d68e  
    11# generated by latex
    2 build/*
     2*.aux
     3*.bbl
     4*.blg
     5*.brf
     6*.dvi
     7*.idx
     8*.ilg
     9*.ind
     10*.log
     11*.out
    312*.pdf
    413*.ps
     14*.toc
     15*.lof
     16*.lot
     17*.synctex.gz
     18comment.cut
     19timing.tex

  • doc/papers/general/Makefile

    r281806b6 r4ab3d68e  
    22
    33Build = build
    4 Figures = figures
    54Macros = ../../LaTeXmacros
    65TeXLIB = .:${Macros}:${Build}:../../bibliography:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     6LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -interaction=nonstopmode
    87BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    98
    109MAKEFLAGS = --no-print-directory --silent #
    11 VPATH = ${Figures} evaluation
    1210
    1311## Define the text source files.
    … …  
    3634# Directives #
    3735
    38 .PHONY : all clean                                      # not file names
     36.PHONY : all clean                                                                              # not file names
    3937
    4038all : ${DOCUMENT}
    … …  
    5250
    5351${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    54                 ${Macros}/common.tex ${Macros}/indexstyle ../../bibliography/pl.bib
    55         # Must have *.aux file containing citations for bibtex
    56         if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    57         -${BibTeX} ${Build}/${basename $@}
    58         # Some citations reference others so run again to resolve these citations
     52                        ${Macros}/common.tex ${Macros}/indexstyle ../../bibliography/cfa.bib
     53        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi # Must have *.aux file containing citations for bibtex
     54        -${BibTeX} ${Build}/${basename $@}                                      # Some citations reference others so run again to resolve these citations
    5955        ${LaTeX} ${basename $@}.tex
    6056        -${BibTeX} ${Build}/${basename $@}
    61         # Run again to finish citations
    62         ${LaTeX} ${basename $@}.tex
     57        ${LaTeX} ${basename $@}.tex                                                     # Finish citations
    6358
    6459## Define the default recipes.
     60
     61vpath %.tex ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
     62vpath %.fig ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    6563
    6664${Build}:
    6765        mkdir -p ${Build}
    6866
    69 ${GRAPHS} : timing.gp timing.dat
    70         gnuplot -e Build="'${Build}/'" evaluation/timing.gp
     67${GRAPHS} : evaluation/timing.gp evaluation/timing.dat
     68        gnuplot evaluation/timing.gp
    7169
    72 %.tex : %.fig
     70%.tex : figures/%.fig
    7371        fig2dev -L eepic $< > ${Build}/$@
    7472
    75 %.ps : %.fig
     73%.ps : figures/%.fig
    7674        fig2dev -L ps $< > ${Build}/$@
    7775
    78 %.pstex : %.fig
     76%.pstex : figures/%.fig
    7977        fig2dev -L pstex $< > ${Build}/$@
    8078        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    8179
    8280# Local Variables: #
     81# tab-width : 4 #
    8382# compile-command: "make" #
    8483# End: #

  • doc/papers/general/Paper.tex

    r281806b6 r4ab3d68e  
    10951095
    10961096\bibliographystyle{plain}
    1097 \bibliography{pl}
     1097\bibliography{cfa}
    10981098
    10991099

  • doc/papers/general/evaluation/timing.gp

    r281806b6 r4ab3d68e  
    22# set output "timing.pdf"
    33set terminal pslatex size 6.25,2.125 color solid
    4 set output Build."timing.tex"
     4set output "timing.tex"
    55
    66set pointsize 2.0

  • doc/proposals/tuples/tuples.tex

    r281806b6 r4ab3d68e  
    322322\addcontentsline{toc}{section}{\refname}
    323323\bibliographystyle{plain}
    324 \bibliography{pl}
     324\bibliography{cfa}
    325325
    326326%\addcontentsline{toc}{section}{\indexname} % add index name to table of contents

  • doc/refrat/.gitignore

    r281806b6 r4ab3d68e  
    11# generated by latex
    2 build/*
     2*.aux
     3*.bbl
     4*.blg
     5*.brf
     6*.dvi
     7*.idx
     8*.ilg
     9*.ind
     10*.log
     11*.out
    312*.pdf
    413*.ps
     14*.toc

  • doc/refrat/Makefile

    r281806b6 r4ab3d68e  
    1 ## Define the configuration variables.
     1## Define the appropriate configuration variables.
    22
    3 Build = build
    4 Figures = figures
    5 Macros = ../LaTeXmacros
    6 TeXLIB = .:${Macros}:${Build}:../bibliography:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     3TeXLIB = .:../LaTeXmacros:../LaTeXmacros/listings:../LaTeXmacros/enumitem:../bibliography/:
     4LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
    85BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    9 
    10 MAKEFLAGS = --no-print-directory --silent #
    11 VPATH = ${Figures}
    126
    137## Define the text source files.
    … …  
    3731# Directives #
    3832
    39 .PHONY : all clean                                      # not file names
    40 
    4133all : ${DOCUMENT}
    4234
    4335clean :
    44         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     36        rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
     37                ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
    4538
    4639# File Dependencies #
    … …  
    5043
    5144${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    52         dvips ${Build}/$< -o $@
     45        dvips $< -o $@
    5346
    54 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    55                 ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib
     47${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
     48                ../LaTeXmacros/common.tex ../LaTeXmacros/lstlang.sty ../LaTeXmacros/indexstyle ../bibliography/cfa.bib
    5649        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    57         if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
     50        if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
    5851        # Must have *.aux file containing citations for bibtex
    5952        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    60         -${BibTeX} ${Build}/${basename $@}
    61         # Some citations reference others so run again to resolve these citations
     53        -${BibTeX} ${basename $@}
     54        # Some citations reference others so run steps again to resolve these citations
    6255        ${LaTeX} ${basename $@}.tex
    63         -${BibTeX} ${Build}/${basename $@}
     56        -${BibTeX} ${basename $@}
    6457        # Make index from *.aux entries and input index at end of document
    65         makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx
    66         # Run again to finish citations
     58        makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx
    6759        ${LaTeX} ${basename $@}.tex
    6860        # Run again to get index title into table of contents
    … …  
    7466## Define the default recipes.
    7567
    76 ${Build}:
    77         mkdir -p ${Build}
    78 
    7968%.tex : %.fig
    80         fig2dev -L eepic $< > ${Build}/$@
     69        fig2dev -L eepic $< > $@
    8170
    8271%.ps : %.fig
    83         fig2dev -L ps $< > ${Build}/$@
     72        fig2dev -L ps $< > $@
    8473
    8574%.pstex : %.fig
    86         fig2dev -L pstex $< > ${Build}/$@
    87         fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
     75        fig2dev -L pstex $< > $@
     76        fig2dev -L pstex_t -p $@ $< > $@_t
    8877
    8978# Local Variables: #

  • doc/refrat/refrat.tex

    r281806b6 r4ab3d68e  
    1111%% Created On       : Wed Apr  6 14:52:25 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Wed Jan 31 17:30:23 2018
    14 %% Update Count     : 108
     13%% Last Modified On : Tue Aug 15 18:46:31 2017
     14%% Update Count     : 106
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    141141The manual deliberately imitates the ordering of the \Celeven standard (although the section numbering differs).
    142142Unfortunately, this means the manual contains more ``forward references'' than usual, making it harder to follow if the reader does not have a copy of the \Celeven standard.
    143 For a simple introduction to \CFA, see~\cite{Cforall}.
     143For a simple introduction to \CFA, see the companion document ``An Overview of \CFA''
     144\cite{Ditchfield96:Overview}.
    144145
    145146\begin{rationale}
    … …  
    595596\begin{rationale}
    596597Since each subsection describes the interpretations of an expression in terms of the interpretations of its subexpressions, this chapter can be taken as describing an overload resolution algorithm that uses one bottom-up pass over an expression tree.
    597 Such an algorithm was first described (for Ada) by Baker~\cite{Baker82}.
     598Such an algorithm was first described (for Ada) by Baker~\cite{Bak:overload}.
    598599It is extended here to handle polymorphic functions and arithmetic conversions.
    599600The overload resolution rules and the predefined functions have been chosen so that, in programs that do not introduce overloaded declarations, expressions will have the same meaning in C and in \CFA.
    … …  
    37743775
    37753776\bibliographystyle{plain}
    3776 \bibliography{pl}
     3777\bibliography{cfa}
    37773778
    37783779

  • doc/user/.gitignore

    r281806b6 r4ab3d68e  
    11# generated by latex
    2 build/*
     2*.aux
     3*.bbl
     4*.blg
     5*.brf
     6*.dvi
     7*.idx
     8*.ilg
     9*.ind
     10*.log
     11*.out
    312*.pdf
    413*.ps
     14*.toc

  • doc/user/Makefile

    r281806b6 r4ab3d68e  
    1 ## Define the configuration variables.
     1## Define the appropriate configuration variables.
    22
    3 Build = build
    4 Figures = figures
    5 Macros = ../LaTeXmacros
    6 TeXLIB = .:${Macros}:${Build}:../bibliography:
    7 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     3TeXLIB = .:../LaTeXmacros:../bibliography/:
     4LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
    85BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    9 
    10 MAKEFLAGS = --no-print-directory --silent #
    11 VPATH = ${Figures}
    126
    137## Define the text source files.
    … …  
    4135# Directives #
    4236
    43 .PHONY : all clean                                      # not file names
    44 
    4537all : ${DOCUMENT}
    4638
    4739clean :
    48         @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
     40        rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
     41                ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
    4942
    5043# File Dependencies #
    … …  
    5447
    5548${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    56         dvips ${Build}/$< -o $@
     49        dvips $< -o $@
    5750
    58 ${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    59                 ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib
     51${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
     52                ../LaTeXmacros/common.tex ../LaTeXmacros/lstlang.sty ../LaTeXmacros/indexstyle ../bibliography/cfa.bib
    6053        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    61         if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
     54        if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
    6255        # Must have *.aux file containing citations for bibtex
    6356        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    64         -${BibTeX} ${Build}/${basename $@}
    65         # Some citations reference others so run again to resolve these citations
     57        -${BibTeX} ${basename $@}
     58        # Some citations reference others so run steps again to resolve these citations
    6659        ${LaTeX} ${basename $@}.tex
    67         -${BibTeX} ${Build}/${basename $@}
     60        -${BibTeX} ${basename $@}
    6861        # Make index from *.aux entries and input index at end of document
    69         makeindex -s ${Macros}/indexstyle ${Build}/${basename $@}.idx
    70         # Run again to finish citations
     62        makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx
    7163        ${LaTeX} ${basename $@}.tex
    7264        # Run again to get index title into table of contents
    7365        ${LaTeX} ${basename $@}.tex
    7466
     67predefined :
     68        sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf
     69
    7570## Define the default recipes.
    7671
    77 ${Build}:
    78         mkdir -p ${Build}
    79 
    8072%.tex : %.fig
    81         fig2dev -L eepic $< > ${Build}/$@
     73        fig2dev -L eepic $< > $@
    8274
    8375%.ps : %.fig
    84         fig2dev -L ps $< > ${Build}/$@
     76        fig2dev -L ps $< > $@
    8577
    8678%.pstex : %.fig
    87         fig2dev -L pstex $< > ${Build}/$@
    88         fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
     79        fig2dev -L pstex $< > $@
     80        fig2dev -L pstex_t -p $@ $< > $@_t
    8981
    9082# Local Variables: #

  • doc/user/user.tex

    r281806b6 r4ab3d68e  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Wed Jan 31 07:59:24 2018
    14 %% Update Count     : 3146
     13%% Last Modified On : Mon Nov 27 18:09:59 2017
     14%% Update Count     : 3143
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    4040\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    4141\usepackage{breakurl}
     42\renewcommand{\UrlFont}{\small\sf}
    4243
    4344\usepackage[pagewise]{lineno}
    … …  
    66606661
    66616662\bibliographystyle{plain}
    6662 \bibliography{pl}
     6663\bibliography{cfa}
    66636664
    66646665
Note: See TracChangeset for help on using the changeset viewer.