Changeset 8f9cc50


Ignore:
Timestamp:
Nov 11, 2016, 1:31:34 PM (5 years ago)
Author:
Rob Schluntz <rschlunt@…>
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, resolv-new, with_gc
Children:
33a7b6d
Parents:
30b65d8 (diff), 668e971a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' into tuples

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/concurrency/concurrency.tex

    r30b65d8 r8f9cc50  
    673673% #       #     # #     # #     # ####### ####### ####### ####### ###  #####  #     #
    674674\section{Parallelism}
    675 Historically, computer performance was about processor speeds and instructions count. However, with heat dissipation being an ever growing challenge, parallelism has become the new source of greatest performance~\cite{Sutter05, Sutter05b}. In this decade, it is not longer reasonnable to create high-performance application without caring about parallelism. Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization. The lowest level approach of parallelism is to use \glspl{kthread}. However since these have significant costs and limitations \glspl{kthread} are now mostly used as an implementation tool rather than a user oriented one. There are several alternatives to solve these issues which all have strengths and weaknesses.
     675Historically, computer performance was about processor speeds and instructions count. However, with heat dissipation being a direct consequence of speed increase, parallelism has become the new source for increased performance~\cite{Sutter05, Sutter05b}. In this decade, it is not longer reasonnable to create high-performance application without caring about parallelism. Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization. The lowest level approach of parallelism is to use \glspl{kthread} in combination with semantics like \code{fork}, \code{join}, etc. However, since these have significant costs and limitations \glspl{kthread} are now mostly used as an implementation tool rather than a user oriented one. There are several alternatives to solve these issues that all have strengths and weaknesses. While there are many variations of the presented paradigms, most of these variations do not actually change the guarantees or the semantics, they simply move costs in order to achieve better performance for certain workloads.
    676676
    677677\subsection{User-level threads}
    678 A direct improvement on the \gls{kthread} approach is to use \glspl{uthread}. These threads offer most of the same features that the operating system already provide but can be used on a much larger scale. This is the most powerfull solution as it allows all the features of multi-threading while removing several of the more expensives costs of using kernel threads. The down side is that almost none of the low-level threading complexities are hidden, users still have to think about data races, deadlocks and synchronization issues. This can be somewhat alleviated by a concurrency toolkit with strong garantees but the parallelism toolkit offers very little to reduce complexity in itself.
    679 
    680 Examples of languages that support are Java~\cite{Java}, Haskell~\cite{Haskell} and \uC~\cite{uC++book}.
     678A direct improvement on the \gls{kthread} approach is to use \glspl{uthread}. These threads offer most of the same features that the operating system already provide but can be used on a much larger scale. This approach is the most powerfull solution as it allows all the features of multi-threading while removing several of the more expensives costs of using kernel threads. The down side is that almost none of the low-level threading problems are hidden, users still have to think about data races, deadlocks and synchronization issues. These issues can be somewhat alleviated by a concurrency toolkit with strong garantees but the parallelism toolkit offers very little to reduce complexity in itself.
     679
     680Examples of languages that support are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
     681
     682\subsection{Fibers : user-level threads without preemption}
     683In the middle of the flexibility versus complexity spectrum lay \glspl{fiber} which offer \glspl{uthread} without the complexity of preemption by using cooperative scheduling. On a single core machine this means users need not worry about concurrency. On multi-core machines, while concurrency is still a concern, it is only a problem for fibers across cores but not while on the same core. This extra guarantee plus the fact that creating and destroying fibers are implicit synchronizing points means preventing mutable shared ressources still leaves many control flow options. However, multi-core processors can still execute fibers in parallel. This means users either need to worry about mutual exclusion, deadlocks and race conditions, or limit themselves to subset of concurrency primitives, raising the complexity in both cases. In this aspect, fibers can be seen as a more powerfull alternative to \glspl{job}.
     684
     685An example of a language that uses fibers is Go~\cite{Go}
    681686
    682687\subsection{Jobs and thread pools}
    683 The approach on the opposite end of the spectrum is to base parallelism on \glspl{job}. Indeed, \glspl{job} offer limited flexibility but at the benefit of a simpler user interface. In \gls{job} based systems users express parallelism as units of work and the dependency graph (either explicit or implicit) that tie them together. This means users need not to worry about concurrency but significantly limits the interaction that can occur between different jobs. Indeed, any \gls{job} that blocks also blocks the underlying \gls{kthread}, this effectively mean the CPU utilization, and therefore throughput, will suffer noticeably.
    684 The golden standard of this implementation is Intel's TBB library~\cite{TBB}.
    685 
    686 \subsection{Fibers : user-level threads without preemption}
    687 Finally, in the middle of the flexibility versus complexity spectrum lay \glspl{fiber} which offer \glspl{uthread} without the complexity of preemption. This means users don't have to worry about other \glspl{fiber} suddenly executing between two instructions which signficantly reduces complexity. However, any call to IO or other concurrency primitives can lead to context switches. Furthermore, users can also block \glspl{fiber} in the middle of their execution without blocking a full processor core. This means users still have to worry about mutual exclusion, deadlocks and race conditions in their code, raising the complexity significantly.
    688 An example of a language that uses fibers is Go~\cite{Go}
     688The approach on the opposite end of the spectrum is to base parallelism on \glspl{pool}. Indeed, \glspl{pool} offer limited flexibility but at the benefit of a simpler user interface. In \gls{pool} based systems, users express parallelism as units of work and the dependency graph (either explicit or implicit) that tie them together. This approach means users need not worry about concurrency but significantly limits the interaction that can occur between different jobs. Indeed, any \gls{job} that blocks also blocks the underlying worker, which effectively means the CPU utilization, and therefore throughput, suffers noticeably. It can be argued that a solution to this problem is to use more workers than available cores. However, unless the number of jobs and the number of workers are comparable, having a significant amount of blocked jobs will always results in idles cores.
     689
     690The gold standard of this implementation is Intel's TBB library~\cite{TBB}.
    689691
    690692\subsection{Paradigm performance}
    691 While the choice between the three paradigms listed above may have significant performance implication, it is difficult to pin the performance implications of chosing a model at the language level. Indeed, in many situations one of these paradigms will show better performance but it all strongly depends on the usage. Having mostly indepent units of work to execute almost guarantess that the \gls{job} based system will have the best performance. However, add interactions between jobs and the processor utilisation might suffer. User-level threads may allow maximum ressource utilisation but context switches will be more expansive and it is also harder for users to get perfect tunning. As with every example, fibers sit somewhat in the middle of the spectrum. Furthermore, if the units of uninterrupted work are large enough the paradigm choice will be largely amorticised by the actual work done.
     693While the choice between the three paradigms listed above may have significant performance implication, it is difficult to pindown the performance implications of chosing a model at the language level. Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload. Having a large amount of mostly independent units of work to execute almost guarantess that the \gls{pool} based system has the best performance thanks to the lower memory overhead. However, interactions between jobs can easily exacerbate contention. User-level threads may allows fine grain context switching which may result in better resource utilisation but context switches will be more expansive and it is also harder for users to get perfect tunning. As with every example, fibers sit somewhat in the middle of the spectrum. Furthermore, if the units of uninterrupted work are large enough the paradigm choice will be largely amorticised by the actual work done.
    692694
    693695%  #####  #######    #          ####### ######  ######
     
    706708\multicolumn{1}{ c| }{} & Has a stack & Preemptive \\
    707709\hline
    708 \Glspl{job} & X & X \\
     710\Glspl{pool} & X & X \\
    709711\hline
    710712\Glspl{fiber} & \checkmark & X \\
     
    715717\end{center}
    716718
     719This table is missing several variations (for example jobs on \glspl{uthread} or \glspl{fiber}), but these variation affect mostly performance and do not effect the guarantees as the presented paradigm do.
     720
    717721As shown in section \ref{cfaparadigms} these different blocks being available in \CFA it is trivial to reproduce any of these paradigm.
    718722
     
    726730
    727731\subsection{Thread Interface}
    728 The basic building blocks of \CFA are \glspl{cfathread}. By default these are implemented as \glspl{uthread} and as such offer a flexible and lightweight threading interface (lightweight comparatievely to \glspl{kthread}). A thread can be declared using a struct declaration prefix with the \code{thread} as follows :
     732The basic building blocks of \CFA are \glspl{cfathread}. By default these are implemented as \glspl{uthread} and as such offer a flexible and lightweight threading interface (lightweight comparatievely to \glspl{kthread}). A thread can be declared using a struct declaration with prefix \code{thread} as follows :
    729733
    730734\begin{lstlisting}
     
    732736\end{lstlisting}
    733737
    734 Obviously, for this thread implementation to be usefull it must run some user code. Several other threading interfaces use some function pointer representation as the interface of threads (for example : \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, we consider that statically tying a \code{main} routine to a thread superseeds this approach. Since the \code{main} routine is definetely a special routine in \CFA, we can reuse the existing syntax for declaring routines with unordinary name, i.e. operator overloading. As such the \code{main} routine of a thread can be defined as such :
     738Obviously, for this thread implementation to be usefull it must run some user code. Several other threading interfaces use some function pointer representation as the interface of threads (for example : \Csharp~\cite{Csharp} and Scala~\cite{Scala}). However, this proposal considers that statically tying a \code{main} routine to a thread superseeds this approach. Since the \code{main} routine is definitely a special routine in \CFA, the existing syntax for declaring routines with unordinary name can be extended, i.e. operator overloading. As such the \code{main} routine of a thread can be defined as :
    735739\begin{lstlisting}
    736740        thread struct foo {};
     
    780784}
    781785\end{lstlisting}
    782 This semantic has several advantages over explicit semantics : typesafety is guaranteed, any thread will always be started and stopped exaclty once and users can't make any progamming errors. Furthermore it naturally follows the memory allocation semantics which means users don't need to learn multiple semantics.
     786This semantic has several advantages over explicit semantics : typesafety is guaranteed, a thread is always started and stopped exaclty once and users cannot make any progamming errors. Furthermore it naturally follows the memory allocation semantics, which means users do not need to learn multiple semantics.
    783787
    784788These semantics also naturally scale to multiple threads meaning basic synchronisation is very simple :
     
    803807
    804808                //Wait for the 10 threads to finish
     809        }
     810
     811        void bar() {
     812                MyThread* thrds = new MyThread[10];
     813                //Start 10 threads at the beginning of the scope
     814
     815                DoStuff();
     816
     817                //Wait for the 10 threads to finish
     818                delete MyThread;
    805819        }
    806820\end{lstlisting}
  • doc/proposals/concurrency/glossary.tex

    r30b65d8 r8f9cc50  
    5252}
    5353
     54\longnewglossaryentry{pool}
     55{name={thread-pool}}
     56{
     57Group of homogeneuous threads that loop executing units of works after another.
     58
     59\textit{Synonyms : }
     60}
     61
    5462\longnewglossaryentry{cfacluster}
    5563{name={cluster}}
  • doc/proposals/concurrency/version

    r30b65d8 r8f9cc50  
    1 0.5.146
     10.5.150
  • src/ResolvExpr/AlternativeFinder.cc

    r30b65d8 r8f9cc50  
    10041004                                        AssertionSet needAssertions, haveAssertions;
    10051005                                        Alternative newAlt( 0, third->env, first->cost + second->cost + third->cost );
    1006                                         Type* commonType;
     1006                                        Type* commonType = nullptr;
    10071007                                        if ( unify( second->expr->get_result(), third->expr->get_result(), newAlt.env, needAssertions, haveAssertions, openVars, indexer, commonType ) ) {
    10081008                                                ConditionalExpr *newExpr = new ConditionalExpr( first->expr->clone(), second->expr->clone(), third->expr->clone() );
  • src/ResolvExpr/Resolver.cc

    r30b65d8 r8f9cc50  
    7272                Type * functionReturn = nullptr;
    7373                Type *initContext = nullptr;
    74                 Type *switchType = nullptr;
    7574                bool inEnumDecl = false;
    7675        };
  • src/Tuples/TupleExpansion.cc

    r30b65d8 r8f9cc50  
    3232namespace Tuples {
    3333        namespace {
    34                 class MemberTupleExpander : public Mutator {
     34                class MemberTupleExpander final : public Mutator {
    3535                public:
    3636                        typedef Mutator Parent;
    37                         virtual Expression * mutate( UntypedMemberExpr * memberExpr );
    38                 };
    39 
    40                 class UniqueExprExpander : public GenPoly::DeclMutator {
     37                        using Parent::mutate;
     38
     39                        virtual Expression * mutate( UntypedMemberExpr * memberExpr ) override;
     40                };
     41
     42                class UniqueExprExpander final : public GenPoly::DeclMutator {
    4143                public:
    4244                        typedef GenPoly::DeclMutator Parent;
    43 
    44                         virtual Expression * mutate( UniqueExpr * unqExpr );
     45                        using Parent::mutate;
     46
     47                        virtual Expression * mutate( UniqueExpr * unqExpr ) override;
    4548
    4649                        std::map< int, Expression * > decls; // not vector, because order added may not be increasing order
     
    5659                public:
    5760                        typedef Mutator Parent;
     61                        using Parent::mutate;
     62
    5863                        virtual Expression * mutate( TupleAssignExpr * tupleExpr );
    5964                };
     
    6267                  public:
    6368                        typedef GenPoly::DeclMutator Parent;
    64 
    65                         virtual Type * mutate( TupleType * tupleType );
    66 
    67                         virtual CompoundStmt * mutate( CompoundStmt * stmt ) {
     69                        using Parent::mutate;
     70
     71                        virtual Type * mutate( TupleType * tupleType ) override;
     72
     73                        virtual CompoundStmt * mutate( CompoundStmt * stmt ) override {
    6874                                typeMap.beginScope();
    6975                                stmt = Parent::mutate( stmt );
     
    7581                };
    7682
    77                 class TupleIndexExpander : public Mutator {
     83                class TupleIndexExpander final : public Mutator {
    7884                public:
    7985                        typedef Mutator Parent;
    80                         virtual Expression * mutate( TupleIndexExpr * tupleExpr );
    81                 };
    82 
    83                 class TupleExprExpander : public Mutator {
     86                        using Parent::mutate;
     87
     88                        virtual Expression * mutate( TupleIndexExpr * tupleExpr ) override;
     89                };
     90
     91                class TupleExprExpander final : public Mutator {
    8492                public:
    8593                        typedef Mutator Parent;
    86                         virtual Expression * mutate( TupleExpr * tupleExpr );
     94                        using Parent::mutate;
     95                       
     96                        virtual Expression * mutate( TupleExpr * tupleExpr ) override;
    8797                };
    8898        }
     
    318328// compile-command: "make install" //
    319329// End: //
    320 
Note: See TracChangeset for help on using the changeset viewer.