source: doc/proposals/concurrency/text/parallelism.tex @ bf70aa9

% ######     #    ######     #    #       #       ####### #       ###  #####  #     #
% #     #   # #   #     #   # #   #       #       #       #        #  #     # ##   ##
% #     #  #   #  #     #  #   #  #       #       #       #        #  #       # # # #
% ######  #     # ######  #     # #       #       #####   #        #   #####  #  #  #
% #       ####### #   #   ####### #       #       #       #        #        # #     #
% #       #     # #    #  #     # #       #       #       #        #  #     # #     #
% #       #     # #     # #     # ####### ####### ####### ####### ###  #####  #     #
\chapter{Parallelism}
Historically, 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 a 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.

\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.

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.

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 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.

\newpage
\TODO
\subsection{The \protect\CFA\ Kernel : Processors, Clusters and Threads}\label{kernel}


\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?