% -*- 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 6 header files with the names \textfilename{DeviceAdapterTag\textasteriskcentered.h}, \textfilename{DeviceAdapterRuntimeDetector\textasteriskcentered.h}, \textfilename{ArrayManagerExecution\textasteriskcentered.h}, \textfilename{VirtualObjectTransfer\textasteriskcentered.h}, \textfilename{AtomicInterfaceExecution\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 6 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/ArrayManagerExecutionCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/VirtualObjectTransferCxx11Thread.h>
#include <vtkm/cont/cxx11/internal/AtomicInterfaceExecutionCxx11Thread.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}

\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{Array Manager Execution}

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

\VTKm 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. \VTKm
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 the array.
  Returns a portal of type \textcode{PortalType} that works in the execution environment.
\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 the array.
  Returns a portal of type \textcode{PortalConstType} that works in the execution environment.
\end{description}

Specializations of this template typically take on one of two forms.
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.

However, if the control and execution environments have separate memory spaces, then the typical \vtkmcontinternal{ArrayPortalFromIterators} class might not work in the execution environment.
In this case a custom array portal class will have to be implemented and created within the \textidentifier{ExecutionPortalFactoryBasic}.

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|(}

\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.
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{Atomic Interface Execution}

\index{device adapter!atomic interface execution|(}
\index{atomic interface execution|(}

\VTKm defines a template named \vtkmcontinternal{AtomicInterfaceExecution} that is responsible for performing atomic operations on raw addresses.
\vtkmcontinternal{AtomicInterfaceExecution} defines a \textidentifier{WordTypePreferred} member that is the fastest available for bitwise operations of the given device.
At minimum, the interface must support operations on \textidentifier{WordTypePreferred} and \vtkm{WordTypeDefault}, which  may be the same.  
A full list of the supported word types is advertised in the type list stored in \textidentifier{WordTypes}.
\vtkmcontinternal{AtomicInterfaceExecution} must provide the following methods for inputs of both pointer types \textidentifier{WordTypePrefered} and \vtkm{WordTypeDefault}:

\begin{description}
\item[\textcode{Load}]
  Atomically load a value from memory while enforcing, at a minimum, "acquire" memory ordering.
\item[\textcode{Store}]
  Atomically write a value to memory while enforcing, at a minimum "release" memory ordering.
\item[\textcode{Not}]
  Perform a bitwise atomic not operation on the word at the provided address.
\item[\textcode{And}]
  Perform a bitwise atomic and operation on the word at the provided address.
\item[\textcode{Or}]
  Perform a bitwise atomic or operation on the word at the provided address.
\item[\textcode{Xor}]
  Perform a bitwise atomic xor operation on the word at the provided address.
\item[\textcode{CompareAndSwap}]
  Perform a bitwise atomic Compare and Swap operation on the word at the provided address.
\end{description}

\VTKm provides a default implementation of the above operations that can be used on devices that share the control environment.
In order to use this implementation, simply subclass \vtkmcontinternal{AtomicInterfaceControl} from a template specialization of \vtkmcontinternal{AtomicInterfaceExecution} that takes a template argument of the new device adapter tag.

\vtkmlisting{Specialization of \textidentifier{AtomicInterfaceExecution}.}{AtomicInterfaceExecutionCxx11Thread.h}

\index{atomic interface execution|)}
\index{device adapter!atomic interface execution|)}

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