Changeset 5ff188f for doc/papers


Ignore:
Timestamp:
Jan 31, 2018, 5:49:36 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
281806b
Parents:
633a642
Message:

further changes to document Makefiles

Location:
doc/papers
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/OOPSLA17/.gitignore

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

  • doc/papers/OOPSLA17/Makefile

    r633a642 r5ff188f  
    1 ## Define the appropriate configuration variables.
     1## Define the configuration variables.
    22
    3 TeXLIB = .:../LaTeXmacros:../LaTeXmacros/listings:../LaTeXmacros/enumitem:../bibliography/:
    4 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error
     3Build = build
     4Figures = figures
     5Macros = ../../LaTeXmacros
     6TeXLIB = .:${Macros}:${Build}:../../bibliography:
     7LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    58BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
     9
     10MAKEFLAGS = --no-print-directory --silent #
     11VPATH = ${Figures} evaluation
    612
    713## Define the text source files.
    … …  
    3339
    3440clean :
    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}
     41        @rm -frv ${DOCUMENT} ${basename ${DOCUMENT}}.ps ${Build}
    3742
    3843# File Dependencies #
    … …  
    4247
    4348${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    44         dvips $< -o $@
     49        dvips ${Build}/$< -o $@
    4550
    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
     51${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../../bibliography/pl.bib
    5152        # Must have *.aux file containing citations for bibtex
    5253        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    53         -${BibTeX} ${basename $@}
    54         # Some citations reference others so run steps again to resolve these citations
     54        -${BibTeX} ${Build}/${basename $@}
     55        # Some citations reference others so run again to resolve these citations
    5556        ${LaTeX} ${basename $@}.tex
    56         -${BibTeX} ${basename $@}
    57         # Make index from *.aux entries and input index at end of document
    58         makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx
     57        -${BibTeX} ${Build}/${basename $@}
     58        # Run again to finish citations
    5959        ${LaTeX} ${basename $@}.tex
    60         # Run again to get index title into table of contents
    61         ${LaTeX} ${basename $@}.tex
    62 
    63 predefined :
    64         sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf
    6560
    6661## Define the default recipes.
    6762
    68 ${GRAPHS} : evaluation/timing.gp evaluation/timing.dat
    69         gnuplot evaluation/timing.gp
     63${Build}:
     64        mkdir -p ${Build}
     65
     66${GRAPHS} : timing.gp timing.dat
     67        gnuplot -e Build="'${Build}/'" evaluation/timing.gp
    7068
    7169%.tex : %.fig
    72         fig2dev -L eepic $< > $@
     70        fig2dev -L eepic $< > ${Build}/$@
    7371
    7472%.ps : %.fig
    75         fig2dev -L ps $< > $@
     73        fig2dev -L ps $< > ${Build}/$@
    7674
    7775%.pstex : %.fig
    78         fig2dev -L pstex $< > $@
    79         fig2dev -L pstex_t -p $@ $< > $@_t
     76        fig2dev -L pstex $< > ${Build}/$@
     77        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    8078
    8179# Local Variables: #

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

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

  • doc/papers/OOPSLA17/generic_types.tex

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

  • doc/papers/concurrency/.gitignore

    r633a642 r5ff188f  
     1# generated by latex
    12build/*
    23*.pdf

  • doc/papers/concurrency/Makefile

    r633a642 r5ff188f  
    22
    33Build = build
     4Figures = figures
    45Macros = ../../LaTeXmacros
    5 TeXLIB = .:style:annex:${Macros}:${Build}:/usr/local/bibliographies:
    6 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -interaction=nonstopmode
     6TeXLIB = .:style:annex:${Macros}:${Build}:../../bibliography:
     7LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    78BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    89
    910MAKEFLAGS = --no-print-directory --silent #
     11VPATH = ${Figures}
    1012
    1113## Define the text source files.
    … …  
    4143# Directives #
    4244
    43 .PHONY : all clean                                                                              # not file names
     45.PHONY : all clean                                      # not file names
    4446
    4547all : ${DOCUMENT}
    … …  
    5759
    5860${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    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
     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
    6266        ${LaTeX} ${basename $@}.tex
    6367        -${BibTeX} ${Build}/${basename $@}
    64         ${LaTeX} ${basename $@}.tex                                                     # Finish citations
     68        # Run again to finish citations
     69        ${LaTeX} ${basename $@}.tex
    6570
    6671## Define the default recipes.
    67 
    68 vpath %.tex ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    69 vpath %.fig ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    7072
    7173${Build}:
    7274        mkdir -p ${Build}
    7375
    74 %.tex : figures/%.fig
     76%.tex : %.fig
    7577        fig2dev -L eepic $< > ${Build}/$@
    7678
    77 %.ps : figures/%.fig
     79%.ps : %.fig
    7880        fig2dev -L ps $< > ${Build}/$@
    7981
    80 %.pstex : figures/%.fig
     82%.pstex : %.fig
    8183        fig2dev -L pstex $< > ${Build}/$@
    8284        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    8385
    8486# Local Variables: #
    85 # tab-width : 4 #
    8687# compile-command: "make" #
    8788# End: #

  • doc/papers/concurrency/Paper.tex

    r633a642 r5ff188f  
    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-^
     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-^
    97% math escape $...$ (dollar symbol)
    108
    … …  
    2018\usepackage{epic,eepic}
    2119\usepackage{upquote}                                            % switch curled `'" to straight
    22 \usepackage{dirtytalk}
    2320\usepackage{calc}
    2421\usepackage{xspace}
    … …  
    4643\urlstyle{rm}
    4744
    48 \usepackage{tikz}
    49 \def\checkmark{\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle;}
    50 
    5145\setlength{\topmargin}{-0.45in}                         % move running title into header
    5246\setlength{\headsep}{0.25in}
    … …  
    7872
    7973\title{Concurrency in \CFA}
    80 \author{Thierry Delisle, Waterloo, Ontario, Canada, 2018}
     74\author{Thierry Delisle and Peter A. Buhr, Waterloo, Ontario, Canada}
    8175
    8276
    … …  
    8579
    8680\begin{abstract}
    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.
     81\CFA is a modern, \emph{non-object-oriented} extension of the C programming language.
     82This 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.
    8883\end{abstract}
    8984
    … …  
    9590\section{Introduction}
    9691% ======================================================================
    97 This 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.
     92
     93This 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.
    9894
    9995There 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.
    10096
    101 In 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.
     97In 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.
    10298
    10399% ======================================================================
    … …  
    113109
    114110% ======================================================================
    115 \section{References}
     111\subsection{References}
    116112
    117113Like \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:
    … …  
    132128
    133129% ======================================================================
    134 \section{Overloading}
     130\subsection{Overloading}
    135131
    136132Another 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.
    … …  
    153149
    154150% ======================================================================
    155 \section{Operators}
     151\subsection{Operators}
    156152Overloading 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.:
    157153\begin{cfacode}
    … …  
    173169
    174170% ======================================================================
    175 \section{Constructors/Destructors}
     171\subsection{Constructors/Destructors}
    176172Object 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:
    177173\begin{cfacode}
    … …  
    208204
    209205% ======================================================================
    210 \section{Parametric Polymorphism}
     206\subsection{Parametric Polymorphism}
    211207\label{s:ParametricPolymorphism}
    212208Routines 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:
    … …  
    241237
    242238% ======================================================================
    243 \section{with Clause/Statement}
     239\subsection{with Clause/Statement}
    244240Since \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).
    245241\begin{cfacode}
    … …  
    286282
    287283\section{\protect\CFA's Thread Building Blocks}
    288 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 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.
     284One 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.
    289285
    290286\section{Coroutines: A Stepping Stone}\label{coroutine}
    … …  
    664660\end{cfacode}
    665661
    666 In 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.
     662In 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.
    667663\begin{cfacode}
    668664typedef void (*voidFunc)(int);
    … …  
    999995% ======================================================================
    1000996% ======================================================================
    1001 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 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.
     997In 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.
    1002998
    1003999First, here is a simple example of internal scheduling:
    … …  
    18001796A \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}.
    18011797
    1802 \textbf{cfacluster} have not been fully implemented in the context of this thesis. Currently \CFA only supports one \textbf{cfacluster}, the initial one.
     1798\textbf{cfacluster} have not been fully implemented in the context of this paper. Currently \CFA only supports one \textbf{cfacluster}, the initial one.
    18031799
    18041800\subsection{Future Work: Machine Setup}\label{machine}
    1805 While 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.
     1801While 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.
    18061802
    18071803\subsection{Paradigms}\label{cfaparadigms}
    … …  
    18151811The 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.
    18161812
    1817 Note 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.
     1813Note 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.
    18181814
    18191815% ======================================================================
    … …  
    26152611
    26162612\section{Conclusion}
    2617 This 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.
     2613This 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.
    26182614
    26192615
    … …  
    26252621
    26262622\subsection{Performance} \label{futur:perf}
    2627 This 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.
     2623This 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.
    26282624
    26292625\subsection{Flexible Scheduling} \label{futur:sched}
    … …  
    27292725\section{Acknowledgements}
    27302726
    2731 I would like to thank my supervisor, Professor Peter Buhr, for his guidance through my degree as well as the editing of this document.
    2732 
    2733 I would like to thank Professors Martin Karsten and Gregor Richards, for reading my thesis and providing helpful feedback.
    2734 
    2735 Thanks 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 
    2737 Finally, 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.
     2727Thanks 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.
     2728Partial funding was supplied by the Natural Sciences and Engineering Research Council of Canada and a corporate partnership with Huawei Ltd.
    27382729
    27392730
    … …  
    27442735
    27452736\end{document}
     2737
     2738% Local Variables: %
     2739% tab-width: 4 %
     2740% fill-column: 120 %
     2741% compile-command: "make" %
     2742% End: %

  • doc/papers/general/.gitignore

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

  • doc/papers/general/Makefile

    r633a642 r5ff188f  
    22
    33Build = build
     4Figures = figures
    45Macros = ../../LaTeXmacros
    56TeXLIB = .:${Macros}:${Build}:../../bibliography:
    6 LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -interaction=nonstopmode
     7LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    78BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    89
    910MAKEFLAGS = --no-print-directory --silent #
     11VPATH = ${Figures} evaluation
    1012
    1113## Define the text source files.
    … …  
    3436# Directives #
    3537
    36 .PHONY : all clean                                                                              # not file names
     38.PHONY : all clean                                      # not file names
    3739
    3840all : ${DOCUMENT}
    … …  
    5052
    5153${basename ${DOCUMENT}}.dvi : Makefile ${Build} ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    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
     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
    5559        ${LaTeX} ${basename $@}.tex
    5660        -${BibTeX} ${Build}/${basename $@}
    57         ${LaTeX} ${basename $@}.tex                                                     # Finish citations
     61        # Run again to finish citations
     62        ${LaTeX} ${basename $@}.tex
    5863
    5964## Define the default recipes.
    60 
    61 vpath %.tex ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    62 vpath %.fig ${subst .zzz,,${subst .zzz ,:,${SOURCES}}}  # add prefix for source
    6365
    6466${Build}:
    6567        mkdir -p ${Build}
    6668
    67 ${GRAPHS} : evaluation/timing.gp evaluation/timing.dat
    68         gnuplot evaluation/timing.gp
     69${GRAPHS} : timing.gp timing.dat
     70        gnuplot -e Build="'${Build}/'" evaluation/timing.gp
    6971
    70 %.tex : figures/%.fig
     72%.tex : %.fig
    7173        fig2dev -L eepic $< > ${Build}/$@
    7274
    73 %.ps : figures/%.fig
     75%.ps : %.fig
    7476        fig2dev -L ps $< > ${Build}/$@
    7577
    76 %.pstex : figures/%.fig
     78%.pstex : %.fig
    7779        fig2dev -L pstex $< > ${Build}/$@
    7880        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
    7981
    8082# Local Variables: #
    81 # tab-width : 4 #
    8283# compile-command: "make" #
    8384# End: #

  • doc/papers/general/Paper.tex

    r633a642 r5ff188f  
    10951095
    10961096\bibliographystyle{plain}
    1097 \bibliography{cfa}
     1097\bibliography{pl}
    10981098
    10991099

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

    r633a642 r5ff188f  
    22# set output "timing.pdf"
    33set terminal pslatex size 6.25,2.125 color solid
    4 set output "timing.tex"
     4set output Build."timing.tex"
    55
    66set pointsize 2.0
Note: See TracChangeset for help on using the changeset viewer.