% -*- latex -*-

\chapter{Device Algorithms}
\label{chap:DeviceAlgorithms}

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

As described in Chapter \ref{chap:GeneralApproach}, \VTKm is built around the concept of a \keyterm{device adapter} that encapsulates the necessary features of each device on which \VTKm can run.
At the core of the device adapter is a collection of basic algorithms optimized for the specific device.
Many features of \VTKm, such as worklets, are built on top of these device algorithms.
Using these higher level structures simplifies programming.

However, it is sometimes desirable to run directly run these algorithms provided by the device adapter.
\VTKm 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.

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

\section{BitFieldToUnorderedSet}
\deviceadapteralgorithmindex{bit field to unordered set}

The \classmember{Algorithm}{BitFieldToUnorderedSet} method creates a unique, unsorted list of indices denoting which bits are set in a bitfield.
For example, running \classmember*{Algorithm}{BitFieldToUnorderedSet} on an input of [0,0,1,0,1,0,1,1,0,1,1,1] would return an array containing [2,4,6,7,9,10,11] or those numbers in some other order.

\vtkmlisting{Using the \textcode{BitFieldToUnorderedSet} algorithm.}{DeviceAdapterAlgorithmBitFieldToUnorderedSet.cxx}

\section{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}

\section{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}

\section{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}

\section{CountSetBits}
\deviceadapteralgorithmindex{count set bits}

The \classmember{Algorithm}{CountSetBits} method returns the total number of set bits in a BitField.
For example, running \classmember*{Algorithm}{BitFieldToUnorderedSet} on an input of [0,0,1,0,1,0,1,1,0,1,1,1] would return 7.

\vtkmlisting{Using the \textcode{CountSetBits} algorithm.}{DeviceAdapterAlgorithmCountSetBits.cxx}

\section{Fill}
\deviceadapteralgorithmindex{fill}

The \classmember{Algorithm}{Fill} methods fill a \textidentifier{BitField} or \textidentifier{ArrayHandle} with a specific pattern of bits/values.
For a \textidentifier{BitField}, it is possible to supply a boolean value or a \textidentifier{WordType}.
For boolean values, all bits are set to 1 if the value is true, 0 if the value is false.
For word masks, the \textidentifier{WordType} must be an unsigned integral type; this value is stamped across the \textidentifier{BitField}.
For a \textidentifier{ArrayHandle}, the entire array is filled with the provided value.
For both types, if a \textidentifier{numValues} argument is provided the array is resized appropriately and filled with the given value.

\vtkmlisting{Using the \textcode{Fill} algorithm.}{DeviceAdapterAlgorithmFill.cxx}

\section{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}

\section{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}

\section{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}

\section{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.
For inclusive scans, the running sum value for position \textit{i} in the input array \textit{includes} the element at position \textit{i}.
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.
If the input and output array are the same, then the operation is done in place.
\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}

\section{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}

\section{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.
For exclusive scans, the running sum value for position \textit{i} in the input array \textit{excludes} the element at position \textit{i}.
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.
If the input and output array are the same, then the operation is done in place.
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}

\section{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}

\section{ScanExtended}
\deviceadapteralgorithmindex{scan extend}

The \classmember{Algorithm}{ScanExtended} computes an extended prefix sum operation on the input \textidentifier{ArrayHandle} and stores it in a provided output \textidentifier{ArrayHandle}.
The output array has length 1 greater than the input array.
\classmember{Algorithm}{ScanExtended} is a combination of the \classmember{Algorithm}{ScanInclusive} and \classmember{Algorithm}{ScanExclusive} methods.
The exclusive scan values are stored in indices $0$ through $size-1$.
The inclusive scan values are stored in indices $1$ through $size$.
The first entry in the resulting array is 0 (or the specified initial value) like with the exclusive scan.
The last entry in the resulting array is the sum total like with the inclusive scan.
Unlike the two referenced methods, \classmember{Algorithm}{ScanExtended} does not return the total sum.
By using an \textidentifier{ArrayHandleView}, arrays containing both inclusive and exclusive scans can be generated from an extended scan with minimal memory usage by referencing the correct indices in the extended scan output.

This algorithm may be more efficient than \classmember{Algorithm}{ScanInclusive} and \classmember{Algorithm}{ScanExclusive} on some devices; this algorithm may be able to avoid copying the total sum to the control environment to return.
\classmember{Algorithm}{ScanExtended} is similar to the STL partial sum function, with the exception that it does not perform a serial summation.
This means that if you have defined a custom plus operator for T it must be associative, or you will get inconsistent results.

The first form performs the sum using addition.
The second form accepts a custom binary functor to use as the operator and a custom initial value (instead of 0).

\vtkmlisting{Using \textcode{ScanExtended} algorithm.}{DeviceAdapterAlgorithmScanExtended.cxx}

\classmember*{Algorithm}{ScanExtended} can be used to create a running sum that is quickly reversible.
If you subtract to consecutive values of a scan you get back the original value.
This is convenient if you need both the input and output of a scan; you can throw away the input and use differences of the output.
However, \classmember*{Algorithm}{ScanInclusive} does not write out the initial value, so you cannot get back the original value at the beginning without a special condition.
Likewise, \classmember*{Algorithm}{ScanExclusive} does not write out the total sum, so you cannot get back the original value at the end without a special condition.
\classmember*{Algorithm}{ScanExtended} solves this problem by extending the array by 1.
The original value for index $i$ can be retrieved by subtracting scan value at index $i$ from the value at index $i+1$ anywhere in the array, including the at the begin and end.
This is particularly useful for storing packed arrays in structures like \vtkmcont{CellSetExplicit} and \vtkmcont{ArrayHandleGroupVecVariable}.

\section{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.

\section{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}

\section{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}

\section{Synchronize}
\deviceadapteralgorithmindex{synchronize}

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

\section{Transform}
\deviceadapteralgorithmindex{transform}

The \classmember{Algorithm}{Transform} method applies a given binary operation function element-wise on two input arrays, storing the result in a provided output array.
The number of elements in the input arrays do not have to be the same; the output array will have the same number of elements as the smaller of the two input arrays.

\vtkmlisting{Using the \textcode{Transform} algorithm.}{DeviceAdapterAlgorithmTransform.cxx}

\section{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}

\section{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}

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


\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} methods discussed earlier in this chapter.
Currently, \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{Vec}\tparams{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|)}
