This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Triton-private Repository". The branch, master has been updated via 314fbd23937dc125b797259898b8488d042a28d1 (commit) via 8000faa2c45b31c300a600561cc59be86d738e39 (commit) from 31ecc4a14bdeeed9cd52a1c56974a513b5dbec64 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 314fbd23937dc125b797259898b8488d042a28d1 Author: Phil Carns <[email protected]> Date: Thu Mar 15 21:35:03 2012 -0500 captions don't like \aesop I guess? commit 8000faa2c45b31c300a600561cc59be86d738e39 Author: Phil Carns <[email protected]> Date: Thu Mar 15 21:34:52 2012 -0500 Gail edits: programming model section ----------------------------------------------------------------------- Summary of changes: papers/2011/aesop/implementation.tex | 4 +- papers/2011/aesop/model.tex | 104 +++++++++++++++++----------------- 2 files changed, 53 insertions(+), 55 deletions(-) Diff of changes: diff --git a/papers/2011/aesop/implementation.tex b/papers/2011/aesop/implementation.tex index 933abcb..afce9d1 100644 --- a/papers/2011/aesop/implementation.tex +++ b/papers/2011/aesop/implementation.tex @@ -13,9 +13,7 @@ functions; all other code is passed through unmodified. %\vskip -0.25in \centering \includegraphics[keepaspectratio,width=0.48\textwidth]{stack.pdf} - \caption{Model of \aesop usage. - \label{fig:model} - } + \caption{Model of Aesop usage.\label{fig:model}} \end{figure} Figure~\ref{fig:model} shows how a blocking function, \code{service_function}, diff --git a/papers/2011/aesop/model.tex b/papers/2011/aesop/model.tex index ab61b63..6abbf5c 100644 --- a/papers/2011/aesop/model.tex +++ b/papers/2011/aesop/model.tex @@ -5,34 +5,35 @@ program model. \subsection{Parallel Branches} -Concurrency is expressed in \aesop through the use of {\em parallel branches} +Concurrency is expressed in \aesop through the use of {\em parallel branches}, or {\em pbranches}. A parallel branch groups a list of statements and supports branch-scoped variables, much like a regular function. Within a pbranch, statements are executed sequentially, as in a normal C program. -However, when multiple pbranches are active, the \aesop language only enforces -sequential execution within the scope of a single pbranch. Statements from +When multiple pbranches are active, however, the \aesop language enforces +sequential execution only within the scope of a single pbranch. Statements from other pbranches might interleave execution or might execute concurrently (using a thread for example). -It is possible to synchronize with pbranches using the \code{pwait} construct. +\aesop can synchronize pbranches by using the \code{pwait} construct. A pwait is similar to the barrier implicit in many OpenMP directives (such as parallel for), in that no statements following the pwait will execute unless -all of the pbranches it encloses have completed. +all the pbranches it encloses have completed. -By default, variables in \aesop are shared between pbranches. This is similar +By default, variables in \aesop are shared between pbranches. This +configuration is similar to OpenMP, where variables are shared between multiple threads unless indicated otherwise. Marking a variable as \code{pprivate} gives each pbranch -a private shadow copy, initialized using the shared instance when the branch -is created. Variables declared within a pbranch are -- adhering to the C -scoping rules -- necessarily private. +a private shadow copy, initialized by using the shared instance when the branch +is created. Variables declared within a pbranch are, adhering to the C +scoping rules, necessarily private. -It is possible for a pbranch to request the termination (or cancellation) of +A pbranch can request the termination (or cancellation) of all other pbranches within the same pwait by calling the \code{aesop_cancel_branches} function. This function returns as soon as the other pbranches have been marked for cancellation; it is asynchronous in that it does not wait for the other pbranches to exit. While pbranches are not forcibly terminated, a pbranch with an outstanding cancellation request -affects branch execution to ensure a race free delivery of the cancellation +affects branch execution to ensure a race-free delivery of the cancellation signal. If the pbranch is in a function call when the cancellation signal arrives, that function will be notified of the cancellation, enabling the function to take whatever steps necessary to cancel the operation and return a @@ -50,58 +51,58 @@ the needed code to do so. For example, if a device exposes an asynchronous API, \aesop will automatically call the corresponding \code{cancel} function when a pbranch waiting for the completion of an operation is cancelled. Many other libraries aimed at concurrent or asynchronous execution do not -support cancellation or only offer limited support. +support cancellation or offer only limited support. In Grand Central Dispatch, once a code block is dispatched to a queue, it can no longer be removed or cancelled. Likewise, OpenMP does not support cancelling helper threads in parallel for and other concurrency constructs. In both cases, the recommended practice is for the programmer to repeatedly check a cancellation flag. This becomes especially cumbersome if other -functions are called from within the concurrent code, as now those functions -have to have access to the cancellation variable as well. +functions are called from within the concurrent code, since now those functions +must have access to the cancellation variable as well. While the POSIX thread API supports a number of different cancellation modes, using them in production software is not trivial. In the \code{asynchronous} cancellation mode, depending on the system, thread execution might be halted -at any point, making it very hard for the programmer to properly track cleanup +at any point, making it hard for the programmer to properly track cleanup state. In the default \code{deferred} mode, cancellation is ignored by all but a small list of special functions (termed \code{cancellation points}). Many common C functions, such as \code{fread}, -may or may not -- depending on the system -- support cancellation. Most -don't support cancellation at all. This means that a portable program cannot +may or may not, depending on the system, support cancellation. Most +do not. Thus, a portable program cannot call any of these functions if timely cancellation is required. -\aesop also supports {\em lonely pbranches}, i.e.\ pbranches created outside -of a pwait. A lonely pbranch is similar to a POSIX detached thread in that +\aesop also supports {\em lonely pbranches}, that is, pbranches created outside +a pwait. A lonely pbranch is similar to a POSIX detached thread in that lonely pbranches cannot be cancelled or synchronized with. \subsection{Blocking Functions} \aesop extends the C programming language with a new function type: {\em -blocking} functions. The blocking qualifyier is part of the type. A pointer to +blocking} functions. The blocking qualifier is part of the type. A pointer to a regular C function is not compatible with a function pointer to a blocking function with the same function arguments. Blocking functions differ from regular C functions in that only blocking functions can contain pbranches. -In addition, blocking functions support {\em cancellation}. +In addition, blocking functions support cancellation. Functions can be made blocking by adding the \code{__blocking} -qualifier to the function declaration. However, blocking functions can only be -called (either directly or indirectly through a blocking function pointer) by -other blocking functions. This effectively requires the starting function of -an \aesop program to be blocking. \aesop libraries form an exception to this +qualifier to the function declaration. However, blocking functions can be +called (either directly or indirectly through a blocking function pointer) only by +other blocking functions. Thence, the starting function of +an \aesop program must be blocking. \aesop libraries form an exception to this rule. To simplify calling \aesop libraries from C -and other languages, it is possible to generate C function stubs for a -blocking \aesop function. These stubs can either be synchronous, in which case -the stub only returns once the blocking function completed, or asynchronous, +and other languages, one can generate C function stubs for a +blocking \aesop function. These stubs can be either synchronous, in which case +the stub returns only after the blocking function completed, or asynchronous, in which case the stub returns as soon as progress can no longer be made. -To handle completion in the latter case, a callback -- called when the -blocking function completes -- can be specified. +In order to handle completion in the latter case, a callback, called when the +blocking function completes, can be specified. % cancellation An active blocking function in a pbranch receiving a cancellation request will -be notified of the cancellation. The effect of this notification, and the way -the function reacts to this request, depends on the implementation of that +be notified of the cancellation. The effect of this notification and the way +the function reacts to this request depend on the implementation of that particular function. Likewise, any subsequent blocking call initiated in that pbranch will learn of the active cancellation request. While this is not enforced by the language, a proper blocking function should return as soon as @@ -109,10 +110,10 @@ possible when a branch is in a cancelled state. % when to use blocking functions -The intention is that functions that are not completely cpu-bound (i.e. cannot +The intention is that functions that are not completely cpu-bound (i.e., cannot efficiently fully consume a thread) are to be made blocking. The \aesop language provides a way for blocking functions to indicate they can no longer -make progress (for example because the function is waiting on an external +make progress (for example, because the function is waiting on an external event or device). When this happens, execution will continue in another branch. @@ -123,21 +124,21 @@ that, when one or more pbranches within the program are ready to execute, at least one of them will make progress. For example, in a pwait containing two branches, if one branch should stall on a blocking function (for example waiting for I/O), execution will proceed in the second pbranch provided that -pbranch is ready to do so. +pbranch is ready. % multiple threads In effect, the \aesop programming model provides for multiplexing multiple -pbranches onto a single thread or core, similar to application implemented +pbranches onto a single thread or core, similar to application-implemented user space threading with voluntary yielding. This does not preclude true -multi-threading; \aesop is fully thread-safe, and it is possible to have -multiple OS threads executing within a single aesop program. In fact, -we routinely use multiple threads to run aesop +multithreading; \aesop is fully thread-safe and +multiple OS threads can execute within a single \aesop program. In fact, +we routinely use multiple threads to run \aesop code. In that case, if more than one pbranch becomes ready for execution, multiple threads will be used to execute those branches concurrently. \begin{figure} \center - \begin{lstlisting}[caption={Aesop Code Example}, + \begin{lstlisting}[caption={Aesop code example}, label=lst:parallelfor] __blocking void doReplicaWrite (...) { pwait { @@ -173,10 +174,10 @@ __blocking void write (...) { \subsection{Example Aesop Code} \label{sec:example} -Listing~\ref{lst:parallelfor} shows a common aesop code pattern. -Network servers, having a finite set of resources, have to protect against -unbounded resource consumption by misbehaving or failing peers. This is -typically done by placing an upper limit on the time resources are dedicated +Listing~\ref{lst:parallelfor} shows a common \aesop code pattern. +Network servers, having a finite set of resources, must protect against +unbounded resource consumption by misbehaving or failing peers. +Typically, an upper limit is placed on the time resources are dedicated to a request, cancelling the request when the allocated time is exceeded. @@ -186,20 +187,19 @@ Since the pbranch statement does not wait for the completion of the branch, the next iteration of the \code{for} loop can start before the previous one completed. In \code{replicateWrite}, a common pattern for easily handling time-outs can be seen. Two pbranches are created, one to execute the work and -the other one to bound maximum time the other branch is allowed to execute. +the other to bound the maximum time the other branch is allowed to execute. When one of the branches completes, as a last task it cancels the other -branch. This means that if \code{doReplicateWrite} (line 15) completes first, +branch. Thus, if \code{doReplicateWrite} (line 15) completes first, the operation completed within the allocated time frame, and the timer (line 4) will be cancelled. However, if line 15 takes longer than \code{TIMEOUT} -milliseconds, the timer (line 11) will complete first causing the ongoing +to complete, the timer (line 11) will complete first, causing the ongoing \code{doReplicaWrite} operation to be cancelled. Note how \code{replicaWrite}, -in a straightforward an reusable manner, adds a time-out to the existing +in a straightforward and reusable manner, adds a time-out to the existing \code{doReplicaWrite} call. The short code fragment from listing~\ref{lst:parallelfor} effectively -implemented the pattern shown in figure~\ref{fig:sm}, in which a number of -concurrent write operations are started, each consisting of three tasks which -can be executed concurrently and each write operation is protected by a time -out. +implemented the pattern shown in Figure~\ref{fig:sm}, in which a number of +concurrent write operations are started; each consists of three tasks that +can be executed concurrently, and each write operation is protected by a timeout. hooks/post-receive -- Triton-private Repository