% -*- latex -*-

\chapter{Device Adapters}
\label{chap:DeviceAdapter}

\index{device adapter|(}

As multiple vendors vie to provide accelerator-type processors, a great
variance in the computer architecture exists. Likewise, there exist
multiple compiler environments and libraries for these devices such as
CUDA, OpenMP, and various threading libraries. These compiler technologies
also vary from system to system.

To make porting among these systems at all feasible, we require a base
language support, and the language we use is C++. The majority of the code
in VTK-m is constrained to the standard C++ language constructs to minimize
the specialization from one system to the next.

Each device and device technology requires some level of code
specialization, and that specialization is encapsulated in a unit called a
\keyterm{device adapter}. Thus, porting VTK-m to a new architecture can be
done by adding only a device adapter.

The device adapter is shown diagrammatically as the connection between the
control and execution environments in Figure~\ref{fig:VTKmDiagram} on
page~\pageref{fig:VTKmDiagram}. The functionality of the device adapter
comprises two main parts: a collection of parallel algorithms run in the
execution environment and a module to transfer data between the control and
execution environments.

This chapter describes how tags are used to specify which devices to use
for operations within VTK-m. The chapter also outlines the features provided
by a device adapter that allow you to directly control a device. Finally,
we document how to create a new device adapter to port or specialize VTK-m
for a different device or system.


\section{Device Adapter Tag}
\label{sec:DeviceAdapterTag}

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

A device adapter is identified by a \keyterm{device adapter tag}.
This tag, which is simply an empty struct type, is used as the template parameter for several classes in the VTK-m control environment and causes these classes to direct their work to a particular device.
The following device adapter tags are available in VTK-m.

\index{device adapter!tag!provided|(}
\index{tag!device adapter!provided|(}

\begin{description}
\item[\vtkmcont{DeviceAdapterTagSerial}] \index{serial} Performs all
  computation on the same single thread as the control environment. This
  device is useful for debugging. This device is always available. This tag
  is defined in \vtkmheader{vtkm/cont}{DeviceAdapterSerial.h}.
\item[\vtkmcont{DeviceAdapterTagCuda}] \index{CUDA} Uses a CUDA capable
  GPU device. For this device to work, VTK-m must be configured to use CUDA
  and the code must be compiled by the CUDA \textfilename{nvcc}
  compiler. This tag is defined in
  \vtkmheader{vtkm/cont/cuda}{DeviceAdapterCuda.h}.
\item[\vtkmcont{DeviceAdapterTagOpenMP}] \index{OpenMP} Uses OpenMP
  compiler extensions to run algorithms on multiple threads. For this
  device to work, VTK-m must be configured to use OpenMP and the code must be
  compiled with a compiler that supports OpenMP pragmas. This tag is
  defined in \vtkmheader{vtkm/cont/openmp}{DeviceAdapterOpenMP.h}.
\item[\vtkmcont{DeviceAdapterTagTBB}]
  \index{Intel Threading Building Blocks} \index{TBB} Uses the Intel
  Threading Building Blocks library to run algorithms on multiple
  threads. For this device to work, VTK-m must be configured to use TBB and
  the executable must be linked to the TBB library. This tag is defined in
  \vtkmheader{vtkm/cont/tbb}{DeviceAdapterTBB.h}.
\end{description}

\index{tag!device adapter!provided|)}
\index{device adapter!tag!provided|)}

The following example uses the tag for the Intel Threading Building blocks
device adapter to prepare an output array for that device. In this case,
the device adapter tag is passed as a parameter for the
\classmember{ArrayHandle}{PrepareForOutput} method.

\vtkmlisting{Specifying a device using a device adapter tag.}{SpecifyDeviceAdapter.cxx}

Functions, methods, and classes that directly use device adapter tags are usually templated on the device adapter tag.
This allows the function or class to be applied to any type of device specified at compile time.

\vtkmlisting[ex:DeviceTemplateArg]{Specifying a device using template parameters.}{DeviceTemplateArg.cxx}

\begin{commonerrors}
  A device adapter tag is a class just like every other type in C++.
  Thus it is possible to accidently use a type that is not a device adapter tag when one is expected as a template argument.
  This leads to unexpected errors in strange parts of the code.
  To help identify these errors, it is good practice to use the \vtkmmacro{VTKM\_IS\_DEVICE\_ADAPTER\_TAG} macro to verify the type is a valid device adapter tag.
  Example~\ref{ex:DeviceTemplateArg} uses this macro on line 4.
\end{commonerrors}

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

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

Using a device adapter tag directly means that the type of device needs to be known at compile time.
To store a device adapter type at run time, one can instead use \vtkmcont{DeviceAdapterId}.
\textidentifier{DeviceAdapterId} is a superclass to all the device adapter tags, and any device adapter tag can be ``stored'' in a \textidentifier{DeviceAdapterId}.
Thus, it is more common for functions and classes to use \textidentifier{DeviceAdapterId} then to try to track a specific device with templated code.

In addition to the provided device adapter tags listed previously, a \textidentifier{DeviceAdapterId} can store some special device adapter tags that do not directly specify a specific device.

\index{device adapter!id!provided|(}
\index{id!device adapter!provided|(}

\begin{description}
\item[\vtkmcont{DeviceAdapterTagAny}] \index{device adapter!any}
  Used to specify that any device may be used for an operation.
  In practice this is limited to devices that are currently available.
\item[\vtkmcont{DeviceAdapterTagUndefined}] \index{device adapter!undefined}
  Used to avoid specifying a device.
  Useful as a placeholder when a device can be specified but none is given.
\end{description}

\index{id!device adapter!provided|)}
\index{device adapter!id!provided|)}

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


\section{Device Adapter Traits}
\label{sec:DeviceAdapterTraits}

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

In Section~\ref{sec:Traits} we see that \VTKm defines multiple \keyterm{traits} classes to publish and retrieve information about types.
In addition to traits about basic data types, \VTKm also has instances of defining traits for other features.
One such traits class is \vtkmcont{DeviceAdapterTraits}, which provides some basic information about a device adapter tag.
The \textidentifier{DeviceAdapterTraits} class provides the following features.

\begin{description}
\item[{\classmember*{DeviceAdapterTraits}{GetId}}]
  A \textcode{static} method taking no arguments that returns a unique integer identifier for the device adapter.
  The integer identifier is stored in a type named \vtkmcont{DeviceAdapterId}, which is currently aliased to \vtkm{Int8}.
  The device adapter id is useful for storing run time information about a device without directly compiling for the class.
\item[{\classmember*{DeviceAdapterTraits}{GetName}}]
  A \textcode{static} method that returns a string description for the device adapter.
  The string is stored in a type named \vtkmcont{DeviceAdapterNameType}, which is currently aliased to \textcode{std::string}.
  The device adapter name is useful for printing information about a device being used.
\item[{\classmember*{DeviceAdapterTraits}{Valid}}]
  A \textcode{static const bool} that is true if the implementation of the device is available.
  The valid flag is useful for conditionally compiling code depending on whether a device is available.
\end{description}

The following example demonstrates using the \vtkmcont{DeviceAdapterId} to check whether an array already has its data available on a particular device.
Code like this can be used to attempt find a device on which data is already available to avoid moving data across devices.
For simplicity, this example just outputs a message.

\vtkmlisting[ex:DeviceAdapterTraits]{Using \textidentifier{DeviceAdapterTraits}.}{DeviceAdapterTraits.cxx}

\VTKm contains multiple devices that might not be available for a variety of reasons.
For example, the CUDA device is only available when code is being compiled with the special \textfilename{nvcc} compiler.
To make it easier to manage devices that may be available in some configurations but not others, \VTKm always defines the device adapter tag structure, but signals whether the device features are available through the \classmember{DeviceAdapterTraits}{Valid} flag.
For example, \VTKm always provides the \vtkmheader{vtkm/cont/cuda}{DeviceAdapterCuda.h} header file and the \vtkmcont{DeviceAdapterTagCuda} tag defined in it.
However, \vtkmcont{DeviceAdapterTraits}\tparams{\vtkmcont{DeviceAdapterTagCuda}}\textcode{::}\classmember*{DeviceAdapterTraits}{Valid} is true if and only if \VTKm was configured to use CUDA and the code is being compiled with \textfilename{nvcc}.
The following example uses \textidentifier{DeviceAdapterTraits} to wrap the function defined in Example{ex:DeviceAdapterTraits} in a safer version of the function that checks whether the device is valid and will compile correctly in either case.

\vtkmlisting[ex:DeviceAdapterValid]{Managing invalid devices without compile time errors.}{DeviceAdapterValid.cxx}

Note that Example~\ref{ex:DeviceAdapterValid} makes use of \textcode{std::integral\_constant} to make it easier to overload a function based on a \textcode{bool} value.
The example also makes use of \textcode{std::true\_type} and \textcode{std::false\_type}, which are aliases of true and false Boolean integral constants.
They save on typing and make the code more clear.

\begin{didyouknow}
  It is rare that you have to directly query whether a particular device is valid.
  If you wish to write functions that support multiple devices, it is common to wrap them in a \vtkmcont{TryExecute}, which takes care of invalid devices for you.
  \textidentifier{TryExecute} is described in Chapter\ref{chap:TryExecute}.
\end{didyouknow}

\begin{commonerrors}
  Be aware that even though supported \VTKm devices always have a tag and associated traits defined, the rest of the implementation will likely be missing for devices that are not valid.
  Thus, you are likely to get errors in code that uses an invalid tag in any class that is not \textidentifier{DeviceAdapterTraits}.
  For example, you might be tempted to implement the behavior of Example~\ref{ex:DeviceAdapterValid} by simply adding an \textcode{if} condition to the function in Example~\ref{ex:DeviceAdapterTraits}.
  However, if you did that, then you would get compile errors in other \textcode{if} branches that use the invalid device tag (even though they can never be reached).
  This is why Example~\ref{ex:DeviceAdapterValid} instead uses function overloading to avoid compiling any code that attempts to use an invalid device adapter.
\end{commonerrors}

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


\section{Runtime Device Tracker}
\label{sec:RuntimeDeviceTracker}

\index{runtime device tracker|(}
\index{device adapter!runtime tracker|(}

It is often the case that you are agnostic about what device \VTKm algorithms run so long as they complete correctly and as fast as possible.
Thus, rather than directly specify a device adapter, you would like \VTKm to try using the best available device, and if that does not work try a different device.
Because of this, there are many features in \VTKm that behave this way.
For example, you may have noticed that running filters, as in the examples of Chapter~\ref{chap:RunningFilters}, you do not need to specify a device; they choose a device for you.

However, even though we often would like \VTKm to choose a device for us, we still need a way to manage device preferences.
\VTKm also needs a mechanism to record runtime information about what devices are available so that it does not have to continually try (and fail) to use devices that are not available at runtime.
These needs are met with the \vtkmcont{RuntimeDeviceTracker} class.
\textidentifier{RuntimeDeviceTracker} maintains information about which devices can and should be run on.
\textidentifier{RuntimeDeviceTracker} has the following methods.

\begin{description}
\item[{\classmember*{RuntimeDeviceTracker}{CanRunOn}}]
  Takes a device adapter tag and returns true if \VTKm was configured for the device and it has not yet been marked as disabled.
\item[{\classmember*{RuntimeDeviceTracker}{DisableDevice}}]
  Takes a device adapter tag and marks that device to not be used.
  Future calls to \classmember*{RuntimeDeviceTracker}{CanRunOn} for this device will return false until that device is reset.
\item[{\classmember*{RuntimeDeviceTracker}{ResetDevice}}]
  Takes a \vtkmcont{DeviceAdapterTag} and resets the state for that device to its default value.
  Each device defaults to on as long as \VTKm is configured to use that device and a basic runtime check finds a viable device.
\item[{\classmember*{RuntimeDeviceTracker}{Reset}}]
  Resets all devices.
  This equivocally calls \classmember*{RuntimeDeviceTracker}{ResetDevice} for all devices supported by \VTKm.
\item[{\classmember*{RuntimeDeviceTracker}{ForceDevice}}]
  Takes a device adapter tag and enables that device.
  All other devices are disabled.
  This method throws a \vtkmcont{ErrorBadValue} if the requested device cannot be enabled.
\item[{\classmember*{RuntimeDeviceTracker}{DeepCopy}}]
  \textidentifier{RuntimeDeviceTracker} behaves like a smart pointer for its state.
  That is, if you copy a \textidentifier{RuntimeDeviceTracker} and then change the state of one (by, for example, calling \classmember*{RuntimeDeviceTracker}{DisableDevice} on one), then the state changes for both.
  If you want to copy the state of a \textidentifier{RuntimeDeviceTracker} but do not want future changes to effect each other, then use \classmember*{RuntimeDeviceTracker}{DeepCopy}.
  There are two versions of \classmember*{RuntimeDeviceTracker}{DeepCopy}.
  The first version takes no arguments and returns a new \textidentifier{RuntimeDeviceTracker}.
  The second version takes another instance of a \textidentifier{RuntimeDeviceTracker} and copies its state into this class.
\item[{\classmember*{RuntimeDeviceTracker}{ReportAllocationFailure}}]
  A device might have less working memory available than the main CPU.
  If this is the case, memory allocation errors are more likely to happen.
  This method is used to report a \vtkmcont{ErrorBadAllocation} and disables the device for future execution.
\item[{\classmember*{RuntimeDeviceTracker}{ReportBadDeviceFailure}}]
  It is possible that a device may throw a \vtkmcont{ErrorBadDevice} failure caused by some erroneous device issue.
  If this occurs, it is possible to catch the \vtkmcont{ErrorBadDevice} exception and pass it to \classmember*{RuntimeDeviceTracker}{ReportBadDeviceFailure} along with the \vtkmcont{DeviceAdapterId} to forcefully disable a device.
\end{description}

A \textidentifier{RuntimeDeviceTracker} can be used to specify which devices to consider for a particular operation.
For example, let us say that we want to perform a deep copy of an array using the \vtkmcont{ArrayCopy} method (described in Section~\ref{sec:DeepArrayCopies}).
However, we do not want to do the copy on a CUDA device because we happen to know the data is not on that device and we do not want to spend the time to transfer the data to that device.
Since each thread maintains a \textidentifier{RuntimeDeviceTracker}, we can simply disable the device before calling \textidentifier{ArrayCopy} to guarantee that data transfer does not occur on the CUDA device.
This is best achieved using a \vtkmcont{ScopedRuntimeDeviceTracker} so that the disabled device is automatically restored once the program leaves its current scope.
\fix{TODO: The documentation of \textidentifier{RuntimeDeviceAdapter} should be redone to actually document \textidentifier{ScopedRuntimeDeviceTracker} and favor its use.}

\vtkmlisting[ex:RestrictCopyDevice]{Disabling a device with \textidentifier{RuntimeDeviceTracker}.}{RestrictCopyDevice.cxx}

\begin{didyouknow}
  Section~\ref{sec:DeviceAdapterTraits} warned that using device adapter tags for devices that are not available can cause compile time errors when used with most features of \VTKm.
  This is not the case for \textidentifier{RuntimeDeviceTracker}.
  You may pass \textidentifier{RuntimeDeviceTracker} any device adapter tag regardless of whether \VTKm is configured for that device or whether the current compiler supports that device.
  This allows you to set up a \textidentifier{RuntimeDeviceTracker} in a translation unit that does not support a particular device and pass it to function compiled in a unit that does.
\end{didyouknow}

It can be tedious to maintain your own \textidentifier{RuntimeDeviceTracker} and pass it to every function that chooses a device.
To make this easier, \VTKm maintains a per thread runtime device tracker, which can be retrieved with the \vtkmcont{GetRuntimeDeviceTracker} function.
Specifying a \textidentifier{RuntimeDeviceTracker} is almost always optional, and the per thread runtime device tracker is used if none is specified.

One of the nice features about having a per thread runtime device tracker is that when an algorithm encounters a problem with a device, it can be marked as disabled and future algorithms can skip over that non-functioning device.
This information can be shared between various \VTKm threads and helps minimize the time spent checking for malfunctioning devices.
That said, it may be the case where you want to re-enable a device previously marked as disabled.
For example, an algorithm may disable a device in the tracker because that device ran out of memory.
However, your code might want to re-enable such devices if moving on to a different data set.
This can be done by simply calling a reset method on the global runtime device tracker.

\vtkmlisting[ex:ResetThreadLocalDevice]{Resetting the Thread Local \textidentifier{RuntimeDeviceTracker}.}{ResetThreadLocalDevice.cxx}

It is also possible to restrict devices that are used through the global runtime device adapter.
For example, if you are debugging some code, you might find it useful to restrict \VTKm to use the serial device.

\vtkmlisting[ex:ForceThreadLocalDevice]{Restricting which devices \VTKm uses per thread.}{ForceThreadLocalDevice.cxx}

\index{device adapter!runtime tracker|)}
\index{runtime device tracker|)}

\section{Predicates and Operators}
\label{sec:PredicatesAndOperators}

\index{predicates and operators|(}

\VTKm follows certain design philosophies consistent with the functional programming paradigm.  
This assists in making implementations device agnostic and ensuring that various functions operate correctly and efficiently in multiple environments.
Many basic operations, such as binary and unary comparisons and predicates, are implemented as templated functors. 
These are mostly re-implementations of basic C++ STL functors that can be used in the \VTKm execution environment.

Strictly using a functor by itself adds little in the way of functionality to the code.
Their use is demonstrated more when used as parameters to one of the \vtkmcont{Algorithm} (discussed in detail in Section~\ref{sec:DeviceAdapterAlgorithms}).
Currenly, \VTKm provides 3 categories of functors: \textcode{Unary Predicates}, \textcode{Binary Predicates}, and \textcode{Binary Operators}.

\subsection{Unary Predicates}
\label{sec:UnaryPredicates}

\index{predicates and operators!unary predicates|(}

\textcode{Unary Predicates} are functors that take a single parameter and return a Boolean value.
These types of functors are useful in determining if values have been initialized or zeroed out correctly.

\begin{description}
\item[\vtkm{IsZeroInitialized}] Returns True if argument is the identity of its type.
\item[\vtkm{NotZeroInitialized}] Returns True if the argument is not the identify of its type.
\item[\vtkm{LogicalNot}] Returns True iff the argument is False.
  Requires that the argument type is convertible to a Boolean or implements the \textcode{!} operator.
\end{description}

\vtkmlisting{Basic Unary Predicate.}{UnaryPredicates.cxx}

\index{predicates and operators!unary predicates|)}

\subsection{Binary Predicates}
\label{sec:BinaryPredicates}

\index{predicates and operators!binary predicates|(}

\textcode{Binary Predicates} take two parameters and return a single Boolean value.
These types of functors are used when comparing two different parameters for some sort of condition.

\begin{description}
\item[\vtkm{Equal}] Returns True iff the first argument is equal to the second argument.
  Requires that the argument type implements the \textcode{==} operator.
\item[\vtkm{NotEqual}] Returns True iff the first argument is not equal to the second argument.
  Requires that the argument type implements the \textcode{!=} operator.
\item[\vtkm{SortLess}] Returns True iff the first argument is less than the second argument.
  Requires that the argument type implements the \textcode{<} operator.
\item[\vtkm{SortGreater}] Returns True iff the first argument is greater than the second argument.
  Requires that the argument type implements the \textcode{<} operator (the comparison is inverted internally).
\item[\vtkm{LogicalAnd}] Returns True iff the first argument and the second argument are True.
  Requires that the argument type is convertible to a Boolean or implements the \textcode{\&\&} operator.
\item[\vtkm{LogicalOr}] Returns True iff the first argument or the second argument is True.
  Requires that the argument type is convertible to a Boolean or implements the \textcode{||} operator.
\end{description}

\vtkmlisting{Basic Binary Predicate.}{BinaryPredicates.cxx}

\index{predicates and operators!binary predicates|)}

\subsection{Binary Operators}
\label{sec:BinaryOperators}

\index{predicates and operators!binary operators|(}

\textcode{Binary Operators} take two parameters and return a single value (usually of the same type as the input arguments).
These types of functors are useful when performing reductions or transformations of a dataset.

\begin{description}
\item[\vtkm{Sum}] Returns the sum of two arguments.
  Requires that the argument type implements the \textcode{+} operator.
\item[\vtkm{Product}] Returns the product (multiplication) of two arguments.
  Requires that the argument type implements the \textcode{*} operator.
\item[\vtkm{Maximum}] Returns the larger of two arguments.
  Requires that the argument type implements the \textcode{<} operator.
\item[\vtkm{Minimum}] Returns the smaller of two arguments.
  Requires that the argument type implements the \textcode{<} operator.
\item[\vtkm{MinAndMax}] Returns a \vtkm{Vector<T,2>} that represents the minimum and maximum values.
  Requires that the argument type implements the \vtkm{Min} and \vtkm{Max} functions.
\item[\vtkm{BitwiseAnd}] Returns the bitwise and of two arguments.
  Requires that the argument type implements the \textcode{\&} operator.
\item[\vtkm{BitwiseOr}] Returns the bitwise or of two arguments.
  Requires that the argument type implements the \textcode{|} operator.
\item[\vtkm{BitwiseXor}] Returns the bitwise xor of two arguments.
  Requires that the argument type implements the \textcode{\^} operator.
\end{description}

\vtkmlisting{Basic Binary Operator.}{BinaryOperators.cxx}

\index{predicates and operators!binary operators|)}

\subsection{Creating Custom Comparators}
\label{sec:CreatingCustomComparators}

\index{predicates and operators!creating custom comparators|(}

In addition to using the built in operators and predicates, it is possible to create your own custom functors to be used in one of the \vtkmcont{Algorithm}.
Custom operator and predicate functors can be used to apply specific logic used to manipulate your data.
The following example creates a unary predicate that checks if the input is a power of 2.

\vtkmlisting{Custom Unary Predicate Implementation.}{CustomUnaryPredicateImplementation.cxx}
\vtkmlisting{Custom Unary Predicate Usage.}{CustomUnaryPredicateUsage.cxx}

\index{predicates and operators!creating custom comparators|)}

\index{predicates and operators|)}

\section{Device Adapter Algorithms}
\label{sec:DeviceAdapterAlgorithms}

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

VTK-m comes with the templated class \vtkmcont{Algorithm} that
provides a set of algorithms that can be invoked in the control environment
and are run on the execution environment. All algorithms also accept an optional device adapter argument.

\vtkmlisting{Prototype for \protect\vtkmcont{Algorithm}.}{DeviceAdapterAlgorithmPrototype.cxx}

\textidentifier{Algorithm} contains no state. It only has a
set of static methods that implement its algorithms. The following methods
are available.

\begin{didyouknow}
  Many of the following device adapter algorithms take input and output
  \textidentifier{ArrayHandle}s, and these functions will handle their own
  memory management. This means that it is unnecessary to allocate output
  arrays. \index{Allocate} For example, it is unnecessary to call
  \classmember{ArrayHandle}{Allocate} for the output array
  passed to the \classmember{Algorithm}{Copy} method.
\end{didyouknow}

\newcommand{\deviceadapteralgorithmindex}[1]{
  \index{#1}
  \index{algorithm!#1}
  \index{device adapter!algorithm!#1}
}

\subsection{Copy}
\deviceadapteralgorithmindex{copy}

The \classmember{Algorithm}{Copy} method copies data from an input array to an output array.
The copy takes place in the execution environment.

\vtkmlisting{Using the \textcode{Copy} algorithm.}{DeviceAdapterAlgorithmCopy.cxx}

\subsection{CopyIf}
\deviceadapteralgorithmindex{stream compact} \deviceadapteralgorithmindex{copy if}

The \classmember{Algorithm}{CopyIf} method selectively removes values from an array.
The \keyterm{copy if} algorithm is also sometimes referred to as \keyterm{stream compact}.
The first argument, the input, is an \textidentifier{ArrayHandle} to be compacted (by removing elements).
The second argument, the stencil, is an \textidentifier{ArrayHandle} of equal size with flags indicating whether the corresponding input value is to be copied to the output.
The third argument is an output \textidentifier{ArrayHandle} whose length is set to the number of true flags in the stencil and the passed values are put in order to the output array.

\classmember{Algorithm}{CopyIf} also accepts an optional fourth argument that is a unary predicate to determine what values in the stencil (second argument) should be considered true.
See Section~\ref{sec:PredicatesAndOperators} for more information on unary predicates.
The unary predicate determines the true/false value of the stencil that determines whether a given entry is copied.
If no unary predicate is given, then \classmember*{Algorithm}{CopyIf} will copy all values whose stencil value is not equal to 0 (or the closest equivalent to it).
More specifically, it copies values not equal to \vtkm{TypeTraits}[ZeroInitialization].

\vtkmlisting{Using the \textcode{CopyIf} algorithm.}{DeviceAdapterAlgorithmCopyIf.cxx}

\subsection{CopySubRange}
\deviceadapteralgorithmindex{copy sub range}

The \classmember{Algorithm}{CopySubRange} method copies the contents of a section of one \textidentifier{ArrayHandle} to another.
The first argument is the input \textidentifier{ArrayHandle}.
The second argument is the index from which to start copying data.
The third argument is the number of values to copy from the input to the output.
The fourth argument is the output \textidentifier{ArrayHandle}, which will be grown if it is not large enough.
The fifth argument, which is optional, is the index in the output array to start copying data to.
If the output index is not specified, data are copied to the beginning of the output array.

\vtkmlisting{Using the \textcode{CopySubRange} algorithm.}{DeviceAdapterAlgorithmCopySubRange.cxx}

\subsection{LowerBounds}
\deviceadapteralgorithmindex{lower bounds}

The \classmember{Algorithm}{LowerBounds} method takes three arguments.
The first argument is an \textidentifier{ArrayHandle} of sorted values.
The second argument is another \textidentifier{ArrayHandle} of items to find in the first array.
\classmember*{Algorithm}{LowerBounds} find the index of the first item that is greater than or equal to the target value, much like the \textcode{std::lower\_bound} STL algorithm.
The results are returned in an \textidentifier{ArrayHandle} given in the third argument.

There are two specializations of \classmember{Algorithm}{LowerBounds}.
The first takes an additional comparison function that defines the less-than operation.
The second specialization takes only two parameters.
The first is an \textidentifier{ArrayHandle} of sorted \vtkm{Id}s and the second is an \textidentifier{ArrayHandle} of \vtkm{Id} to find in the first list.
The results are written back out to the second array.
This second specialization is useful for inverting index maps.

\vtkmlisting{Using the \textcode{LowerBounds} algorithm.}{DeviceAdapterAlgorithmLowerBounds.cxx}

\subsection{Reduce}
\deviceadapteralgorithmindex{reduce}

The \classmember{Algorithm}{Reduce} method takes an input array, initial value, and a binary function and computes a ``total'' of applying the binary function to all entries in the array.
The provided binary function must be associative (but it need not be commutative).
There is a specialization of \classmember*{Algorithm}{Reduce} that does not take a binary function and computes the sum.

\vtkmlisting{Using the \textcode{Reduce} algorithm.}{DeviceAdapterAlgorithmReduce.cxx}

\subsection{ReduceByKey}
\deviceadapteralgorithmindex{reduce by key}

The \classmember{Algorithm}{ReduceByKey} method works similarly to the \classmember*{Algorithm}{Reduce} method except that it takes an additional array of keys, which must be the same length as the values being reduced.
The arrays are partitioned into segments that have identical adjacent keys, and a separate reduction is performed on each partition.
The unique keys and reduced values are returned in separate arrays.

\vtkmlisting{Using the \textcode{ReduceByKey} algorithm.}{DeviceAdapterAlgorithmReduceByKey.cxx}

\subsection{ScanExclusive}
\deviceadapteralgorithmindex{scan!exclusive}

The \classmember{Algorithm}{ScanExclusive} method takes an input and an output \textidentifier{ArrayHandle} and performs a running sum on the input array.
The first value in the output is always 0.
The second value in the output is the same as the first value in the input.
The third value in the output is the sum of the first two values in the input.
The fourth value in the output is the sum of the first three values of the input, and so on.
\classmember*{Algorithm}{ScanExclusive} returns the sum of all values in the input.
There are two forms of \classmember*{Algorithm}{ScanExclusive}.
The first performs the sum using addition.
The second form accepts a custom binary functor to use as the ``sum'' operator and a custom initial value (instead of 0).

\vtkmlisting{Using the \textcode{ScanExclusive} algorithm.}{DeviceAdapterAlgorithmScanExclusive.cxx}

\subsection{ScanExclusiveByKey}
\deviceadapteralgorithmindex{scan!exclusive by key}

The \classmember{Algorithm}{ScanExclusiveByKey} method works similarly to the \classmember*{Algorithm}{ScanExclusive} method except that it takes an additional array of keys, which must be the same length as the values being scanned.
The arrays are partitioned into segments that have identical adjacent keys, and a separate scan is performed on each partition.
Only the scanned values are returned.

\vtkmlisting{Using \textcode{ScanExclusiveByKey} algorithm.}{DeviceAdapterAlgorithmScanExclusiveByKey.cxx}

\subsection{ScanInclusive}
\deviceadapteralgorithmindex{scan!inclusive}

The \classmember{Algorithm}{ScanInclusive} method takes an input and an output \textidentifier{ArrayHandle} and performs a running sum on the input array.
The first value in the output is the same as the first value in the input.
The second value in the output is the sum of the first two values in the input.
The third value in the output is the sum of the first three values of the input, and so on.
\classmember*{Algorithm}{ScanInclusive} returns the sum of all values in the input.
There are two forms of \classmember*{Algorithm}{ScanInclusive}: one performs the sum using addition whereas the other accepts a custom binary function to use as the sum operator.

\vtkmlisting{Using the \textcode{ScanInclusive} algorithm.}{DeviceAdapterAlgorithmScanInclusive.cxx}

\subsection{ScanInclusiveByKey}
\deviceadapteralgorithmindex{scan!inclusive by key}

The \classmember{Algorithm}{ScanInclusiveByKey} method works similarly to the \classmember*{Algorithm}{ScanInclusive} method except that it takes an additional array of keys, which must be the same length as the values being scanned.
The arrays are partitioned into segments that have identical adjacent keys, and a separate scan is performed on each partition.
Only the scanned values are returned.

\vtkmlisting{Using the \textcode{ScanInclusiveByKey} algorithm.}{DeviceAdapterAlgorithmScanInclusiveByKey.cxx}

\subsection{Schedule}
\deviceadapteralgorithmindex{schedule}

The \classmember{Algorithm}{Schedule} method takes a functor as its first argument and invokes it a number of times specified by the second argument.
It should be assumed that each invocation of the functor occurs on a separate thread although in practice there could be some thread sharing.

There are two versions of the \classmember*{Algorithm}{Schedule} method.
The first version takes a \vtkm{Id} and invokes the functor that number of times.
The second version takes a \vtkm{Id3} and invokes the functor once for every entry in a 3D array of the given dimensions.

The functor is expected to be an object with a const overloaded parentheses operator.
The operator takes as a parameter the index of the invocation, which is either a \vtkm{Id} or a \vtkm{Id3} depending on what version of \classmember*{Algorithm}{Schedule} is being used.
The functor must also subclass \vtkmexec{FunctorBase}, which provides the error handling facilities for the execution environment.
\textidentifier{FunctorBase} contains a public method named \index{RaiseError} \index{errors!execution environment} \classmember*{FunctorBase}{RaiseError} that takes a message and will cause a \vtkmcont{ErrorExecution} exception to be thrown in the control environment.

\subsection{Sort}
\deviceadapteralgorithmindex{sort}

The \classmember{Algorithm}{Sort} method provides an unstable sort of an array.
There are two forms of the \classmember*{Algorithm}{Sort} method.
The first takes an \textidentifier{ArrayHandle} and sorts the values in place.
The second takes an additional argument that is a functor that provides the comparison operation for the sort.

\vtkmlisting{Using the \textcode{Sort} algorithm.}{DeviceAdapterAlgorithmSort.cxx}

\subsection{SortByKey}
\deviceadapteralgorithmindex{sort!by key}

The \classmember{Algorithm}{SortByKey} method works similarly to the \classmember*{Algorithm}{Sort} method except that it takes two \textidentifier{ArrayHandle}s: an array of keys and a corresponding array of values.
The sort orders the array of keys in ascending values and also reorders the values so they remain paired with the same key.
Like \classmember*{Algorithm}{Sort}, \classmember*{Algorithm}{SortByKey} has a version that sorts by the default less-than operator and a version that accepts a custom comparison functor.

\vtkmlisting{Using the \textcode{SortByKey} algorithm.}{DeviceAdapterAlgorithmSortByKey.cxx}

\subsection{Synchronize}
\deviceadapteralgorithmindex{synchronize}

The \textidentifier{Synchronize} method waits for any asynchronous operations running on the device to complete and then returns.

\subsection{Unique}
\deviceadapteralgorithmindex{unique}

The \classmember{Algorithm}{Unique} method removes all duplicate values in an \textidentifier{ArrayHandle}.
The method will only find duplicates if they are adjacent to each other in the array.
The easiest way to ensure that duplicate values are adjacent is to sort the array first.

There are two versions of \classmember*{Algorithm}{Unique}.
The first uses the equals operator to compare entries.
The second accepts a binary functor to perform the comparisons.

\vtkmlisting{Using the \textcode{Unique} algorithm.}{DeviceAdapterAlgorithmUnique.cxx}

\subsection{UpperBounds}
\deviceadapteralgorithmindex{upper bounds}

The \classmember{Algorithm}{UpperBounds} method takes three arguments.
The first argument is an \textidentifier{ArrayHandle} of sorted values.
The second argument is another \textidentifier{ArrayHandle} of items to find in the first array.
\classmember*{Algorithm}{UpperBounds} find the index of the first item that is greater than to the target value, much like the \textcode{std::upper\_bound} STL algorithm.
The results are returned in an \textidentifier{ArrayHandle} given in the third argument.

There are two specializations of \classmember*{Algorithm}{UpperBounds}.
The first takes an additional comparison function that defines the less-than operation.
The second takes only two parameters.
The first is an \textidentifier{ArrayHandle} of sorted \vtkm{Id}s and the second is an \textidentifier{ArrayHandle} of \vtkm{Id}s to find in the first list.
The results are written back out to the second array.
This second specialization is useful for inverting index maps.

\vtkmlisting{Using the \textcode{UpperBounds} algorithm.}{DeviceAdapterAlgorithmUpperBounds.cxx}

\subsection{Specifying the Device Adapter}
\index{algorithm!selecting device}

When you call a method in \vtkmcont{Algorithm}, a device is automatically specified
based on available hardware and the VTK-m state. However, if you want to use a
specific device, you can specify that device by passing either a
\vtkmcont{DeviceAdapterId} or a device adapter tag as the first
argument to any of these methods.

\vtkmlisting{Using the \textcode{DeviceAdapter} with \vtkmcont{Algorithm}.}{DeviceAdapterAlgorithmDeviceAdapter.cxx}

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


\index{device adapter|)}
