% -*- latex -*-

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

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

\VTKm 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}, files associated with the Intel Threading Building Blocks (TBB) are located in \textfilename{vtkm/cont/tbb}, and files associated with OpenMP are in \textfilename{vtkm/cont/openmp}.
The documentation here assumes that you are adding a device adapter to the \VTKm 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 \VTKm are divided into 5 header files with the names \textfilename{DeviceAdapterTag\textasteriskcentered.h}, \textfilename{DeviceAdapterRuntimeDetector\textasteriskcentered.h}, \textfilename{DeviceAdapterMemoryManager\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 7 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/DeviceAdapterRuntimeDetectorCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/DeviceAdapterMemoryManagerCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/VirtualObjectTransferCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/DeviceAdapterAlgorithmCxx11Thread.h>
\end{vtkmexample}

The reason \VTKm 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 \VTKm 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 \VTKm 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}

This new device adapter tag needs to be added to \vtkmcont{DeviceAdapterListCommon}, which is defined in \vtkmheader{vtkm/cont}{DeviceAdapterList.h}.
Other components of \VTKm will use this list to write code for the device.
If you do not add the device tag to this list, then the device will not be tried when things are invoked in the execution environment, and directly specifying execution on this device will likely fail.

\begin{vtkmexample}[ex:DeviceAdapterListCommon]{Modification of \textidentifier{DeviceAdapterListCommon} in \textfilename{DeviceAdapterList.h}}
using DeviceAdapterListCommon = vtkm::List<vtkm::cont::DeviceAdapterTagCuda,
                                           vtkm::cont::DeviceAdapterTagTBB,
                                           vtkm::cont::DeviceAdapterTagOpenMP,
                                           vtkm::cont::DeviceAdapterTagCxx11Thread,
                                           vtkm::cont::DeviceAdapterTagSerial>;
\end{vtkmexample}

\begin{didyouknow}
  The order of device adapter tags in \vtkmcont{DeviceAdapterListCommon} matters.
  Devices will be tried in the order listed in this list.
  Thus, the most ``preferred'' devices should be listed first.
  In Example \ref{ex:DeviceAdapterListCommon}, our new C++11 thread device will be used before the serial device but after the other parallel devices.

  It is OK for \vtkmcont{DeviceAdapterListCommon} to contain device adapter tags for devices that are not being compiled for.
  These devices will be registered as inactive and be skipped.
\end{didyouknow}

\index{device adapter!tag|)}

\section{Runtime Detector}

\index{device adapter!runtime detector|(}

\VTKm defines a template named \vtkmcont{DeviceAdapterRuntimeDetector} that provides the ability to detect whether a given device is available on the current system.
\textidentifier{DeviceAdapterRuntimeDetector} has a single template argument that is the device adapter tag.

\vtkmlisting{Prototype for \textidentifier{DeviceAdapterRuntimeDetector}.}{DeviceAdapterRuntimeDetectorPrototype.cxx}

All device adapter implementations must create a specialization of \textidentifier{DeviceAdapterRuntimeDetector}.
They must contain a method named \classmember{DeviceAdapterRuntimeDetector}{Exists} that returns a true or false value to indicate whether the device is available on the current runtime system.
For our simple C++ threading example, the C++ threading is always available (even if only one such processing element exists) so our implementation simply returns true if the device has been compiled.

\vtkmlisting{Implementation of \textidentifier{DeviceAdapterRuntimeDetector} specialization}{DeviceAdapterRuntimeDetectorCxx11Thread.cxx}

\index{device adapter!runtime detector|)}

\section{Memory Manager}

\index{device adapter!memory manager|(}

\VTKm defines a template named \vtkmcontinternal{DeviceAdapterMemoryManager} that provides the ability to allocate memory on the device and copy data.
\textidentifier{DeviceAdapterMemoryManager} has a single template argument that is the device adapter tag.

\vtkmlisting{Prototype for \textidentifier{DeviceAdapterMemoryManager}.}{DeviceAdapterMemoryManagerPrototype.cxx}

All device adapter implementations must create a specialization of \textidentifier{DeviceAdapterMemoryManager}.
This specialization of \textidentifier{DeviceAdapterMemoryManager} must inherit from \vtkmcontinternal{DeviceAdapterMemoryManagerBase}.
The \textidentifier{DeviceAdapterMemoryManager} allocates memory and returns it wrapped in a \vtkmcontinternal{BufferInfo} object.
The superclass provides the \classmember{DeviceAdapterMemoryManagerBase}{ManageArray} method to take a raw pointer for the device (captured as a \textcode{void \textasteriskcentered}) along with some metadata and management functions and returns that pointer wrapped in a \textidentifier{BufferInfo} management object.

A specialization of \textidentifier{DeviceAdapterMemoryManager} must override the following pure virtual methods (which are defined in the \textidentifier{DeviceAdapterMemoryManagerBase} superclass).

\begin{description}
\item[\classmember*{DeviceAdapterMemoryManager}{GetDevice}] %
  Return a \vtkmcont{DeviceAdapterId} for the device that this memory manager allocates and deallocates for.
\item[\classmember*{DeviceAdapterMemoryManager}{Allocate}] %
  Given a buffer size in bytes, allocates the buffer on the device and returns it in a \textidentifier{BufferInfo} object.
\item[\classmember*{DeviceAdapterMemoryManager}{CopyHostToDevice}] %
  Copies a \textidentifier{BufferInfo} object for memory allocated on the host to the device.
  \textidentifier{DeviceAdapterMemoryManager} must implement two forms of \classmember*{DeviceAdapterMemoryManager}{CopyHostToDevice}.
  The first form takes just a source \textidentifier{BufferInfo} and returns a new \textidentifier{BufferInfo} containing a copy of the data on the device.
  If the device supports shared or unified memory, this can be a shallow copy.
  The second form takes both a source \textidentifier{BufferInfo} and a pre-allocated destination \textidentifier{BufferInfo}.
\item[\classmember*{DeviceAdapterMemoryManager}{CopyDeviceToHost}] %
  Copies a \textidentifier{BufferInfo} object for memory allocated on the device to the host.
  \textidentifier{DeviceAdapterMemoryManager} must implement two forms of \classmember*{DeviceAdapterMemoryManager}{CopyDeviceToHost}.
  The first form takes just a source \textidentifier{BufferInfo} and returns a new \textidentifier{BufferInfo} containing a copy of the data on the host.
  If the device supports shared or unified memory, this can be a shallow copy.
  The second form takes both a source \textidentifier{BufferInfo} and a pre-allocated destination \textidentifier{BufferInfo}.
\item[\classmember*{DeviceAdapterMemoryManager}{CopyDeviceToDevice}] %
  Copies a \textidentifier{BufferInfo} object for memory allocated on the device to another buffer on the device.
  \textidentifier{DeviceAdapterMemoryManager} must implement two forms of \classmember*{DeviceAdapterMemoryManager}{CopyDeviceToDevice}.
  The first form takes just a source \textidentifier{BufferInfo} and returns a new \textidentifier{BufferInfo} containing a copy of the data on the device.
  The second form takes both a source \textidentifier{BufferInfo} and a pre-allocated destination \textidentifier{BufferInfo}.
\end{description}

If the control and execution environments share the same memory space, the execution array manager can, and should, share buffers among host and ``device'' and shallow copy data when possible.
\VTKm comes with a class called \vtkmcontinternal{DeviceAdapterMemoryManagerShared} that provides the implementation for a device memory manager that shares a memory space with the control environment.
In this case, the \textidentifier{DeviceAdapterMemoryManager} specialization need only override the \classmember*{DeviceAdapterMemoryManager}{GetDevice} method.
(\textidentifier{DeviceAdapterMemoryManagerShared} will provide all other necessary overrides.)

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

\vtkmlisting{Specialization of \textidentifier{DeviceAdapterMemoryManager}.}{DeviceAdapterMemoryManagerCxx11Thread.h}

\begin{didyouknow}
  You may notice that although \vtkmcontinternal{DeviceAdapterMemoryManager} requires methods to allocate memory, it has no methods to delete memory.
  This is because all memory created by a \vtkmcontinternal{DeviceAdapterMemoryManager} is wrapped in a \vtkmcontinternal{BufferInfo} object.
  Responsibility for the memory management is taken over by \textidentifier{BufferInfo} and the memory will be automatically deleted once it is no longer used.
\end{didyouknow}

\index{device adapter!memory manager|)}

\section{Virtual Object Transfer}

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

\VTKm defines a template named \vtkmcontinternal{VirtualObjectTransfer} that is responsible for instantiating virtual objects in the execution environment.
% Chapter~\ref{chap:VirtualObjects} discusses how to design and implement virtual objects.
Virtual objects are a deprecated feature that will be removed in a future version of \VTKm.
The \textidentifier{VirtualObjectTransfer} class is the internal mechanism that allocates space for the object and sets up the virtual method tables for them.
This class has two template parameters.
The first parameter is the concrete derived type of the virtual object to be transferred to the execution environment.
It is assumed that after the object is copied to the execution environment, a pointer to a base superclass of this concrete derived type will be used.
The second template argument is 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[\textidentifier{VirtualObjectTransfer}] (constructor)
  A \textidentifier{VirtualObjectTransfer} has a constructor that takes a pointer to the derived type that (eventually) gets transferred to the execution environment of the given device adapter.
  The object provided must stay valid for the lifespan of the \textidentifier{VirtualObjectTransfer} object.
\item[\textcode{PrepareForExecution}]
  Transfers the virtual object (given in the constructor) to the execution environment and returns a pointer to the object that can be used in the execution environment.
  The returned object may not be valid in the control environment and should not be used there.
  \textcode{PrepareForExecution} takes a single \textcode{bool} argument.
  If the argument is false and \textcode{PrepareForExecution} was called previously, then the method can return the same data as the last call without any updates.
  If the argument is true, then the data in the execution environment is always updated regardless of whether data was copied in a previous call to \textcode{PrepareForExecution}.
  This argument is used to tell the \textidentifier{VirtualObjectTransfer} whether the object in the control environment has changed and has to be updated in the execution environment.
\item[\textcode{ReleaseResources}]
  Frees up any resources in the execution environment.
  Any previously returned virtual object from \textcode{PrepareForExecution} becomes invalid.
  (The destructor for \textidentifier{VirtualObjectTransfer} should also release the resources.)
\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 (where the virtual table will be invalid) and a new object is created in the execution environment by copying the object from the control environment.
It can be assumed that the object can be trivially copied (with the exception of the virtual method table).

\begin{didyouknow}
  For some devices, like CUDA, it is either only possible or more efficient to allocate data from the host (the control environment).
  To avoid having to allocate data from the device (the execution environment), implement \textcode{PrepareForExecution} by first allocating data from the host and then running code on the device that does a ``placement new'' to create and copy the object in the pre-allocated space.
\end{didyouknow}

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.
\VTKm 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 provides the underlying implementation of the algorithms described in Chapter \ref{chap:DeviceAlgorithms}.
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, \VTKm 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
Chapter \ref{chap:WorkletErrorHandling}, 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 \VTKm 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|)}
