% -*- 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 class to establish virtual objects 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.

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 4 header files with the names \textfilename{DeviceAdapterTag\textasteriskcentered.h}, \textfilename{ArrayManagerExecution\textasteriskcentered.h}, \textfilename{VirtualObjectTransfer\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 4 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/VirtualObjectTransferCxx11Thread.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}
\label{sec:ImplementingDeviceAdapters: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.
\textidentifier{ArrayManagerExecution} is also paired with two helper classes, \vtkmcontinternal{ExecutionPortalFactoryBasic} and \vtkmcontinternal{ExecutionArrayInterfaceBasic}, which provide operations for creating and operating on and manipulating data in standard C arrays.
All 3 class specializations are typically defined in an internal header file with a prefix of \textfilename{ArrayManagerExecution}.
The following subsections describe each of these classes.

\subsection{\textidentifier{ArrayManagerExecution}}

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

A device adapter must provide a partial specialization of
\vtkmcontinternal{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}] 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}

\subsection{\textidentifier{ExecutionPortalFactoryBasic}}

\index{execution portal factory|(}
\index{basic execution portal factory|(}
\index{device adapter!basic execution portal|(}

\vtkmlisting{Prototype for \protect\vtkmcontinternal{ExecutionPortalFactoryBasic}.}{ExecutionPortalFactoryBasicPrototype.cxx}

A device adapter must provide a partial specialization of \vtkmcontinternal{ExecutionPortalFactoryBasic} for its device adapter tag.
The implementation for \textidentifier{ExecutionPortalFactoryBasic} is capable of taking pointers to an array in the execution environment and returning an array portal to the data in that array.
\textidentifier{ExecutionPortalFactoryBasic} has no state and all of its methods are static.
\textidentifier{ExecutionPortalFactoryBasic} provides the following elements.

\begin{description}
\item[\textcode{ValueType}]
  The type for each item in the array.
  This is the same type as the first template argument.
\item[\textcode{PortalType}]
  The type for the read/write portals created by the class.
\item[\textcode{PortalConstType}]
  The type for read-only portals created by the class.
\item[\textcode{CreatePortal}]
  A static method that takes two pointers of type \textcode{ValueType*} that point to the beginning (first element) and end (one past the last element) of the array to create a portal for.
  Returns a portal of type \textcode{PortalType} that works in the execution environment.
  \fix{Is that true? If so, why not just create an array portal of iterators?}
\item[\textcode{CreatePortalConst}]
  A static method that takes two pointers of type \textcode{const ValueType*} that point to the beginning (first element) and end (one past the last element) of the array to create a portal for.
  Returns a portal of type \textcode{PortalConstType} that works in the execution environment.
  \fix{Is that true? If so, why not just create an array portal of iterators?}
\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 creating an object in the execution environment for this data that is not directly accessible in the control environment.
\fix{Is this true? The CUDA version seems to be doing something more fancy.}

However, if the control and execution environments share the same memory space, then the execution array manager can, and should, return a simple \vtkmcontinternal{ArrayPortalFromIterators}.
\VTKm comes with a class called \vtkmcontinternal{ExecutionPortalFactoryBasicShareWithControl} that provides the implementation for a basic execution portal factory that shares a memory space with the control environment.
In this case, making the \textidentifier{ExecutionPortalFactoryBasic} 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{ExecutionPortalFactoryBasic}, which by convention would be placed in the \textfilename{vtkm/cont/cxx11/internal/ArrayManagerExecutionCxx11Thread.h} header file.

\vtkmlisting{Specialization of \textidentifier{ExecutionPortalFactoryBasic}.}{ExecutionPortalFactoryBasicCxx11Thread.cxx}

\index{device adapter!basic execution portal|)}
\index{basic execution portal factory|)}
\index{execution portal factory|)}

\subsection{\textidentifier{ExecutionArrayInterfaceBasic}}

\index{execution array interface|(}
\index{basic execution array interface|(}
\index{device adapter!basic execution array interface|(}

\vtkmlisting{Prototype for \protect\vtkmcontinternal{ExecutionArrayInterfaceBasic}.}{ExecutionArrayInterfaceBasicPrototype.cxx}

A device adapter must provide a partial specialization of \vtkmcontinternal{ExecutionArrayInterfaceBasic} for its device adapter tag.
The implementation for \textidentifier{ExecutionArrayInterfaceBasic} is expected to allow allocation of basic C arrays in the execution environment and to copy data between control and execution environments.
All implementations of \textidentifier{ExecutionArrayInterfaceBasic} are expected to inherit from \vtkmcontinternal{ExecutionArrayInterfaceBasicBase} and implement the pure virtual methods therein.
All implementations are also expected to have a constructor that takes a reference to a \vtkmcontinternal{StorageBasicBase}, which should subsequently be passed to the \textidentifier{ExecutionArrayInterfaceBasicBase}.
The methods that \vtkmcontinternal{ExecutionArrayInterfaceBasic} must override are the following.

\begin{description}
\item[\textcode{GetDeviceId}]
  Returns a \vtkmcont{DeviceAdapterId} integer representing a unique identifier for the device associated with this implementation.
  This number should be the same as the \textcode{VTKM\_DEVICE\_ADAPTER\_} macro described in Section~\ref{sec:ImplementingDeviceAdapters:Tag}.
\item[\textcode{Allocate}]
  Takes a reference to a \vtkmcontinternal{TypelessExecutionArray}, which holds a collection of array pointer references, and a size of allocation in bytes.
  The method should allocate an array of the given size in the execution environment and return the resulting pointers in the given \textidentifier{TypelessExecutionArray} reference.
\item[\textcode{Free}]
  Takes a reference to a \vtkmcontinternal{TypelessExecutionArray} created in a previous call to \textcode{Allocate} and frees the memory.
  The array references in the \textidentifier{TypelessExecutionArray} should be set to \textcode{nullptr}.
\item[\textcode{CopyFromControl}]
  Takes a \textcode{const void*} pointer for an array in the control environment, a \textcode{void*} for an array in the execution environment, and a size of the arrays in bytes.
  The method copies the data from the control array to the execution array.
\item[\textcode{CopyToControl}]
  Takes a \textcode{const void*} pointer for an array in the execution environment, a \textcode{void*} for an array in the control environment, and a size of the arrays in bytes.
  The method copies the data from the execution array to the control array.
\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 allocating arrays on the device and copying data between the main CPU and the device.

However, if the control and execution environments share the same memory space, then the execution array interface can, and should, use the storage on the control environment to allocate arrays and do simple copies (shallow where possible).
\VTKm comes with a class called \vtkmcontinternal{ExecutionArrayInterfaceBasicShareWithControl} that provides the implementation for a basic execution array interface that shares a memory space with the control environment.
In this case, it is best to make the \textidentifier{ExecutionArrayInterfaceBasic} specialization a subclass of \textidentifier{ExecutionArrayInterfaceBasicShareWithControl}.
Note that in this case you still need to define a constructor that takes a reference to \vtkmcontinternal{StorageBasicBase} (which is passed straight to the superclass) and an implementation of the \textcode{GetDeviceId} method.

Continuing our example of a device adapter based on C++11's \textcode{std::thread} class, here is the implementation of \textidentifier{ExecutionArrayInterfaceBasic}, which by convention would be placed in the \textfilename{vtkm/cont/cxx11/internal/ArrayManagerExecutionCxx11Thread.h} header file.

\vtkmlisting{Specialization of \textidentifier{ExecutionArrayInterfaceBasic}.}{ExecutionArrayInterfaceBasicCxx11Thread.cxx}

\index{device adapter!basic execution array interface|)}
\index{basic execution array interface|)}
\index{execution array interface|)}

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

\section{Virtual Object Transfer}

\index{device adapter!virtual object transfer|(}
\index{virtual object transfer|(}
\index{transfer virtual object|(}

VTK-m defines a template named \vtkmcontinternal{VirtualObjectTransfer} that is responsible for instantiating virtual objects in the execution environment.
\fix{Re-add the following after it is implemented.}
%% Chapter~\ref{chap:VirtualObjects} discusses how to design and implement virtual 
objects.
The \textidentifier{VirtualObjectTransfer} class is the internal mechanism that  allocates space for the object and sets up the method tables for them.
This class has three template parameters: the class of the virtual object used in the execution environment, the class of the concrete implementation, and the device adapter on which to put the object.

\vtkmlisting{Prototype for \protect\vtkmcontinternal{VirtualObjectTransfer}.}{VirtualObjectTransferPrototype.cxx}

A device adapter must provide a partial specialization of \textidentifier{VirtualObjectTransfer} for its device adapter tag.
This partial specialization is typically defined in an internal header file with a prefix of \textfilename{VirtualObjectTransfer}.
The implementation for \textidentifier{VirtualObjectTransfer} can establish a virtual object in the execution environment based on an object in the control environment, update the state of said object, and release all the resources for the object.
\textidentifier{VirtualObjectTransfer} must provide the following methods.

\begin{description}
\item[\textcode{Create}]
  A static method that takes a reference to the virtual object to create and a pointer to the concrete object to bind to.
  The method returns a \textcode{void*} pointer to an internal data structure that is passed to the other 2 methods.
\item[\textcode{Update}]
  A static method that takes the \textcode{void*} pointer returned from \textcode{Create} and the pointer to the concrete object passed to \textcode{Create}.
  The state of the object in the execution environment (the first argument) is updated to reflected to update the state of the control object (the second argument).
\item[\textcode{Cleanup}]
  A static method that takes the \textcode{void*} pointer returned from \textcode{Create} and deletes all the state and resources used in the execution environment.
  After calling this method the virtual object becomes invalid.
\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 the concrete control object to the execution environment, allocating space for the virtual object in the execution environment, and calling \textcode{Bind} on the virtual object.
A pointer to the allocated space is what is returned from \textcode{Create}.

However, if the control and execution environments share the same memory space, the virtual object transfer can, and should, just bind directly with the target concrete object.
VTK-m comes with a class called \vtkmcontinternal{VirtualObjectTransferShareWithControl} that provides the implementation for a virtual object transfer that shares a memory space with the control environment.
In this case, making the \textidentifier{VirtualObjectTransfer} 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{VirtualObjectTransfer}, which by convention would be placed in the \textfilename{vtkm/cont/cxx11/internal/VirtualObjectTransferCxx11Thread.h} header file.

\vtkmlisting{Specialization of \textidentifier{VirtualObjectTransfer}.}{VirtualObjectTransferCxx11Thread.h}

\index{transfer virtual object|)}
\index{virtual object transfer|)}
\index{device adapter!virtual object transfer|)}

\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|)}
