Changes in doc/proposals/concurrency/concurrency.tex [b512454:d1fbaa7]

File:

• doc/proposals/concurrency/concurrency.tex (modified) (10 diffs)

doc/proposals/concurrency/concurrency.tex

@@ -62 +62 @@
 \newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
 \newcommand{\code}[1]{\lstinline{#1}}
+\newcommand{\pseudo}[1]{\lstinline[language=Pseudo]{#1}}
 
 \input{glossary}
@@ -510 +511 @@
 \begin{center}
 \begin{tabular}{l}
-\begin{lstlisting}
-        ¶if¶ critical section is free :
+\begin{lstlisting}[language=Pseudo]
+        if monitor is free :
                 enter
-        elif critical section accepts me :
+        elif monitor accepts me :
                 enter
-        ¶else¶ :
+        else :
                 block
 \end{lstlisting}
@@ -521 +522 @@
 \end{center}
 
-For the \code{critical section is free} condition it is easy to implement a check that can evaluate the condition in a few instruction. However, a fast check for \code{critical section accepts me} is much harder to implement depending on the constraints put on the monitors. Indeed, monitors are often expressed as an entry queue and some acceptor queue as in the following figure :
-
-\begin{center}
-{\resizebox{0.5\textwidth}{!}{\input{monitor}}}
-\end{center}
-
-There are other alternatives to these pictures but in the case of this picture implementing a fast accept check is relatively easy. Indeed simply updating a bitmask when the acceptor queue changes is enough to have a check that executes in a single instruction, even with a fairly large number of acceptor. However, this requires all the acceptable routines to be declared with the monitor declaration. For OO languages this doesn't compromise much since monitors already have an exhaustive list of member routines. However, for \CFA this isn't the case, routines can be added to a type anywhere after its declaration. A more flexible
-
-
-At this point we must make a decision between flexibility and performance. Many design decisions in \CFA achieve both flexibility and performance, for example polymorphic routines add significant flexibility but inlining them means the optimizer can easily remove any runtime cost.
-
-This approach leads to the \uC example being translated to :
-\begin{lstlisting}
-        accept( void g(mutex struct A & mutex a) )
-        mutex struct A {};
-
-        void f(A & mutex a) { accept(g); }
-        void g(A & mutex a);
-\end{lstlisting}
-
-This syntax is the most consistent with the language since it somewhat mimics the \code{forall} declarations. However, the fact that it comes before the struct declaration does means the type needs to be forward declared (done inline in the example). Here are a few alternatives to this syntax : \\
-\begin{tabular}[t]{l l}
+For the \pseudo{monitor is free} condition it is easy to implement a check that can evaluate the condition in a few instruction. However, a fast check for \pseudo{monitor accepts me} is much harder to implement depending on the constraints put on the monitors. Indeed, monitors are often expressed as an entry queue and some acceptor queue as in the following figure :
+
+\begin{center}
+{\resizebox{0.4\textwidth}{!}{\input{monitor}}}
+\end{center}
+
+There are other alternatives to these pictures but in the case of this picture implementing a fast accept check is relatively easy. Indeed simply updating a bitmask when the acceptor queue changes is enough to have a check that executes in a single instruction, even with a fairly large number of acceptor. However, this relies on the fact that all the acceptable routines are declared with the monitor type. For OO languages this doesn't compromise much since monitors already have an exhaustive list of member routines. However, for \CFA this isn't the case, routines can be added to a type anywhere after its declaration. Its important to note that the bitmask approach does not actually require an exhaustive list of routines, but it requires a dense unique ordering of routines with an upper-bound and that ordering must be consistent across translation units.
+The alternative would be to have a picture more like this one:
+
+\begin{center}
+{\resizebox{0.4\textwidth}{!}{\input{ext_monitor}}}
+\end{center}
+
+Not storing the queues inside the monitor means that the storage can vary between routines, allowing for more flexibility and extensions. Storing an array of function-pointers would solve the issue of uniquely identifying acceptable routines. However, the single instruction bitmask compare has been replaced by dereferencing a pointer followed by a linear search. Furthermore, supporting nested external scheduling may now require additionnal searches on calls to accept to check if a routine is already queued in.
+
+At this point we must make a decision between flexibility and performance. Many design decisions in \CFA achieve both flexibility and performance, for example polymorphic routines add significant flexibility but inlining them means the optimizer can easily remove any runtime cost. Here however, the cost of flexibility cannot be trivially removed.
+
+In either cases here are a few alternatives for the different syntaxes this syntax : \\
+\begin{center}
+{\renewcommand{\arraystretch}{1.5}
+\begin{tabular}[t]{l @{\hskip 0.35in} l}
+\hline
+\multicolumn{2}{ c }{\code{accept} on type}\\
+\hline
 Alternative 1 & Alternative 2 \\
 \begin{lstlisting}
 mutex struct A
-accept( void g(A & mutex a) )
+accept( void f(A & mutex a) )
 {};
 \end{lstlisting} &\begin{lstlisting}
 mutex struct A {}
-accept( void g(A & mutex a) );
+accept( void f(A & mutex a) );
 
 \end{lstlisting} \\
@@ -556 +559 @@
 \begin{lstlisting}
 mutex struct A {
-        accept( void g(A & mutex a) )
+        accept( void f(A & mutex a) )
 };
 
@@ -562 +565 @@
 mutex struct A {
         accept :
-                void g(A & mutex a) );
+                void f(A & mutex a) );
 };
-\end{lstlisting}
+\end{lstlisting}\\
+\hline
+\multicolumn{2}{ c }{\code{accept} on routine}\\
+\hline
+\begin{lstlisting}
+mutex struct A {};
+
+void f(A & mutex a)
+
+accept( void f(A & mutex a) )
+void g(A & mutex a) {
+        /*...*/
+}
+\end{lstlisting}&\\
 \end{tabular}
-
+}
+\end{center}
 
 An other aspect to consider is what happens if multiple overloads of the same routine are used. For the time being it is assumed that multiple overloads of the same routine should be scheduled regardless of the overload used. However, this could easily be extended in the future.
@@ -597 +614 @@
 \end{lstlisting}
 
-This is unambiguous. The both locks will be acquired and kept, when routine \code{f} is called the lock for monitor \code{a} will be temporarily transferred from \code{g} to \code{f} (while \code{g} still holds lock \code{b}). This behavior can be extended to multi-monitor accept statment as follows.
+This is unambiguous. Both locks will be acquired and kept, when routine \code{f} is called the lock for monitor \code{a} will be temporarily transferred from \code{g} to \code{f} (while \code{g} still holds lock \code{b}). This behavior can be extended to multi-monitor accept statment as follows.
 
 \begin{lstlisting}
@@ -613 +630 @@
 
 \subsubsection{Implementation Details: External scheduling queues}
-To support multi-monitor external scheduling means that some kind of entry-queues must be used that is aware of both monitors. However, acceptable routines must be aware of the entry queues which means they most be stored inside at least one of the monitors that will be acquired. This in turn adds the requirement a systematic algorithm of disambiguating which queue is relavant regardless of user ordering. The proposed algorithm is to fall back on monitors lock ordering and specify that the monitor that is acquired first is the lock with the relevant entry queue. This assumes that the lock acquiring order is static for the lifetime of all concerned objects gut that is a reasonnable contraint. This algorithm choice has two consequences, the ofthe highest priority monitor is no longer a true FIFO queue and the queue of the lowest priority monitor is both required and probably unused. The queue can no longer be a FIFO queue because instead of simply containing the waiting threads in order arrival, they also contain the second mutex. Therefore, another thread with the same highest priority monitor but a different lowest priority monitor may arrive first but enter the critical section after a thread with the correct pairing. Secondly, since it may not be known at compile time which monitor will be the lowest priority monitor, every monitor needs to have the correct queues even though it is probably that half the multi-monitor queues will go unused for the entire duration of the program.
+To support multi-monitor external scheduling means that some kind of entry-queues must be used that is aware of both monitors. However, acceptable routines must be aware of the entry queues which means they must be stored inside at least one of the monitors that will be acquired. This in turn adds the requirement a systematic algorithm of disambiguating which queue is relavant regardless of user ordering. The proposed algorithm is to fall back on monitors lock ordering and specify that the monitor that is acquired first is the lock with the relevant entry queue. This assumes that the lock acquiring order is static for the lifetime of all concerned objects but that is a reasonnable constraint. This algorithm choice has two consequences, the entry queue of the highest priority monitor is no longer a true FIFO queue and the queue of the lowest priority monitor is both required and probably unused. The queue can no longer be a FIFO queue because instead of simply containing the waiting threads in order arrival, they also contain the second mutex. Therefore, another thread with the same highest priority monitor but a different lowest priority monitor may arrive first but enter the critical section after a thread with the correct pairing. Secondly, since it may not be known at compile time which monitor will be the lowest priority monitor, every monitor needs to have the correct queues even though it is probable that half the multi-monitor queues will go unused for the entire duration of the program.
 
 \subsection{Other concurrency tools}
-
+TO BE CONTINUED...
+
+\newpage
 \section{Parallelism}
-Historically, computer performance was about processor speeds and instructions count. However, with heat dissipaction 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 create high-performance application without caring about parallelism. Indeed, parallelism an important aspect of performance and more specifically throughput and hardware utilization. The lowest level approach 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.
+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.
 
 \subsection{User-level threads}
@@ -624 +643 @@
 
 Examples of languages that support are Java\cite{Java}, Haskell\cite{Haskell} and \uC\cite{uC++book}.
+
 \subsection{Jobs and thread pools}
-The opposite approach 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. The golden standard of this implementation is Intel's TBB library\cite{TBB}.
+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.
+The golden standard of this implementation is Intel's TBB library\cite{TBB}.
 
 \subsection{Fibers : user-level threads without preemption}
 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.
-\cite{Go}
+An example of a language that uses fibers is Go\cite{Go}
 
 \subsection{Paradigm performance}
-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 own 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 fully armoticised by the actual work done.
+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.
 
 \section{\CFA 's Thread Building Blocks}
@@ -687 +708 @@
 \end{lstlisting}
 
-In this example \code{func} is a function pointer stored in \acrfull{tls}, which is \CFA is both easy to use and completly typesafe.
-
-Of course for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution. While using \acrshort{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is not needed. Indeed, the simplest approach is to use \acrshort{raii} principles and have threads \code{fork} once the constructor has completed and \code{join} before the destructor runs.
+% In this example \code{func} is a function pointer stored in \acrfull{tls}, which is \CFA is both easy to use and completly typesafe.
+
+Of course for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution. While using an \acrshort{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is not needed. Indeed, the simplest approach is to use \acrshort{raii} principles and have threads \code{fork} once the constructor has completed and \code{join} before the destructor runs.
 \begin{lstlisting}
 thread struct FuncRunner; //FuncRunner declared above
@@ -733 +754 @@
 \end{lstlisting}
 
+\newpage
+\large{\textbf{WORK IN PROGRESS}}
 \subsection{The \CFA Kernel : Processors, Clusters and Threads}\label{kernel}