% -*-latex-*-
\chapter{How Cilk Works}
\index{compiling Cilk|(}
\index{scheduling|(}
\label{chap:impl-notes}

\newcommand{\cilktoc}{\texttt{cilk2c}}

This section outlines the basic runtime assumptions and compilation
schemes for Cilk procedures, which may be useful to those wishing to
understand more about Cilk implementation or the C code generated by
the \cilktoc{} compiler.

We first describe how a Cilk program is scheduled on one processor
(nanoscheduling), and then describe how a Cilk program is scheduled on
multiple processors.  Cilk currently has no job scheduler (the
scheduling of multiple simultaneous Cilk programs).

\section{Nanoscheduling}
\indexsub{scheduling}{nanoscheduling}{|(}

The nanoscheduler's job is to schedule procedures within a single
processor.  It is very important that the nanoscheduler make
scheduling decisions quickly, so the nanoscheduler is ``compiled''
into the source code by \cilktoc.  The nanoscheduler's algorithm is
very simple: it executes a procedure and its subprocedures in exactly
the same order as they would execute in C\@.  This schedule guarantees
that on one processor, when no microscheduling is needed, the Cilk
code executes in the same order as the C code.

The nanoscheduler is very easy to implement.  The \cilktoc\ compiler
translates each Cilk procedure into a C procedure with the same
arguments and return value.  Each spawn is translated into its
equivalent C function call.  Each sync is translated into a
no-operation, because all children would have already completed by the
time the sync point is reached.

In order to enable the use of our microscheduler, we must add some
code to the nanoscheduler to keep track of the current scheduling
state.  The nanoscheduler uses a deque of frames for this purpose.  A
\sysname\
\defn{frame}\indexsub{scheduling}{frame}{|textbf}
is a data structure which can hold the state of a procedure, and is
analogous to a C activation frame.  A
\defn{deque}\indexsub{scheduling}{deque}{|textbf}
is a doubly-ended queue, which can be thought of as a stack from the
nanoscheduler's perspective.  The deque is tightly coupled to the C
stack, with a one-to-one correspondence between the frames on the
deque and the activation frames on the C stack.\footnote{We maintain a
separate deque instead of using the native C stack to maintain
portability.  Someday, we hope to merge the frame deque and the native
C stack, which will further reduce the overhead of the nanoscheduler.}

The nanoscheduler performs the following additional operations to keep
track of the state of the computation.  When a procedure is first
called, it initializes a frame to hold its saved state, and pushes
this frame on the bottom of the frame deque.  When a spawn occurs, the
state of the current procedure is saved in this frame.  Finally, when
the procedure completes and returns to its parent, its frame is
popped.

\begin{figure}
{\small \input{fib}}
\caption{\small Nanoscheduled version of \texttt{fib}.}
\label{fig:nanofib}
\end{figure}

\figref{nanofib} shows the nanoscheduled version of the Fibonacci
example from \figref{fib}(b).  \cilktoc\ generates a frame for the
{\tt fib} procedure to hold all of its state.  The state of {\tt fib}
includes its argument {\tt n} and its two local variables, {\tt x} and
{\tt y}.  Additional state, such as the procedure ID and program
counter, are stored in the header.

The procedure fib has one additional local variable,
\texttt{\_frame}\indexvar{frame@\texttt{\_frame}}{}, which holds a
pointer to the procedure's frame.  The frame is initialized and pushed
onto the deque with the
\texttt{\_INIT\_FRAME}\indexmac{INITFRAME@\texttt{\_INIT\_FRAME}}{}
macro.  For each spawn, the state of the procedure is saved into the
frame.  The state that is saved includes the entry number
(representing the program counter), and each live, dirty variable.
For instance, the first spawn, identified by entry number 1, saves the
entry number and the argument {\tt n} into the frame.  The spawned
procedure is then called with a normal C function call.  After the
function call returns, execution of the parent resumes after the
spawn.  The second spawn is the same as the first, except it has entry
number 2, and the only live, dirty variable is {\tt x}.

The nanoscheduler must check to see whether the procedure has been
migrated after each spawn call.  This check is done in the
\texttt{\_XPOP\_FRAME\_RESULT}\indexmac{XPOPFRAMERESULT@\texttt{\_XPOP\_FRAME\_RESULT}}{}
macro by checking if the current frame is still in the frame deque.
If the frame is not in the deque, then it has been migrated, in which
case {\tt \_XPOP\_FRAME\_RESULT} returns immediately with a dummy
return value. This immediate return feature quickly cleans up the C
stack when the frame deque becomes empty.  Otherwise, the procedure
can be resumed after the spawn call in normal C fashion.

\note{A little more explanation would be helpful here.  Which frame is
\texttt{\_XPOP\_FRAME\_RESULT} popping?  Or is it actually not popping
any frame?  What happens after \texttt{\_XPOP\_FRAME\_RESULT} returns
with a dummy value? What happens if the frame has not been migrated?
Why are $x$ and $y$ included as arguments to
\texttt{\_XPOP\_FRAME\_RESULT}, and what do the 0 arguments do? --
Bruce}

Finally, when a procedure returns, the nanoscheduler pops its frame
off the deque and frees it using the
\texttt{\_BEFORE\_RETURN\_FAST}\indexmac{BEFORERETURNFAST@\texttt{\_BEFORE\_RETURN\_FAST}}{}
macro.

Note that during nanoscheduling, the state information written to the
frame deque is never used.  The nanoscheduler is simply recording
this information for use by the microscheduler, which is described in
the next section.
\indexsub{scheduling}{nanoscheduling}{|)}

\section{Microscheduling}
\indexsub{scheduling}{microscheduling}{|(}

The microscheduler's job is to schedule procedures across a fixed set
of processors.  The microscheduler is implemented as a randomized
work-stealing scheduler.  Specifically, when a processor runs out of
work, it becomes a \defn{thief}\indexsub{scheduling}{thief}{|textbf}
and steals work from a
\defn{victim}\indexsub{scheduling}{victim}{|textbf} processor chosen
uniformly at random.  When it finds a victim with some frames in its
deque, it takes the topmost frame (the least recently pushed frame) on
the victim's deque and places it in its own deque.  It then gives the
corresponding procedure to the nanoscheduler to execute.

\indexsub{scheduling}{slow version}{|(textbf} The procedure given to
the nanoscheduler is a different version of the stolen procedure,
however.  We call this version the ``slow'' version of the procedure,
because it has a higher overhead than the normal nanoscheduled
routine.  Because the slow version is invoked from a generic
scheduling routine, its interface is standard.  Instead of receiving
its arguments as C arguments, it receives a pointer to its frame as
its only argument, from which it can extract its arguments and local
state.  It also produces a return value using the macro
\texttt{\_SET\_RESULT}\indexmac{SETRESULT@\texttt{\_SET\_RESULT}}{}
instead of returning a result normally.  Finally, because this
procedure may have outstanding children on another processor, it may
suspend at a synchronization point.

\begin{figure}
{\footnotesize \input{fib2}}
\caption{\small Microscheduled version of \texttt{fib}.}
\label{fig:microfib}
\end{figure}

\figref{microfib} shows the microscheduled version of the Fibonacci
example from \figref{fib}(b).  The microscheduled version takes a
pointer to the frame as its only argument, and returns void.  The
first thing the microscheduled function does is to restore its state,
first restoring the program counter using the {\tt switch} statement, and then
restoring local variables using the state-restoring code at each {\tt
sync} label.

For each return in the Cilk code, instead of returning the value as in
C, the slow version uses
\texttt{\_SET\_RESULT}\indexmac{SETRESULT@\texttt{\_SET\_RESULT}}{} to record the return value
in a temporary area and then returns a void value.  The runtime system
can then read the return value from this temporary area and store it in
the appropriate final destination.

\note{A little more explanation might be helpful here.  Why isn't
there are called to \texttt{\_INIT\_FRAME} in the slow version? -- Bruce}

At each synchronization point, the slow version needs to save its
state and then check whether
any return values are still outstanding.  It does this with the
\texttt{\_SYNC}\indexmac{SYNCmacro@\texttt{\_SYNC}}{} macro, which returns
non-zero if any children are still outstanding.  If there are still
children outstanding, the slow version returns to the scheduler, where
it is suspended by the runtime system.

Since slow versions of procedures are created only during a steal,
they are always topmost in a processor's frame deque.  All other
procedures in the frame deque are the standard, fast, nanoscheduled
versions.  Therefore, as long as the number of steals is small, most
of the computation is performed using the nanoscheduled routines.
\indexsub{scheduling}{slow version}{|)textbf}
\indexsub{scheduling}{microscheduling}{|)}
\index{compiling Cilk|)}

Note how we make extensive use of Duff's Device~\cite{Duff83} to jump into the middle of C code.

\section{Overheads}
\indexsub{scheduling}{overhead}{|(}

The overhead of the nanoscheduler, as compared to a serial C version,
comes from five factors:
\begin{itemize}

\item A procedure's frame needs to be allocated, initialized, and
pushed on the deque at the start of each procedure.  These operations
can be performed in less than a dozen assembly instructions.

\item A procedure's state needs to be saved before each spawn.  The
entry number and each live, dirty variable must be saved.  Note that
some memory synchronization operations are also required at this point
for architectures which do not implement sequential consistency (see
\secref{weak-mem-interaction} for details).

\item A procedure must check whether its frame has been stolen after
each spawn.  This check requires only two reads, a compare, and a
branch.  Again, memory synchronization operations are required at this
point for architectures which do not implement sequential consistency.

\item On return, a procedure must free its frame, which takes only a
few instructions.

\item One extra variable is needed to hold the frame pointer.  This
extra variable imposes a small amount of additional register pressure
on the compiler's register allocator.

\end{itemize}

This overhead is very small in practice.  For instance, the Cilk
Fibonacci program runs only $3$ times slower than the sequential C
program on one processor.  For programs with larger thread lengths,
this overhead would be minimal.
\indexsub{scheduling}{overhead}{|)}

\note{Can we say anything about the overhead of the microscheduler? --
Bruce}

\section{Interactions with weak memory models}
\indexsubt{scheduling}{shared memory}{weak memory models}{|(}
\label{sec:weak-mem-interaction}

In general, the \sysnameversion\ scheduler will work for any reasonable
consistency model supported by modern SMPs.  The \sysname\ scheduler
requires stronger consistency in the three following areas:

\begin{itemize}

\item The scheduler requires that obtaining a lock on a data structure
guarantees atomic access to that data structure.

\item When a frame is pushed on the deque, the scheduler requires that
all writes must be globally visible before the tail pointer (the end
of deque pointer) is incremented.  In systems where writes can be
reordered, a memory barrier of some sort must be inserted before the
pointer increment.  Writes remain ordered on our current platform
(UltraSPARC SMP), so no barrier is needed for our implementation.

\item When a frame is popped from the deque, the scheduler requires
that the write of the tail pointer be globally visible before the read
of the exception pointer is performed.  In systems where reads can be
performed before preceeding writes are globally visible, a memory
barrier of some sort must be inserted before the read of the exception
pointer.  Our UltraSPARC SMP implementation requires a ``StoreLoad''
barrier at this point.

\end{itemize}

Note that the last two requirements are simply optimizations to avoid
the cost of a lock acquire and release on each push and pop of a
frame.  In the worst case, the last two requirements can be
implemented using a lock acquire and release.
\indexsubt{scheduling}{shared memory}{weak memory models}{|)}
\index{scheduling|)}

% $Log: impl-notes.tex,v $
% Revision 1.1.1.1  2000/06/22 08:04:15  matley
% Initial Cilk import into sourceforge
%
% Revision 1.3  2000/06/03 13:07:31  athena
% Revised manual.
%
% Revision 1.2  2000/05/25 19:44:59  athena
% Manual is now down to 42 pages.  Clearly, this is a sign of $DEITY.
%
% Revision 1.1  2000/05/04 21:11:52  athena
% Added manual, AUTHORS.
%
% Revision 1.18  1998/11/03 18:01:08  bmm
% Corrected many small typos and added comments where I didn't understand
% something.
%
% Revision 1.17  1998/07/17 03:05:31  cel
% Extremely minor edits.
%
