path: root/Carpet/doc/scheduling.tex

\documentclass{article}

\addtolength{\oddsidemargin}{-25mm}
\addtolength{\textwidth}{50mm}
\addtolength{\textheight}{50mm}
\addtolength{\topmargin}{-20mm}

\renewcommand{\bottomfraction}{0.75}
\addtolength{\textfloatsep}{5ex}

% Make a comment stand out visually
\def\todo#1{\textbf{Erik: #1}}
%%\newcommand{\todo}[1]{$\blacksquare$~\textsf{[#1]}}

\def\arrangement#1{\textbf{#1}}
\def\thorn#1{\textbf{#1}}

% get size/spacing of "++" right, cf online C++ FAQ question 35.1
\def\Cplusplus{\hbox{C\raise.25ex\hbox{\footnotesize ++}}}

\def\ie{i.e.\hbox{}}
\def\eg{e.g.\hbox{}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\author{Thomas Radke and Jonathan Thornburg}
\title{Carpet Scheduling}
\date{2 November 2006}
\maketitle
\begin{abstract}
This document describes how scheduling works in (\thorn{PUGH} and)
\thorn{Carpet}.  This information is particularly useful if you're
using \thorn{Carpet} and you need to do a mixture of local computations
at each grid point (\eg{} computing some grid function), and global
operations which need to operate across multiple grids (\eg{} computing
norms of this grid function).
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Cactus offers a predefined set of about 20 schedule bins corresponding
to major phases of a simulation, like \verb|BASEGRID|, \verb|INITIAL|,
\verb|POSTINITIAL|, \verb|EVOL|, etc.  See the Cactus Users' Guide for
an up-to-date list of all the schedule bins (currently these are listed
in section~E3).%%%
\footnote{%%%
	 Note that a few schedule bins (notably \texttt{STARTUP},
	 \texttt{RECOVER\_PARAMETERS}, and \texttt{SHUTDOWN}) have
	 special semantics; much of the description here doesn't
	 apply to them.  Unless you really know what you're doing,
	 you should probably avoid scheduling routines in these
	 bins; instead use the \texttt{WRAGH}, \texttt{BASEGRID},
	 and \texttt{TERMINATE} schedule bins, respectively.
	 }%%%

There are two major pieces of software involved in scheduling:
\begin{itemize}
\item	The Cactus flesh.%%%
\footnote{%%%
	 Strictly speaking, what we're calling the ``flesh'' is
	 the combination of what's done by the CST when configuring
	 Cactus, and by the actual Cactus flesh when Cactus runs.
	 But this distinction isn't important here, so for simplicity
	 we just refer to the ``flesh''.
	 }%%%
{}	The flesh knows about everything in \verb|schedule.ccl| files,
	and handles sorting scheduled routines into an order which is
	consistent with the \verb|BEFORE| and \verb|AFTER| clauses in
	all the schedule groups.  The flesh also handles repeatedly
	calling scheduled routines which are scheduled with a
	\verb|WHILE| clause.
        In addition, the flesh determines when storage is turned
        on/off for grid scalars, functions, and arrays and when
        grid arrays and functions are synchronised,
        based on the {\tt STORAGE:} and {\tt SYNC:} statements in
        schedule blocks.

        The flesh does \emph{not} know anything
	about the spatial grid or grids, or how grid functions are
	stored in memory or distributed across processors.
\item	The driver, typically \thorn{PUGH} or \thorn{Carpet}.
	The driver defines the set of allowed schedule bins.
	The driver knows about the grid or grids, and how grid functions
	are stored in memory, distributed across processors, and
        synchronised.

	The driver does \emph{not} know what's in \verb|schedule.ccl| files.
\end{itemize}

The basic flow of control in Cactus is that the flesh starts up, does
some initialization, then calls the driver.  The driver does some
more initialization, then sequences through the schedule bins; for
each one it calls back into the flesh to have the flesh call all the
scheduled routines in that bin in the correct order.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{\thorn{PUGH} Scheduling}

When using the \thorn{PUGH} unigrid driver, the scheduling process
is pretty simple, and is shown in figure~\ref{fig-PUGH-schedule}.
Nowdays most evolutions use \thorn{MoL}; all the \thorn{MoL} evolution
happens inside the \verb|EVOL| schedule bin.

%%%%%%%%%%
\begin{figure}[bp]
\begin{center}
\fbox{\begin{minipage}[t]{\textwidth}
RECOVER\_PARAMETERS\\
STARTUP\\
WRAGH\\
PARAMCHECK\\
BASEGRID
\end{minipage}}
\\
\fbox{\begin{minipage}[t]{\textwidth}
Recover? (yes/no)
\\
\fbox{\begin{minipage}[t]{0.475\textwidth}
INITIAL\\
POSTINITIAL\\
POSTPOSTINITIAL\\
POSTSTEP
\end{minipage}}
\fbox{\begin{minipage}[t]{0.475\textwidth}
RECOVER\_VARIABLES\\
POST\_RECOVER\_VARIABLES
\end{minipage}}
\end{minipage}}
\\
\fbox{\begin{minipage}[t]{\textwidth}
CPINITIAL\\
ANALYSIS\\
OutputGH
\end{minipage}}
\\
\fbox{\begin{minipage}[t]{0.1\textwidth}
main loop\\
over\\
time steps
\end{minipage}
\fbox{\begin{minipage}[t]{0.87\textwidth}
Advance time\\
PRESTEP\\
EVOL (includes all of \texttt{MoL})\\
POSTSTEP\\
CHECKPOINT\\
ANALYSIS\\
OutputGH
\end{minipage}}}
\\
\fbox{\begin{minipage}[t]{\textwidth}
TERMINATE\\
SHUTDOWN
\end{minipage}}
\end{center}
\caption[The \thorn{PUGH} schedule]
	{
	\label{fig-PUGH-schedule}
	This figure shows the order in which \thorn{PUGH}
	sequences through the shedule bins.
	}
\end{figure}
%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{\thorn{Carpet} Scheduling}

With \thorn{Carpet} the scheduling process is much more complicated,
because there are (in general) many different grids, and the various
actions on the different grids have to be carefully coordinated to
obtain accurate results.  Erik Schnetter, Scott Hawley, and Ian Hawke
give a nice general description of Carpet in their
paper~\cite{Schnetter-etal-03b}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The Berger-Oliger Algorithm}
\label{sect-Berger-Oliger-algorithm}

The basic idea underlying \thorn{Carpet} is \emph{mesh refinement}:
use small high-resolution grids in those parts of our problem domain
where they're needed, and use lower resolution elsewhere.  The goal
is to approximate the accuracy of using the finest grid spacing
everywhere, while being vastly more efficient.  The basic algorithm
Carpet uses to do this was first published by Marhsa Berger and
Joseph Oliger~\cite{Berger-1982,Berger84,Berger86,Berger89,Berger91}.

The Berger-Oliger algorithm uses locally-uniform grids.  When the grid
resolution needs to be changed, it's changed by a fixed (integer)
refinement factor, typically a factor of~2.  Fine grids overlap
coarser ones.%%%
\footnote{%%%
	 One could imagine omitting those coarse grid
	 points where there is also a finer grid, but the
	 cost saving would be small, and the bookkeeping
	 quite messy, so it's not worth doing this.
	 (If you want to try, Carpet does support this;
	 it is only necessary to choose a grid structure
	 that has a ``hole'' in the coarse grid.)
	 }%%%
{}  The key to the Berger-Oliger algorithm is that, when doing the time
evolution, in each time step coarse grids are stepped first, and their
values are then interpolated (in space and/or time) as necessary to
provide boundary conditions for fine grids.  This process is illustrated
in figure~\ref{fig-Berger-Oliger-algorithm}.

Notice that after each fine grid has taken enough time steps to be
at the same time level as next coarser grid, the fine-grid values at
points where there is a coarse-grid point are copied (``injected'')
back to the coarse grid.  This keeps the coarse-grid evolution from
gradually drifting away from the (more accurate) fine-grid evolution.

%%%%%%%%%%
\begin{figure}[bp]
\begin{center}
\vspace{35mm}
This figure doesn't exist yet. :(
\vspace{35mm}
\end{center}
\caption[The Berger-Oliger Algorithm]
	{
	This figure shows an example of the sequence of operations
	for taking a single coarse-grid time step using the Berger-Oliger
	mesh-refinement algorithm.
	There are 3~grids, a coarse grid (shown on the left),
	a medium grid (shown in the middle), and a fine grid
	(shown on the right).
	}
\label{fig-Berger-Oliger-algorithm}
\end{figure}
%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Grid Attributes}

In \thorn{Carpet}, a local grid (a ``cuboid'' that has a uniform spacing
in each axis, and lives on a single processor) has a number of attributes:
\begin{description}
\item[\texttt{mglevel}]%%%
\mbox{}\\
	This is an integer specifying a ``convergence level''
	in the sense of ``convergence testing''.  Convergence levels
	are numbered from~0 (the lowest-resolution simulation)
	up up to some maximum value ($\ge 0$) for the highest-resolution
	simulation.  It's important to realise that in this context
	``resolution'' refers to the entire ensemble of grids at
	at different refinement levels in the Berger-Oliger algorithm.
	That is, incrementing \texttt{mglevel} means coarsening
	\emph{every} grid in the Berger-Oliger algorithm by
	(typically) a factor of~2.

	Using convergence levels, you can run several simulations
	with different resolutions concurrently.  This might be useful
	in a multigrid solver and/or for a ``shadow hierarchy'' of
	grids for estimating the local accuracy of an evolution
	(FIXME: REFERENCE FOR SHADOW HIERARCHY).

	At present convergence levels aren't used, so \texttt{mglevel}
	is always set to~0.
\item[\texttt{reflevel}]%%%
\mbox{}\\
	This is an integer specifing the grid's ``refinement level''
	in the Berger-Oliger algorithm (at this convergence level).
	Refinement levels are numbered from~0 (the coarsest or ``base''
	grid) up to some maximum value ($\ge 0$) for the finest grid.
\item[\texttt{map}]
\mbox{}\\
	This is an integer ($\ge 0$) specifying the ``map'' (grid patch)
	at this convergence level and refinement level.%%%
\footnote{%%%
	 The terms ``map'' and ``patch'' mean exactly the same
	 thing.  Carpet originally used the term ``map'', but
	 recently ``patch'' has become more common.  As a rule of
	 thumb, the thorns in the \arrangement{Carpet} arrangement
	 generally use ``map'', but other infrastructure thorns
	 (like \thorn{MultiPatch} and \thorn{GZPatchSystem})
	 generally use ``patch''.
	 }%%%
{}	This will always be~0 unless you're doing a multipatch simulation.
\item[\texttt{component}]
\mbox{}\\
	This is an integer ($\ge 0$) specifying one of the local
	grids in this map/patch.  By definition, a given local grid
	lives on a single processor; there may be multiple local grids
	on a single processor.
\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Modes}

When looping over grids, Carpet has a standard order to loop over
the attributes described in the previous section.  This is shown in
figure~\ref{fig-Carpet-loops-and-modes}.  Corresponding to this,
Carpet defines a set of ``modes'', which correspond to the depth in this
set of nested loops.  In more detail, the modes are as follows:
\begin{description}
\item[meta mode]%%%
\mbox{}\\
	In meta mode Carpet is logically outside its loops over
	convergence levels, refinement levels, maps/patches, and
	components.  Therefore, \emph{none} of \texttt{mglevel},
	\texttt{reflevel}, \texttt{map}, or \texttt{component} are defined.
\item[global mode]%%%
\mbox{}\\
	In global mode Carpet is logically inside its loop over
 	convergence levels, but outside its loops over refinement levels,
	maps/patches, and components.  Therefore, \texttt{mglevel}
	is defined, but \texttt{reflevel}, \texttt{map}, and
	\texttt{component} aren't defined.
\item[level mode]%%%
\mbox{}\\
	In level mode Carpet is logically inside its loops over
	convergence levels and refinement levels, but outside its
	loops over maps/patches and components.  Therefore,
	\texttt{mglevel} and \texttt{reflevel} are defined,
	but \texttt{map} and \texttt{component} are not defined.
\item[singlemap mode]%%%
\mbox{}\\
	In singlemap mode Carpet is logically inside its loops over
	convergence levels, refinement levels, and maps/patches, but
	outside its loop over components.  Therefore, \texttt{mglevel},
	\texttt{reflevel}, and \texttt{map} are defined,
	but \texttt{component} is not defined.
\item[local mode]%%%
\mbox{}\\
	In local mode Carpet is logically inside its loops over
	convergence levels, refinement levels, maps/patches, and
	components.  Therefore, all of \texttt{mglevel},
	\texttt{reflevel}, \texttt{map}, and \texttt{component}
	are defined.
\end{description}

%%%%%%%%%%
\begin{figure}[bp]
\begin{verbatim}
#
# meta mode
#
begin loop over mglevel (convergence level)
        #
        # global mode
        #
        begin loop over reflevel (refinement level)
                #
                # level mode
                #
                begin loop over map
                        #
                        # singlemap mode
                        #
                        begin loop over component
                                #
                                # local mode
                                #
                        end loop over component
                        #
                        # singlemap mode
                        #
                end loop over map
                #
                # level mode
                #
        end loop over reflevel
        #
        # global mode
        #
end loop over mglevel
#
# meta mode
#
\end{verbatim}
\caption[Carpet Loops and Modes]
	{
	This figure shows how Carpet loops over the various
	attributes of local grids, and how the Carpet modes
	correspond to depth in this set of nested loops.
	}
\label{fig-Carpet-loops-and-modes}
\end{figure}
%%%%%%%%%%

When you schedule a routine (by writing a schedule block in a
\verb|schedule.ccl| file), you specify what mode it should run in.
If you don't specify a mode, the default is local.  You can also
specify various schedule options; some of these are used in the
Carpet scheduling algorithms discussed in
section~\ref{sect-Carpet-scheduling-pipeline}.

Since convergence levels aren't used at present, for most practical
purposes meta mode is identical to global mode.  Similarly, unless
you're doing multipatch simulations, singlemap mode is identical to
level mode.

Table~\ref{tab-what-Carpet-defines-in-each-mode} shows which of the
grid attributes and predefined Cactus macros and variables are defined
in each mode.  [Notice that for backwards compatability and simpler
program in the most common (single-patch) case, some variables which
are logically only defined in singlemap and local modes, are ``extended''
to also be defined in level mode in single-patch simulations.]

%%%%%%%%%%
\begin{table}[bp]
\def\yes{$\surd$}
\def\no{$\times$}
\begin{center}
\begin{tabular}{|lccccc|}
\hline %----------------------------------------------------------------
				&meta	&global	&level	&singlemap
								&local	\\
\hline %----------------------------------------------------------------
\texttt{mglevel}		&\no	&\yes	&\yes	&\yes	&\yes	\\
\texttt{reflevel}		&\no	&\no	&\yes	&\yes	&\yes	\\
\texttt{map}			&\no	&\no	&\no	&\yes	&\yes	\\
\texttt{component}		&\no	&\no	&\no	&\no	&\yes	\\
\hline %----------------------------------------------------------------
\texttt{CCTK\_ORIGIN\_SPACE}	&\no	&\no	&\yes{} if single-patch
							&\yes	&\yes	\\
\texttt{CCTK\_DELTA\_SPACE}	&\no	&\no	&\yes{} if single-patch
							&\yes	&\yes	\\
\texttt{CCTK\_DELTA\_TIME}	&\no	&\no	&\yes
							&\yes	&\yes	\\
\texttt{cctk\_origin\_space}	&\no	&\yes (coarse)
						&\yes (coarse) if single-patch
							&\yes (coarse)
								&\yes (coarse)
									\\
\texttt{cctk\_delta\_space}	&\no	&\yes (coarse)
						&\yes (coarse) if single-patch
							&\yes (coarse)
								&\yes (coarse)
									\\
\texttt{cctk\_delta\_time}	&\no	&\yes (coarse)
						&\yes (coarse)
							&\yes (coarse)
								&\yes (coarse)
									\\
\hline %----------------------------------------------------------------
grid scalars			&\no	&\yes	&\yes	&\yes	&\yes	\\
grid arrays			&\no	&\yes	&\yes	&\yes	&\yes	\\
grid functions			&\no	&\no	&\no	&\no	&\yes	\\
\hline %----------------------------------------------------------------
\end{tabular}
\end{center}
\caption[What Carpet Defines in Each Mode]
	{
	This table shows what grid attributes and Cactus variables
	are defined in each Carpet mode.				\\
	``\yes{} if single-patch'' means that the corresponding macros
	are defined if this is a single-patch simulation, but not if
	this is a multipatch simulation.				\\
	``\yes (coarse)'' means that the corresponding variables are
	defined, and that they describe the \emph{coarsest} refinement
	level.								%%%\\
	}
\label{tab-what-Carpet-defines-in-each-mode}
\end{table}
%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%

\subsubsection{What to Do in Each Mode}

As can be seen from table~\ref{tab-what-Carpet-defines-in-each-mode},
grid functions are defined \emph{only} in local mode.  Since most physics
code needs to manipulate grid functions, it therefore must run in local
mode.  (That's why local is the default mode in a \verb|schedule.ccl|
schedule block.)

However, in general code scheduled in local mode will run multiple times
(because it's nested inside loops over \texttt{mglevel}, \texttt{reflevel},
\texttt{map}, and \texttt{component}).  Sometimes you don't want this.
For example, you may want to open or close an output file, or initialize
some global property of your simulation.  Meta or global modes (recall
that they're identical for most purposes) are good for this kind of thing.

Level mode is in some sense the natural mode for Berger-Oliger mesh
refinement.  That is, the Berger-Oliger algorithm is naturally written
in terms of computations done in level mode.  Level mode is convenient
for things like convergence tests that depend on the grid spacing.

Singelmap mode is mostly useful (and differs from level mode) only if
you're doing multipatch simulations.

Synchronization and turning storage on/off happen in level mode.%%%
\footnote{%%%
	 For backwards compatibility, these operations are
	 also allowed (with a warning message printed) in
	 singlemap and local modes if there is only one
	 component per processor.
	 }%%%
{}  (At any time only the ``current'' refinement level has storage
turned on.)  Boundary conditions must be selected (in the sense of
thorn \thorn{Boundary}) in level mode.  Cactus output must be done
in level mode.

Reduction/interpolation of grid arrays and/or grid functions may be
done in either level mode (applying only to that refinement level),
or in global mode (applying to all refinement levels).  

%%%%%%%%%%%%%%%%%%%%

\subsubsection{Querying and Changing Modes}

Normally, Carpet changes between modes automatically.  But for
advanced programming, sometimes you need to do this explicitly.
Carpet has various functions to query what mode you're in, and
functions and macros to change modes.  These are all defined in
\verb|Carpet/Carpet/src/modes.hh|, and are only usable from
\Cplusplus{} code.

To use any of these facilities, put the line
``\verb|uses include: carpet.hh|'' in your \verb|interface.ccl|,
then include \verb|"carpet.hh"| in your \Cplusplus{} source code
(this must come \emph{after} including \verb|"cctk.h"|).

To query the current mode, just use any of the Boolean predicates
\verb|is_meta_mode()|, \verb|is_global_mode()|, \dots, \verb|is_local_mode()|.
A common usage of these is in assertions, to verify that the mode
is what it should be, \eg{}
\begin{verbatim}
#include <cassert>

#include "cctk.h"
#include "carpet.hh"

void my_function(...)
{
// make sure we're in level mode
assert(Carpet::is_level_mode());
...
}
\end{verbatim}

For changing modes, the macros defined in \verb|carpet.hh| provide
a higher-level interface, and automagically enforce proper nesting
of the modes (in the sense of figure~\ref{fig-Carpet-loops-and-modes}).
The mode-changing functions provide a lower-level interface, and
do not enforce proper nesting, but they can be used with explicit
\verb|Carpet::| namespace qualifications (\ie, without having to import
the entire \verb|Carpet::| namespace).

The macros set the \verb|cctkGH| entries as appropriate.  However, they
don't define or undefine grid functions, grid variables, or any \verb|cctk_|*
variables; to do this, you need to place a \verb|DECLARE_CCTK_ARGUMENTS|
inside the macro loop.

The most commonly-used macros are probably the looping ones, which
come in pairs \verb|BEGIN_|*\verb|_LOOP| and \verb|END_|*\verb|_LOOP|.
These let you move one level deeper in the loop hierarchy.
There are also \verb|ENTER_|*\verb|_MODE| and \verb|LEAVE_|*\verb|_MODE|
macros, which let you escape out of a level (or even levels!) in the
loop hierarchy.

Some of these macros also require a \verb|grouptype| argument; this
is either \verb|CCTK_GF| or \verb|CCTK_ARRAY| to specify whether you
are looping over grid function components or grid array components.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The \thorn{Carpet} Scheduling Pipeline}
\label{sect-Carpet-scheduling-pipeline}

It's useful to think of the overall Carpet scheduling process as a
pipeline (in the Unix sense) of 3~subprocesses:
\begin{enumerate}
\item	First, Carpet runs the Berger-Oliger mesh refinement algorithm,
	as described in section~\ref{sect-Berger-Oliger-algorithm}.
	Figure~\ref{fig-Carpet-Berger-Oliger-summary} gives a summary
	of how Carpet uses the Berger-Oliger algorithm to step through
	scheule groups and refinement levels.
	 Figure~\ref{fig-Carpet-Berger-Oliger-details} describes this
	in (much!) more detail.

	Notice that while some loops in the algorithm traverse the
	different refinement levels from coarse grids to fine grids
	as described above, other loops traverse the levels in the
	opposite direction.  This is done to make boundary conditions
	and symmetries work better.

	Logically, the output of Carpet's Berger-Oliger algorithm
	is a sequence of tuples:
	$$
	(\textrm{schedule bin},\,\,\texttt{mglevel},\,\,\texttt{reflevel})
	$$
	Since these tuples have definite \texttt{mglevel}
	and \texttt{reflevel} values, but no \texttt{map} or
	\texttt{component} values, they're semantically in level
	mode.
\item	Next, for each schedule bin output by the previous
	``pipeline stage'', the Cactus flesh sorts all the
	scheduled routines in that bin into some order which is
	consistent with the combination of all active thorns'
	\verb|schedule.ccl| files.%%%
\footnote{%%%
	 Strictly speaking, ``scheduled routine'' here also
	 includes entry to and exit from a schedule group,
	 since storage may need to be turned on or off when
	 these events happen.
	 }%%%
{}	This is where \verb|BEFORE|,
	\verb|AFTER|, and \verb|WHILE| clauses in \verb|schedule.ccl|
	files are interpreted.

	Logically, the output of this pipeline stage is a sequence
	of tuples:
	$$
	(\textrm{scheduled routine},\,\,
	 \textrm{schedule mode},\,\, \textrm{schedule options},\,\,
	 \texttt{mglevel},\,\, \texttt{reflevel})
	$$
	For this ``pipeline stage'', the schedule mode and options
	are just uninterpreted tokens to be passed along to the next
	stage --- there's no knowledge (yet) of what they mean.
\item	Finally, Carpet applies the schedule options for each
	scheduled routine, in the manner shown in
	figure~\ref{fig-how-Carpet-uses-modes}.  This generates
	a sequence of calls on scheduled routines.  Some calls
	may be performed in a loop (\eg{} for local mode), while
	others may be skipped (\eg{} for global mode).
\end{enumerate}

%%%%%%%%%%
\begin{figure}[bp]
\begin{center}
\fbox{\begin{minipage}[t]{\textwidth}
RECOVER\_PARAMETERS\\
STARTUP\\
WRAGH\\
PARAMCHECK
\end{minipage}}
\\
\fbox{\begin{minipage}[t]{\textwidth}
Recover? (yes/no)
\\
\fbox{\begin{minipage}[t]{0.47\textwidth}
PREREGRIDINITIAL\\
const bool did\_regrid = Regrid()\\
if (did\_regrid) POSTREGRIDINITIAL
\end{minipage}}
\fbox{\begin{minipage}[t]{0.47\textwidth}
Recover grid structure
\end{minipage}}\\
\fbox{\begin{minipage}[t]{0.1\textwidth}
initial\\
loop
\end{minipage}
\fbox{\begin{minipage}[t]{0.345\textwidth}
BASEGRID\\
INITIAL\\
POSTINITIAL\\
$\longrightarrow$ Recurse\\
Restrict\\
POSTRESTRICTINITIAL\\
POSTPOSTINITIAL\\
POSTSTEP
\end{minipage}}}
\fbox{\begin{minipage}[t]{0.1\textwidth}
recover\\
loop
\end{minipage}
\fbox{\begin{minipage}[t]{0.345\textwidth}
BASEGRID\\
RECOVER\_VARIABLES\\
POST\_RECOVER\_VARIABLES
$\longrightarrow$ Recurse
\end{minipage}}}
\\
\fbox{\begin{minipage}[t]{0.47\textwidth}
3 Time Level Initialisation
\end{minipage}}
\end{minipage}}
\\
\fbox{\begin{minipage}[t]{0.1\textwidth}
initial\\
loop
\end{minipage}
\fbox{\begin{minipage}[t]{0.87\textwidth}
$\longrightarrow$ Recurse\\
CPINITIAL\\
ANALYSIS\\
OutputGH
\end{minipage}}}
\\
\fbox{\begin{minipage}[t]{0.1\textwidth}
main loop\\
over\\
time steps
\end{minipage}
\fbox{\begin{minipage}[t]{0.875\textwidth}
PREREGRID\\
const bool did\_regrid = Regrid()\\
if (did\_regrid) POSTREGRID\\
Advance time\\
PRESTEP\\
EVOL\\
$\longrightarrow$ Recurse\\
Restrict\\
POSTRESTRICT\\
POSTSTEP\\
CHECKPOINT\\
ANALYSIS\\
OutputGH
\end{minipage}}}
\\
\fbox{\begin{minipage}[t]{0.1\textwidth}
shutdown\\
loop
\end{minipage}
\fbox{\begin{minipage}[t]{0.87\textwidth}
$\longrightarrow$ Recurse\\
TERMINATE
\end{minipage}}}
\\
\fbox{\begin{minipage}[t]{\textwidth}
SHUTDOWN
\end{minipage}}
\end{center}
\caption[Summary of the \thorn{Carpet} schedule]
	{
	This figure gives an outline of how Carpet uses the
	Berger-Oliger algorithm to sequence through the
	schedule bins and grids.
	See figure~\protect\ref{fig-Carpet-Berger-Oliger-details}
	for a (much!) more detailed description of the algorithm.	\\
	In general, all the loops are traversed in the order
	from coarse grids to fine grids.
	FIXME: ARE THERE EXCPETIONS TO THIS RULE
	(AMONG THE LOOPS SHOWN IN THIS FIGURE)?
	}
\label{fig-Carpet-Berger-Oliger-summary}
\end{figure}
%%%%%%%%%%

%%%%%%%%%%
\begin{figure}[bp]
\begin{center}
\fbox{
 \begin{minipage}[t]{\textwidth}
  RECOVER\_PARAMETERS\\
  STARTUP
 \end{minipage}
}
\\
%%%%%
\fbox{
 \begin{minipage}[t]{\textwidth}
  \begin{minipage}[c]{22ex}
   \tt
   loop $\uparrow$ mglevels
  \end{minipage}
%  
  \fbox{
   \begin{minipage}[c]{0.78\textwidth}
    WRAGH\\
    PARAMCHECK
   \end{minipage}
  }
 \end{minipage}
}
\\ 
%%%%%
\fbox{
 \begin{minipage}[t]{\textwidth}
  Recover?\hspace*{0.14\textwidth}no\hspace*{0.47\textwidth}yes
\\
  \fbox{
   \begin{minipage}[t]{0.47\textwidth}
    \fbox{
     \begin{minipage}[c]{12ex}
      \tt
      loop $\uparrow$\\
      reflevels
     \end{minipage}
%   
     \begin{minipage}[c]{0.73\textwidth}
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mg\-levels
       \end{minipage}
%
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         BASEGRID\\
         INITIAL\\
         POSTINITIAL\\
        \end{minipage}
       }
      }
\\
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mg\-levels
       \end{minipage}
%    
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         PREREGRIDINITIAL
        \end{minipage}
       }
      }
\\
      \fbox{
       \begin{minipage}[c]{0.94\textwidth}
        const bool did\_regrid = Regrid()
       \end{minipage}
      }
\\
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mg\-levels
       \end{minipage}
%
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         if (did\_regrid) POSTREGRIDINITIAL
        \end{minipage}
       }
      }
     \end{minipage}
    }
\\
    \fbox{
     \begin{minipage}[c]{22ex}
      \tt
      loop $\downarrow$ reflevels\\
      \hspace*{2ex}loop $\uparrow$ mglevels
     \end{minipage}
%
     \fbox{
      \begin{minipage}[c]{0.49\textwidth}
       Restrict
      \end{minipage}
     }
    }
\\
    \fbox{
     \begin{minipage}[c]{22ex}
      \tt
      loop $\uparrow$ reflevels\\
      \hspace*{2ex}loop $\uparrow$ mglevels
     \end{minipage}
%
     \fbox{
      \begin{minipage}[c]{0.49\textwidth}
       POSTRESTRICTINITIAL\\
       POSTPOSTINITIAL
       POSTSTEP
      \end{minipage}
     }
    }
\\
    \fbox{
     \begin{minipage}[c]{0.95\textwidth}
      3 Time Level Initialisation
     \end{minipage}
    }
   \end{minipage}
  }
%
  \fbox{
   \begin{minipage}[t]{0.47\textwidth}
    \fbox{
     \begin{minipage}[c]{12ex}
      \tt
      loop $\uparrow$\\
      reflevels
     \end{minipage}
%
     \begin{minipage}[c]{0.73\textwidth}
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mglevels
       \end{minipage}
%
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         BASEGRID\\
         RECOVER\_VARIABLES
        \end{minipage}
       }
      }
\\
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mglevels
       \end{minipage}
%
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         PREREGRID
        \end{minipage}
       }
      }
\\
      \fbox{
       \begin{minipage}[c]{0.94\textwidth}
        const bool did\_regrid = Regrid()
       \end{minipage}
      }
\\
      \fbox{
       \begin{minipage}[c]{10ex}
        \tt
        loop $\uparrow$ mglevels
       \end{minipage}
%
       \fbox{
        \begin{minipage}[c]{0.6\textwidth}
         if (did\_regrid) POSTREGRID
        \end{minipage}
       }
      }
     \end{minipage}
    }
\\
    \fbox{
     \begin{minipage}[c]{22ex}
      \tt
      loop $\uparrow$ reflevels\\
      \hspace*{2ex}loop $\uparrow$ mglevels
     \end{minipage}
%
     \fbox{
      \begin{minipage}[c]{0.49\textwidth}
       POST\_RECOVER\_VARIABLES
%      $\longrightarrow$ Recurse
      \end{minipage}
     }
    }
   \end{minipage}
  }
 \end{minipage}
}
\\
%%%%%%
\fbox{
 \begin{minipage}[t]{\textwidth}
  \begin{minipage}[c]{22ex}
   \tt
   loop $\uparrow$ reflevels\\
   \hspace*{2ex}loop $\uparrow$ mglevels
  \end{minipage}
%
  \fbox{
   \begin{minipage}[c]{0.78\textwidth}
    CPINITIAL\\
    ANALYSIS\\
    OutputGH
   \end{minipage}
  }
 \end{minipage}
}
\\
%%%%%%
\fbox{
 \begin{minipage}[t]{\textwidth}
  \begin{minipage}[c]{0.1\textwidth}
   main loop\\
   over\\
   time steps
  \end{minipage}
%
  \begin{minipage}[c]{1.58\textwidth}
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\uparrow$ reflevels\\
     \hspace*{2ex}loop $\downarrow$ mglevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      PREREGRID
     \end{minipage}
    }
   }
\\
%
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\uparrow$ reflevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      const bool did\_regrid = Regrid()
     \end{minipage}
    }
   }
\\
%
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\uparrow$ reflevels\\
     \hspace*{2ex}loop $\downarrow$ mglevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      if (did\_regrid) POSTREGRID
     \end{minipage}
    }
   }
\\
%
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\downarrow$ mglevels\\
     \hspace*{2ex}loop $\uparrow$ reflevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      Advance time\\
      PRESTEP\\
      EVOL (includes all of \texttt{MoL})
     \end{minipage}
    }
   }
\\
%
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\downarrow$ mglevels\\
     \hspace*{2ex}loop $\downarrow$ reflevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      Restrict
     \end{minipage}
    }
   }
\\
%
   \fbox{
    \begin{minipage}[c]{22ex}
     \tt
     loop $\downarrow$ mglevels\\
     \hspace*{2ex}loop $\uparrow$ reflevels
    \end{minipage}
%
    \fbox{
     \begin{minipage}[c]{0.41\textwidth}
      POSTRESTRICT\\
      POSTSTEP\\
      CHECKPOINT\\
      ANALYSIS\\
      OutputGH
     \end{minipage}
    }
   }
  \end{minipage}
 \end{minipage}
}
\\
%%%%%%
\fbox{
 \begin{minipage}[c]{\textwidth}
  \begin{minipage}[c]{22ex}
   \tt
   loop $\downarrow$ reflevels\\
   \hspace*{2ex}loop $\downarrow$ mglevels
  \end{minipage}
%
  \fbox{
   \begin{minipage}[c]{0.78\textwidth}
%      $\longrightarrow$ Recurse\\
    TERMINATE
   \end{minipage}
  }
 \end{minipage}
}
\\
%%%%%%
\fbox{
 \begin{minipage}[c]{\textwidth}
  \begin{minipage}[c]{22ex}
   \tt
   loop $\downarrow$ mglevels
  \end{minipage}
%
  \fbox{
   \begin{minipage}[c]{0.78\textwidth}
    SHUTDOWN
   \end{minipage}
  }
 \end{minipage}
}
\end{center}
\caption[Detailed View of the \thorn{Carpet} Berger-Oliger Algorithm]
	{
	This figure gives a detailed description of how Carpet
		uses the Berger-Oliger algorithm
		to sequence through the schedule bins and grids
		(see figure~\protect\ref{fig-Carpet-Berger-Oliger-summary}
		 for a summary of the algorithm).			\\
	$\uparrow$ loops iterate upwards
		on \texttt{mglevel} or \texttt{reflevel},
		\ie{} (for \texttt{reflevel})
		from coarse grids to fine grids.			\\
	$\downarrow$ loops iterate downwards
		on \texttt{mglevel} or \texttt{reflevel},
		\ie{} (for \texttt{reflevel})
		from fine grids to coarse grids.			\\
	At present \texttt{mglevels} aren't used, \ie{} the
		\texttt{mglevels} loops have only a single iteration.	%%%\\
%
\todo{ES: The postregrid bin loops now over all time levels.  The
  initial bin can also do this if init\_all\_timelevels is selected.}
%
\todo{ES: Some of these loops may have change recently.  Check.}
%
	}
\label{fig-Carpet-Berger-Oliger-details}
\end{figure}
%%%%%%%%%%

%%%%%%%%%%
\begin{figure}
\def\B#1{\textbf{#1}}
\def\tab{\phantom{\texttt{~~~~~~~~}}}
\begin{tabbing}
\B{procedure} \verb|Carpet_use_modes|\B{(}\=%%%
        \B{function} \verb|scheduled_routine|,				\\
        \>\B{string} \verb|schedule_mode|,				\\
        \>\B{string} \verb|schedule_options|,				\\
        \>\B{int} \texttt{mglevel},
        \B{int} \texttt{reflevel}\B{)}					\\
\B{select} \B{case} \verb|schedule_mode|				\\
\B{case} META\B{:}							\\
\tab    \=\B{if} \=\B{(}\verb|do_global_mode_routines_now()|
                        \textbf{and} this is the coarsest convergence level)
									\\
        \>        \>\B{then}
                        call \verb|scheduled_routine()| in META mode	\\
\B{case} GLOBAL\B{:}							\\
\tab    \=\B{if} \=\B{(}\verb|do_global_mode_routines_now()|)		\\
        \>       \>\B{then}
			call \verb|scheduled_routine(mglevel)|
			in GLOBAL mode					\\
\B{case} LEVEL\B{:}							\\
	\>call \verb|scheduled_routine(mglevel, reflevel)|
	in LEVEL mode							\\
\B{case} SINGLEMAP\B{:}							\\
	\>\B{begin} loop over all maps \verb|m|
		  in (\verb|mglevel, reflevel|)				\\
	\>\tab	\=call \verb|scheduled_routine(mglevel, reflevel, m)|
		  in SINGLEMAP mode					\\
	\>\B{end} loop over map \verb|m|			\\
\B{case} LOCAL\B{:}							\\
	\>\B{begin} loop over all maps \verb|m|
		  in (\verb|mglevel, reflevel|)				\\
	\>\tab	\=\B{begin} loop over all components \verb|c|
			  in (\verb|mglevel, reflevel, m|)		\\
	\>	\>\tab	\=call
			  \verb|scheduled_routine(mglevel, reflevel, m, c)|
			  in LOCAL mode					\\
	\>	\>\B{end} loop over components \verb|c|	\\
	\>\B{end} loop over map \verb|m|			\\
\B{end} \B{select} \B{case}						\\
\B{end} \B{procedure}							%%%\\
%
\end{tabbing}
\begin{tabbing}
\B{Boolean} \B{function} \verb|do_global_mode_routines_now()|		\\
FIXME: \=THIS IS COMPLICATED
         AND VARIES FROM ONE SCHEDULE BIN TO ANOTHER,			\\
       \>BUT IT IS USUALLY A TEST OF THE FORM				\\
       \>\verb|reflevel == |$R$						\\
       \>where $R$ is either the coarsest or the finest \verb|reflevel|	\\
\B{end} \B{function}							%%%\\
\end{tabbing}
%
In \verb|Carpet_use_modes()|, suppose \verb|schedule_mode| is X.
Then if \verb|schedule_options| is ``loop-Y'', replace
\begin{verbatim}
call scheduled_routine(X_arguments) in X mode
\end{verbatim}
by
\begin{verbatim}
loop over all ... in ...
        loop over all ... in ...
                call scheduled_routine(X_arguments, ...) in Y mode
        end loop over ...
end loop over ...
\end{verbatim}
with the appropriate number and kind of loops to get from X mode to Y mode,
and with the corresponding set of extra arguments to the scheduled routine.
[If X is LEVEL, SINGLEMAP, or LOCAL, then this gives exactly the same
result as just scheduling \verb|scheduled_routine| in Y~mode, so the
``loop-Y'' schedule option is only interesting (gives new semantics)
if X is META or GLOBAL.]
\caption[How Carpet uses Modes when Calling Scheduled Routines]
	{
	This figure shows how Carpet uses modes when calling
	scheduled routines.  The input to this algorithm is the
	sequence of
	$(\textrm{scheduled routine},\,\,
	  \textrm{schedule mode},\,\, \textrm{schedule options},\,\,
	  \texttt{mglevel},\,\, \texttt{reflevel})$
	tuples produced as Carpet steps through the Berger-Oliger
	algorithm (figures~\protect\ref{fig-Carpet-Berger-Oliger-summary}
	and~\protect\ref{fig-Carpet-Berger-Oliger-details}).
	}
\label{fig-how-Carpet-uses-modes}
\end{figure}
%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Examples, Tips, and Tricks}

This section needs more writing. :(

\subsubsection{Example 1}

{\bf Problem}

How to perform a global operation (e.g.\ maximum reduction) once at \verb|CCTK_POSTINITIAL| (call the
routine which performs this global operation routine A), before another routine, B, which is scheduled in local mode. As a further
constraint, suppose that the scheduling of thorn B cannot be modified.\\

\noindent {\bf A solution}

Use the Carpet namespace functions to manually change mode, before executing the global computation,
and then go back to the original mode. That is, schedule A in local mode \verb|BEFORE| B:

\begin{verbatim}
schedule A  AT CCTK_PostInitial BEFORE B
{
  LANG: C
} "global operation"
\end{verbatim}

where A is the \Cplusplus{} (this is necessary in order to access the carpet namespace variables
and functions which are used in the routine) routine described in Fig.~\ref{fig-example1}

\begin{figure}
\begin{verbatim}
#include "Carpet/Carpet/src/carpet.hh"

void A(CCTK_ARGUMENTS)
{
 DECLARE_CCTK_ARGUMENTS;
 DECLARE_CCTK_PARAMETERS;
 static int flag = true; // flag used to have this routine effectively executed only once

 // Store the present values of the active refinement level, single map and component.
 // Variables from the Carpet namespace.
 int rl = Carpet::reflevel;   
 int singlemap = Carpet::map;
 int comp = Carpet::component;
    
 if (flag)
    {
    // Go to global mode
    // That is:
    // Leave local mode
    assert(Carpet::is_local_mode());
    Carpet::leave_local_mode (cctkGH);

    // Leave singlemap mode
    assert(Carpet::is_singlemap_mode());
    Carpet::leave_singlemap_mode (cctkGH);	    

    // Leave level mode
    assert(Carpet::is_level_mode());
    Carpet::leave_level_mode (cctkGH);	    
		
    assert(Carpet::is_global_mode());
	    
    // Do the global operation
    ...
    // Go back to local mode
	    
    // Enter level mode
    Carpet::enter_level_mode (cctkGH, rl);
    assert(Carpet::is_level_mode());

    // Enter singlemap mode
    Carpet::enter_singlemap_mode (cctkGH, singlemap);
    assert(Carpet::is_singlemap_mode());
	    
    // Enter local mode
    Carpet::enter_local_mode (cctkGH, comp);
    assert(Carpet::is_local_mode());
  }
// After this has run once, set the flag so that this does not run again
flag = false;
     } // end if (flag)
   else
     {
      return;
     }
}
\end{verbatim}
\caption[Example1]
	{
	  Example1: perform a global operation A, before given local routine B, 
	  in the case that the scheduling of thorn B cannot be modified.
	}
\label{fig-example1}
\end{figure}

\begin{figure}
\begin{verbatim}
// import header file exported by Carpet
// This also requires the following line in this thorn's interface.ccl:
//   "using include header: carpet.hh"
#include "carpet.hh"

extern "C" void A(CCTK_ARGUMENTS)
{
  // do nothing if the global mode routine B hasn't been called yet
  // (ie. if not yet on the finest refinement level)
  if (Carpet::reflevel < Carpet::reflevels-1) return;

  // temporarily leave the current scheduling mode
  BEGIN_GLOBAL_MODE(cctkGH) {

    // now loop over all refinement levels and do the local operation
    BEGIN_REFLEVEL_LOOP (cctkGH) {
      BEGIN_MAP_LOOP (cctkGH, CCTK_GF) {
        BEGIN_LOCAL_COMPONENT_LOOP (cctkGH, CCTK_GF) {
  
          // redeclare CCTK arguments which change for each level/map/component
          DECLARE_CCTK_ARGUMENTS;
  
          // Do the local operation
          // (eg. use the integration result to adjust some mask grid function)
          ...
  
        } END_LOCAL_COMPONENT_LOOP;
      } END_MAP_LOOP;
    } END_REFLEVEL_LOOP;

  // switch back to where we came from
  } END_GLOBAL_MODE;

}
\end{verbatim}
\caption[Example2]
  {
    Example2: perform a local operation A on all refinement levels,
    after global mode routine B within the same schedule group G
    (eg. call B to integrate some grid function, then call A to apply the
     integration result to some other grid function).
	  It is assumed that group G is scheduled in INITIAL (where the loop over
    refinement levels is iterated upwards) and the scheduling of routine B
    cannot be modified.
  }
\label{fig-example2}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Other Miscellaneous Stuff}

Erik says:
I am surprised that the \verb|POSTSTEP| loop for the initial data is
fine--to--coarse.  I think people may apply boundary conditions in
this bin\ldots Maybe this loop needs to be reversed?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{alpha}
\bibliography{scheduling}

\end{document}