ImplementingDeviceAdapters.tex

% -*- latex -*-

\chapter{Implementing Device Adapters}
\label{chap:ImplementingDeviceAdapters}

\index{device adapter|(}
\index{device adapter!implementing|(}

VTK-m comes with several implementations of device adapters so that it may
be ported to a variety of platforms. It is also possible to provide new
device adapters to support yet more devices, compilers, and libraries. A
new device adapter provides a tag, a class to manage arrays in the
execution environment, a collection of algorithms that run in the execution
environment, and (optionally) a timer.

Most device adapters are associated with some type of device or library,
and all source code related directly to that device is placed in a
subdirectory of \textfilename{vtkm/cont}. For example, files associated
with CUDA are in \textfilename{vtkm/cont/cuda} and files associated with
the Intel Threading Building Blocks (TBB) are located in
\textfilename{vtkm/cont/tbb}. The documentation here assumes that you are
adding a device adapter to the VTK-m source code and following these file
conventions. However, it is also possible to define a device adapter
outside of the core VTK-m, in which case the file paths might be different.

For the purposes of discussion in this section, we will give a simple
example of implementing a device adapter using the \textcode{std::thread}
class provided by C++11. We will call our device \textcode{Cxx11Thread} and
place it in the directory \textfilename{vtkm/cont/cxx11}.

By convention the implementation of device adapters within VTK-m are
divided into 3 header files with the names
\textfilename{DeviceAdapterTag\textasteriskcentered.h},
\textfilename{ArrayManagerExecution\textasteriskcentered.h} and
\textfilename{DeviceAdapterAlgorithm\textasteriskcentered.h}, which are
hidden in internal directories. The
\textfilename{DeviceAdapter\textasteriskcentered.h} that most code includes
is a trivial header that simply includes these other three files. For our
example \textcode{std::thread} device, we will create the base header at
\textfilename{vtkm/cont/cxx11/DeviceAdapterCxx11Thread.h}. The contents are
the following (with minutia like include guards removed).

\begin{vtkmexample}{Contents of the base header for a device adapter.}
#include <vtkm/cont/cxx11/internal/DeviceAdapterTagCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/ArrayManagerExecutionCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/DeviceAdapterAlgorithmCxx11Thread.h>
\end{vtkmexample}

The reason VTK-m breaks up the code for its device adapters this way is
that there is an interdependence between the implementation of each device
adapter and the mechanism to pick a default device adapter. Breaking up the
device adapter code in this way maintains an acyclic dependence among
header files.

\section{Tag}

\index{device adapter!tag|(}

The device adapter tag, as described in Section~\ref{sec:DeviceAdapterTag}
is a simple empty type that is used as a template parameter to identify the
device adapter. Every device adapter implementation provides one. The
device adapter tag is typically defined in an internal header file with a
prefix of \textfilename{DeviceAdapterTag}.

The device adapter tag should be created with the macro
\vtkmmacro{VTKM\_VALID\_DEVICE\_ADAPTER}. This adapter takes an abbreviated
name that it will append to \textcode{DeviceAdapterTag} to make the tag
structure. It will also create some support classes that allow VTK-m to
introspect the device adapter. The macro also expects a unique integer
identifier that is usually stored in a macro prefixed with
\textcode{VTKM\_DEVICE\_ADAPTER\_}. These identifiers for the device
adapters provided by the core VTK-m are declared in
\vtkmheader{vtkm/cont/internal}{DeviceAdapterTag.h}.

The following example gives the implementation of our custom device
adapter, which by convention would be placed in the
\textfilename{vtkm/cont/cxx11/internal/DeviceAdapterTagCxx11Thread.h}
header file.

\vtkmlisting{Implementation of a device adapter tag.}{DeviceAdapterTagCxx11Thread.h}

\index{device adapter!tag|)}

\section{Array Manager Execution}

\index{device adapter!array manager|(}
\index{array manager execution|(}
\index{execution array manager|(}

VTK-m defines a template named \vtkmcontinternal{ArrayManagerExecution}
that is responsible for allocating memory in the execution environment and
copying data between the control and execution environment. The execution
array manager is typically defined in an internal header file with a prefix
of \textfilename{ArrayManagerExecution}.

\vtkmlisting{Prototype for \protect\vtkmcontinternal{ArrayManagerExecution}.}{ArrayManagerExecutionPrototype.cxx}

A device adapter must provide a partial specialization of
\textidentifier{ArrayManagerExecution} for its device adapter tag. The
implementation for \textidentifier{ArrayManagerExecution} is expected to
manage the resources for a single array. All
\textidentifier{ArrayManagerExecution} specializations must have a
constructor that takes a pointer to a \vtkmcontinternal{Storage} object.
The \textidentifier{ArrayManagerExecution} should store a reference to this
\textidentifier{Storage} object and use it to pass data between control and
execution environments. Additionally,
\textidentifier{ArrayManagerExecution} must provide the following elements.

\begin{description}
\item[\textcode{ValueType}] A \textcode{typedef} of the type for each item
  in the array. This is the same type as the first template argument.
\item[\textcode{PortalType}] The type of an array portal that can be used
  in the execution environment to access the array.
\item[\textcode{PortalConstType}] A read-only (const) version of
  \textcode{PortalType}.
\item[\textcode{GetNumberOfValues}] A method that returns the number of
  values stored in the array. The results are undefined if the data has not
  been loaded or allocated.
\item[\textcode{PrepareForInput}] A method that ensures an array is
  allocated in the execution environment and valid data is there. The
  method takes a \textcode{bool} flag that specifies whether data needs to
  be copied to the execution environment. (If false, then data for this
  array has not changed since the last operation.) The method returns a
  \textcode{PortalConstType} that points to the data.
\item[\textcode{PrepareForInPlace}] A method that ensures an array is
  allocated in the execution environment and valid data is there. The
  method takes a \textcode{bool} flag that specifies whether data needs to
  be copied to the execution environment. (If false, then data for this
  array has not changed since the last operation.) The method returns a
  \textcode{PortalType} that points to the data.
\item[\textcode{PrepareForOutput}] A method that takes an array
  size and allocates an array in the execution environment
  of the specified size. The initial memory may be uninitialized. The
  method returns a \textcode{PortalType} to the data.
\item[\textcode{RetrieveOutputData}] This method takes a storage object,
  allocates memory in the control environment, and copies data from the
  execution environment into it. If the control and execution environments
  share arrays, then this can be a no-operation.
\item[\textcode{CopyInto}] This method takes an STL-compatible iterator and
  copies data from the execution environment into it.
\item[\textcode{Shrink}] A method that adjusts the size of the array in the
  execution environment to something that is a smaller size. All the data
  up to the new length must remain valid. Typically, no memory is actually
  reallocated. Instead, a different end is marked.
\item[\textcode{ReleaseResources}] A method that frees any resources
  (typically memory) in the execution environment.
\end{description}

Specializations of this template typically take on one of two forms. If the
control and execution environments have separate memory spaces, then this
class behaves by copying memory in methods such as
\textcode{PrepareForInput} and \textcode{RetrieveOutputData}. This might
require creating buffers in the control environment to efficiently move
data from control array portals.

However, if the control and execution environments share the same memory
space, the execution array manager can, and should, delegate all of its
operations to the \textidentifier{Storage} it is constructed with. VTK-m
comes with a class called
\vtkmcontinternal{ArrayManagerExecutionShareWithControl} that provides the
implementation for an execution array manager that shares a memory space
with the control environment. In this case, making the
\textidentifier{ArrayManagerExecution} specialization be a trivial subclass
is sufficient. Continuing our example of a device adapter based on C++11's
\textcode{std::thread} class, here is the implementation of
\textidentifier{ArrayManagerExecution}, which by convention would be placed
in the
\textfilename{vtkm/cont/cxx11/internal/ArrayManagerExecutionCxx11Thread.h}
header file.

\vtkmlisting{Specialization of \textidentifier{ArrayManagerExecution}.}{ArrayManagerExecutionCxx11Thread.h}

\index{execution array manager|)}
\index{array manager execution|)}
\index{device adapter!array manager|)}

\section{Algorithms}

\index{device adapter!algorithm|(}
\index{algorithm|(}

A device adapter implementation must also provide a specialization of
\vtkmcont{DeviceAdapterAlgorithm}, which is documented in
Section~\ref{sec:DeviceAdapterAlgorithms}. The implementation for the
device adapter algorithms is typically placed in a header file with a
prefix of \textfilename{DeviceAdapterAlgorithm}.

Although there are many methods in \textidentifier{DeviceAdapterAlgorithm},
it is seldom necessary to implement them all. Instead, VTK-m comes with
\vtkmcontinternal{DeviceAdapterAlgorithmGeneral} that provides generic
implementation for most of the required algorithms. By deriving the
specialization of \textidentifier{DeviceAdapterAlgorithm} from
\textidentifier{DeviceAdapterAlgorithmGeneral}, only the implementations
for \textcode{Schedule} and \textcode{Synchronize} need to be implemented.
All other algorithms can be derived from those.

That said, not all of the algorithms implemented in
\textidentifier{DeviceAdapterAlgorithmGeneral} are optimized for all types
of devices. Thus, it is worthwhile to provide algorithms optimized for the
specific device when possible. In particular, it is best to provide
specializations for the sort, scan, and reduce algorithms.

It is standard practice to implement a specialization of \textidentifier{DeviceAdapterAlgorithm} by having it inherit from \vtkmcontinternal{DeviceAdapterAlgorithmGeneral} and specializing those methods that are optimized for a particular system.
\textidentifier{DeviceAdapterAlgorithmGeneral} is a templated class that takes as its single template parameter the type of the subclass.
For example, a device adapter algorithm structure named \textidentifier{DeviceAdapterAlgorithm}\tparams{DeviceAdapterTagFoo} will subclass \textidentifier{DeviceAdapterAlgorithmGeneral}\tparams{\textidentifier{DeviceAdapterAlgorithm}\tparams{DeviceAdapterTagFoo} }.

\begin{didyouknow}
  The convention of having a subclass be templated on the derived class' type is known as the Curiously Recurring Template Pattern (CRTP).
  In the case of \textidentifier{DeviceAdapterAlgorithmGeneral}, \VTKm uses this CRTP behavior to allow the general implementation of these algorithms to run \textcode{Schedule} and other specialized algorithms in the subclass.
\end{didyouknow}

One point to note when implementing the \textcode{Schedule} methods is to
make sure that errors handled in the execution environment are handled
correctly. As described in
Section~\ref{sec:ExecutionEnvironment:ErrorHandling}, errors are signaled
in the execution environment by calling \textcode{RaiseError} on a functor
or worklet object. This is handled internally by the
\vtkmexecinternal{ErrorMessageBuffer} class.
\textidentifier{ErrorMessageBuffer} really just holds a small string
buffer, which must be provided by the device adapter's \textcode{Schedule}
method.

So, before \textcode{Schedule} executes the functor it is given, it should
allocate a small string array in the execution environment, initialize it
to the empty string, encapsulate the array in an
\textidentifier{ErrorMessageBuffer} object, and set this buffer object in
the functor. When the execution completes, \textcode{Schedule} should check
to see if an error exists in this buffer and throw a
\vtkmcont{ErrorExecution} if an error has been reported.

\begin{commonerrors}
  Exceptions are generally not supposed to be thrown in the execution
  environment, but it could happen on devices that support them.
  Nevertheless, few thread schedulers work well when an exception is thrown
  in them. Thus, when implementing adapters for devices that do support
  exceptions, it is good practice to catch them within the thread and
  report them through the \textidentifier{ErrorMessageBuffer}.
\end{commonerrors}

The following example is a minimal implementation of device adapter
algorithms using C++11's \textcode{std::thread} class. Note that no attempt
at providing optimizations has been attempted (and many are possible). By
convention this code would be placed in the
\textfilename{vtkm/cont/cxx11/internal/DeviceAdapterAlgorithmCxx11Thread.h}
header file.

\vtkmlisting{Minimal specialization of \textidentifier{DeviceAdapterAlgorithm}.}{DeviceAdapterAlgorithmCxx11Thread.h}

\index{algorithm|)}
\index{device adapter!algorithm|)}

\section{Timer Implementation}

\index{timer|(}
\index{device adapter!timer|(}

The VTK-m timer, described in Chapter~\ref{chap:Timers}, delegates to an
internal class named \vtkmcont{DeviceAdapterTimerImplementation}. The
interface for this class is the same as that for \vtkmcont{Timer}. A default
implementation of this templated class uses the system timer and the
\textcode{Synchronize} method in the device adapter algorithms.

However, some devices might provide alternate or better methods for
implementing timers. For example, the TBB and CUDA libraries come with high
resolution timers that have better accuracy than the standard system
timers. Thus, the device adapter can optionally provide a specialization of
\textidentifier{DeviceAdapterTimerImplementation}, which is typically
placed in the same header file as the device adapter algorithms.

Continuing our example of a custom device adapter using C++11's
\textcode{std::thread} class, we could use the default timer and it would
work fine. But C++11 also comes with a \textcode{std::chrono} package that
contains some portable time functions. The following code demonstrates
creating a custom timer for our device adapter using this package. By
convention, \textidentifier{DeviceAdapterTimerImplementation} is placed in
the same header file as \textidentifier{DeviceAdapterAlgorithm}.

\vtkmlisting{Specialization of \textidentifier{DeviceAdapterTimerImplementation}.}{DeviceAdapterTimerImplementationCxx11Thread.h}

\index{device adapter!timer|)}
\index{timer|)}

\index{device adapter!implementing|)}
\index{device adapter|)}