% -*- 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.

There are two ways to select a device adapter. The first is to make a
global selection of a default device adapter. The second is to specify a
specific device adapter as a template parameter.

\subsection{Default Device Adapter}
\label{sec:DefaultDeviceAdapter}

A default device adapter tag is specified in
\vtkmheader{vtkm/cont}{DeviceAdapter.h}. If no other
information is given, VTK-m attempts to choose a default device adapter
that is a best fit for the system it is compiled on. VTK-m currently select
the default device adapter with the following sequence of conditions.

\begin{itemize}
\item \index{CUDA}
  If the source code is being compiled by CUDA, the CUDA device is used.
\item \index{Intel Threading Building Blocks} \index{TBB}
  If the compiler does not support CUDA and \VTKm was configured to use Intel Threading Building Blocks, then that device is used.
\item \index{OpenMP} \index{OpenMP}
  If neither CUDA nor TBB is being used and \VTKm was configured to use OpenMP compiler directives, then the OpenMP device is used.
\item \index{serial}
  If no parallel device adapters are found, then VTK-m falls back to a serial device.
\end{itemize}

You can also set the default device adapter specifically by setting the
\vtkmmacro{VTKM\_DEVICE\_ADAPTER} macro. This macro must be set
\emph{before} including any VTK-m files. You can set
\vtkmmacro{VTKM\_DEVICE\_ADAPTER} to any one of the following.

\begin{description}
\item[\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_SERIAL}] Performs all computation on
  the same single thread as the control environment. This device is useful
  for debugging. This device is always available.
\item[\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_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.
\item[\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_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.
\item[\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_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.
\end{description}

These macros provide a useful mechanism for quickly reconfiguring code to
run on different devices. The following example shows a typical block of
code at the top of a source file that could be used for quick
reconfigurations.

\vtkmlisting{Macros to port VTK-m code among different devices}{DefaultDeviceAdapter.cxx}

\begin{didyouknow}
  Filters do not actually use the default device adapter tag. They have a
  more sophisticated device selection mechanism that determines the devices
  available at runtime and will attempt running on multiple devices.
\end{didyouknow}

The default device adapter can always be overridden by specifying a device
adapter tag, as described in the next section. There is actually one more
internal default device adapter named
\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_ERROR} that will cause a compile error if
any component attempts to use the default device adapter. This feature is
most often used in testing code to check when device adapters should be
specified.

\subsection{Specifying Device Adapter Tags}

In addition to setting a global default device adapter, it is possible to
explicitly set which device adapter to use in any feature provided by
VTK-m. This is done by providing a device adapter tag as a template
argument to VTK-m templated objects. 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}

\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:DefaultDeviceTemplateArg} uses this macro on line 4.
\end{commonerrors}

When structuring your code to always specify a particular device adapter,
consider setting the default device adapter (with the
\vtkmmacro{VTKM\_DEVICE\_ADAPTER} macro) to
\vtkmmacro{VTKM\_DEVICE\_ADAPTER\_ERROR}. This will cause the compiler to
produce an error if any object is instantiated with the default device
adapter, which checks to make sure the code properly specifies every device
adapter parameter.

VTK-m also defines a macro named \vtkmmacro{VTKM\_DEFAULT\_DEVICE\_ADAPTER\_TAG}, which can be used in place of an explicit device adapter tag to use the default tag.
This macro is used to create new templates that have template parameters for device adapters that can use the default.
The following example defines a functor to be used with the \classmember[DeviceAdapterAlgorithm]{Schedule} operation (to be described later) that is templated on the device it uses.

\vtkmlisting[ex:DefaultDeviceTemplateArg]{Specifying a default device for template parameters.}{DefaultDeviceTemplateArg.cxx}

\begin{commonerrors}
  There was a time when \VTKm required all user code to specify a device and have a single default device adapter.
  Since then, \VTKm has become more flexible in the device that it uses and instead encourages code to support multiple device adapters specified by a runtime device tracker.
  Thus, the use of \vtkmmacro{VTKM\_DEFAULT\_DEVICE\_ADAPTER\_TAG} is now discouraged and may be removed in future version of \VTKm.
  Instead, use the runtime device tracker described in Section~\ref{sec:RuntimeDeviceTracker}.
\end{commonerrors}

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


\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 traits \classmember{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{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{CanRunOn} for this device will return false until that device is reset.
\item[{\classmember[RuntimeDeviceTracker]{ResetDevice}}]
  Takes a device adapter tag 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{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{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{DeepCopy}.
  There are two versions of \classmember{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.
\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.
\textidentifier{ArrayCopy} takes an optional \textidentifier{RuntimeDeviceTracker} argument, so we can pass in a tracker with the CUDA device disabled.

\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 global runtime device tracker, which can be retrieved with the \vtkmcont{GetGlobalRuntimeDeviceTracker} function.
Specifying a \textidentifier{RuntimeDeviceTracker} is almost always optional, and the global runtime device tracker is used if none is specified.

One of the nice features about having a global 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.
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 global 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:ResetGlobalDevice]{Resetting the global \textidentifier{RuntimeDeviceTracker}.}{ResetGlobalDevice.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:ForceGlobalDevice]{Globally restricting which devices \VTKm uses.}{ForceGlobalDevice.cxx}

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

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


\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 \protect\classmember{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.
A unary predicate is a simple functor with a parentheses argument that has a single argument (in this case, a value of the stencil), and returns true or false.
\fix{When written, replace the previous sentence with a reference to the chapter on predicates and operators.}
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{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 \protect\classmember{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 \protect\classmember{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{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 \protect\classmember{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{Reduce} that does not take a binary function and computes the sum.

\vtkmlisting{Using the \protect\classmember{Reduce} algorithm.}{DeviceAdapterAlgorithmReduce.cxx}

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

The \classmember[Algorithm]{ReduceByKey} method works similarly to the \classmember{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 \protect\classmember{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{ScanExclusive} returns the sum of all values in the input.
There are two forms of \classmember{ScanExclusive}.
The first performs the sum using addition.
The second form other accepts a custom binary function to use as the ``sum'' operator and a custom initial value (instead of 0).

\vtkmlisting{Using the \protect\classmember{ScanExclusive} algorithm.}{DeviceAdapterAlgorithmScanExclusive.cxx}

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

The \classmember[Algorithm]{ScanExclusiveByKey} method works similarly to the \classmember{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 \protect\classmember{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{ScanInclusive} returns the sum of all values in the input.
There are two forms of \classmember{ScanInclusive}: one performs the sum using addition whereas the other accepts a custom binary function to use as the sum operator.

\vtkmlisting{Using the \protect\classmember{ScanInclusive} algorithm.}{DeviceAdapterAlgorithmScanInclusive.cxx}

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

The \classmember[Algorithm]{ScanInclusiveByKey} method works similarly to the \classmember{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 \protect\classmember{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{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{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{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{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 \protect\classmember{Sort} algorithm.}{DeviceAdapterAlgorithmSort.cxx}

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

The \classmember[Algorithm]{SortByKey} method works similarly to the \classmember{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{Sort}, \classmember{SortByKey} has a version that sorts by the default less-than operator and a version that accepts a custom comparison functor.

\vtkmlisting{Using the \classmember{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{Unique}.
The first uses the equals operator to compare entries.
The second accepts a binary functor to perform the comparisons.

\vtkmlisting{Using the \protect\classmember{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{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{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 \protect\classmember{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 \protect\classmember{DeviceAdapter} with \vtkmcont{Algorithm}.}{DeviceAdapterAlgorithmDeviceAdapter.cxx}

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


\index{device adapter|)}
