Changeset d67cdb7 for doc/proposals/concurrency/text/parallelism.tex

Timestamp:

Sep 26, 2017, 11:27:38 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:

5dc26f5

Parents:

201aeb9

Message:

merge

File:

• doc/proposals/concurrency/text/parallelism.tex (modified) (1 diff)

doc/proposals/concurrency/text/parallelism.tex

@@ -11 +11 @@
 \section{Paradigm}
 \subsection{User-level threads}
-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 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.
+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 approach is the most powerfull solution as it allows all the features of multi-threading, while removing several of the more expensive costs of 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.
 
 Examples of languages that support \glspl{uthread} are Erlang~\cite{Erlang} and \uC~\cite{uC++book}.
 
 \subsection{Fibers : user-level threads without preemption}
-A popular varient of \glspl{uthread} is what is often reffered to as \glspl{fiber}. However, \glspl{fiber} do not present meaningful semantical differences with \glspl{uthread}. Advocates of \glspl{fiber} list their high performance and ease of implementation as majors strenghts of \glspl{fiber} but the performance difference between \glspl{uthread} and \glspl{fiber} is controversial and the ease of implementation, while true, is a weak argument in the context of language design. Therefore this proposal largely ignore fibers.
+A popular varient of \glspl{uthread} is what is often refered to as \glspl{fiber}. However, \glspl{fiber} do not present meaningful semantical differences with \glspl{uthread}. Advocates of \glspl{fiber} list their high performance and ease of implementation as majors strenghts of \glspl{fiber} but the performance difference between \glspl{uthread} and \glspl{fiber} is controversial, and the ease of implementation, while true, is a weak argument in the context of language design. Therefore this proposal largely ignore fibers.
 
 An example of a language that uses fibers is Go~\cite{Go}
 
 \subsection{Jobs and thread pools}
-The 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 a 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 among 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 always results in idles cores.
+The 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, called jobs, and a 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 among 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 always results in idles cores.
 
 The gold standard of this implementation is Intel's TBB library~\cite{TBB}.
 
 \subsection{Paradigm performance}
-While 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 allow fine-grain context switching, which results in better resource utilisation, but context switches will be more expansive and the extra control means users need to tweak more variables to get the desired performance. Furthermore, if the units of uninterrupted work are large enough the paradigm choice is largely amorticised by the actual work done.
+While 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 (i.e., not thread stack per job). However, interactions among jobs can easily exacerbate contention. User-level threads allow fine-grain context switching, which results in better resource utilisation, but context switches is more expansive and the extra control means users need to tweak more variables to get the desired performance. Finally, if the units of uninterrupted work are large enough the paradigm choice is largely amortised by the actual work done.
 
-\newpage
 \TODO
-\subsection{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}
+
+\section{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}
 
 
+\subsubsection{Future Work: Machine setup}\label{machine}
+While this was not done in the context of this proposal, another important aspect of clusters is affinity. While many common desktop and laptop PCs have homogeneous CPUs, other devices often have more heteregenous setups. For example, system using \acrshort{numa} configurations may benefit from users being able to tie clusters and/or kernel threads to certains CPU cores. OS support for CPU affinity is now common \cit, which means it is both possible and desirable for \CFA to offer an abstraction mechanism for portable CPU affinity.
+
 \subsection{Paradigms}\label{cfaparadigms}
-Given these building blocks we can then reproduce the all three of the popular paradigms. Indeed, we get \glspl{uthread} as the default paradigm in \CFA. However, disabling \glspl{preemption} on the \gls{cfacluster} means \glspl{cfathread} effectively become \glspl{fiber}. Since several \glspl{cfacluster} with different scheduling policy can coexist in the same application, this allows \glspl{fiber} and \glspl{uthread} to coexist in the runtime of an application.
-
-% \subsection{High-level options}\label{tasks}
-%
-% \subsubsection{Thread interface}
-% constructors destructors
-%       initializer lists
-% monitors
-%
-% \subsubsection{Futures}
-%
-% \subsubsection{Implicit threading}
-% Finally, simpler applications can benefit greatly from having implicit parallelism. That is, parallelism that does not rely on the user to write concurrency. This type of parallelism can be achieved both at the language level and at the system level.
-%
-% \begin{center}
-% \begin{tabular}[t]{|c|c|c|}
-% Sequential & System Parallel & Language Parallel \\
-% \begin{lstlisting}
-% void big_sum(int* a, int* b,
-%                int* out,
-%                size_t length)
-% {
-%       for(int i = 0; i < length; ++i ) {
-%               out[i] = a[i] + b[i];
-%       }
-% }
-%
-%
-%
-%
-%
-% int* a[10000];
-% int* b[10000];
-% int* c[10000];
-% //... fill in a and b ...
-% big_sum(a, b, c, 10000);
-% \end{lstlisting} &\begin{lstlisting}
-% void big_sum(int* a, int* b,
-%                int* out,
-%                size_t length)
-% {
-%       range ar(a, a + length);
-%       range br(b, b + length);
-%       range or(out, out + length);
-%       parfor( ai, bi, oi,
-%       [](int* ai, int* bi, int* oi) {
-%               oi = ai + bi;
-%       });
-% }
-%
-% int* a[10000];
-% int* b[10000];
-% int* c[10000];
-% //... fill in a and b ...
-% big_sum(a, b, c, 10000);
-% \end{lstlisting}&\begin{lstlisting}
-% void big_sum(int* a, int* b,
-%                int* out,
-%                size_t length)
-% {
-%       for (ai, bi, oi) in (a, b, out) {
-%               oi = ai + bi;
-%       }
-% }
-%
-%
-%
-%
-%
-% int* a[10000];
-% int* b[10000];
-% int* c[10000];
-% //... fill in a and b ...
-% big_sum(a, b, c, 10000);
-% \end{lstlisting}
-% \end{tabular}
-% \end{center}
-%
-% \subsection{Machine setup}\label{machine}
-% Threads are all good and well but wee still some OS support to fully utilize available hardware.
-%
-% \textbf{\large{Work in progress...}} Do wee need something beyond specifying the number of kernel threads?
+Given these building blocks, it is possible to reproduce all three of the popular paradigms. Indeed, \glspl{uthread} is the default paradigm in \CFA. However, disabling \glspl{preemption} on the \gls{cfacluster} means \glspl{cfathread} effectively become \glspl{fiber}. Since several \glspl{cfacluster} with different scheduling policy can coexist in the same application, this allows \glspl{fiber} and \glspl{uthread} to coexist in the runtime of an application. Finally, it is possible to build executors for thread pools from \glspl{uthread} or \glspl{fiber}.