% -*- latex -*-

\chapter{Worklets}
\label{chap:Worklets}

\index{worklet|(}

The simplest way to implement an algorithm in VTK-m is to create a
\keyterm{worklet}. A worklet is fundamentally a functor that operates on an
element of data. Thus, it is a \textcode{class} or \textcode{struct} that
has an overloaded parenthesis operator (which must be declared
\textcode{const} for thread safety). However, worklets are also embedded
with a significant amount of metadata on how the data should be managed and
how the execution should be structured. This chapter explains the basic
mechanics of defining and using worklets.


\section{Worklet Types}
\label{sec:WorkletTypes}

\index{worklet types|(}

Different operations in visualization can have different data access
patterns, perform different execution flow, and require different
provisions. VTK-m manages these different accesses, execution, and
provisions by grouping visualization algorithms into common classes of
operation and supporting each class with its own worklet type.

Each worklet type has a generic superclass that worklets of that particular
type must inherit. This makes the type of the worklet easy to identify. The
following list describes each worklet type provided by VTK-m and the
superclass that supports it. Details on how to create worklets of each type
are given in Section~\ref{sec:WorkletTypeReference}. It is also possible
to create new worklet types in VTK-m. This is an advanced topic covered in
Chapter~\ref{chap:NewWorkletTypes}.

\begin{description}
\item[Field Map]
  \index{worklet types!field map} \index{field map worklet}
  A worklet deriving \vtkmworklet{WorkletMapField} performs a basic mapping operation that applies a function (the operator in the worklet) on all the field values at a single point or cell and creates a new field value at that same location.
  Although the intention is to operate on some variable over a mesh, a \textidentifier{WorkletMapField} may actually be applied to any array.
  Thus, a field map can be used as a basic \index{map}map operation.

\item[Topology Map]
  \index{worklet types!topology map} \index{topology map worklet}
  A worklet deriving \vtkmworklet{WorkletMapTopology} or one of its sibling classes performs a mapping operation that applies a function (the operator in the worklet) on all elements of a particular type (such as points or cells) and creates a new field for those elements.
  The basic operation is similar to a field map except that in addition to access fields being mapped on, the worklet operation also has access to incident fields.

  There are multiple convenience classes available for the most common types of topology mapping.
  \index{worklet types!point to cell} \index{point to cell worklet} \vtkmworklet{WorkletMapPointToCell} calls the worklet operation for each cell and makes every incident point available.
  This type of map also has access to cell structures and can interpolate point fields.
  \index{worklet types!cell to point} \index{cell to point worklet} Likewise, \vtkmworklet{WorkletMapCellToPoint} calls the worklet operation for each point and makes every incident cell available.

\item[Reduce by Key]
  \index{worklet types!reduce by key} \index{reduce by key worklet}
  A worklet deriving \vtkmworklet{WorkletReduceByKey} operates on an array of keys and one or more associated arrays of values.
  When a reduce by key worklet is invoked, all identical keys are collected and the worklet is called once for each unique key.
  Each worklet invocation is given a \Veclike containing all values associated with the unique key.
  Reduce by key worklets are very useful for combining like items such as shared topology elements or coincident points.
\end{description}

\index{worklet types|)}


\section{Dispatchers}
\label{sec:Dispatchers}

\index{dispatcher|(}

Worklets, both those provided by VTK-m as listed in
Section~\ref{sec:ProvidedWorklets} and ones created by a user as described
in Section~\ref{sec:CreatingWorklets}, are instantiated in the control
environment and run in the execution environment. This means that the
control environment must have a means to \index{invoke}\keyterm{invoke}
worklets that start running in the execution environment.

This invocation is done through a set of
\index{dispatcher}\keyterm{dispatcher} objects. A dispatcher object is an
object in the control environment that has an instance of a worklet and can
invoke that worklet with a set of arguments. There are multiple types of
dispatcher objects, each corresponding to a type of worklet object. All
dispatcher objects have at least two template parameters: the worklet class
being invoked, which is always the first argument, and the device adapter
tag, which is always the last argument and will be set to the default
device adapter if not specified.

All dispatcher classes have a method named \textcode{Invoke} that launches
the worklet in the execution environment.  The arguments to
\textcode{Invoke} must match those expected by the worklet, which is
specified by something called a \keyterm{control signature}. The expected
arguments for worklets provided by VTK-m are documented in
Section~\ref{sec:ProvidedWorklets}. Also, for any worklet, the
\textcode{Invoke} arguments can be gleaned from the control signature,
which is described in Section~\ref{sec:ControlSignature}.

The following is a list of the dispatchers defined in VTK-m. The
dispatcher classes correspond to the list of worklet types specified in
Section~\ref{sec:WorkletTypes}. Many examples of using these dispatchers
are provided in Section~\ref{sec:ProvidedWorklets}.

\begin{description}
\item[\vtkmworklet{DispatcherMapField}]
  The dispatcher used in conjunction with a worklet that subclasses \vtkmworklet{WorkletMapField}.
  The dispatcher class has two template arguments: the worklet type and the device adapter (optional).
\item[\vtkmworklet{DispatcherMapTopology}]
  The dispatcher used in conjunction with a worklet that subclasses \vtkmworklet{WorkletMapTopology} or one of its sibling classes (such as \vtkmworklet{WorkletMapPointToCell}).
  The dispatcher class has two template arguments: the worklet type and the device adapter (optional).
\item[\vtkmworklet{DispatcherReduceByKey}]
  The dispatcher used in conjunction with a worklet that subclasses \vtkmworklet{WorkletReduceByKey}.
  The dispatcher class has two template arguments: the worklet type and the device adapter (optional).
\end{description}

\index{dispatcher|)}

\section{Provided Worklets}
\label{sec:ProvidedWorklets}

\VTKm comes with several worklet implementations.
These worklet implementations for the most part provide the underlying implementations of the filters described in Chapter~\ref{chap:ProvidedFilters}.
The easiest way to execute a filter is to run it from the associated filter class.
However, if your data is not in a \vtkmcont{DataSet} structure or you have knowledge of the specific data types used in the \textidentifier{DataSet}, it might be more efficient to run the worklet directly.
Note that many of the filters use multiple worklets under the covers to implement the full functionality.

The following example demonstrates using the simple \vtkmworklet{PointElevation} worklet directly.

\vtkmlisting{Using the provided \textidentifier{PointElevation} worklet.}{UsePointElevationWorklet.cxx}


\section{Creating Worklets}
\label{sec:CreatingWorklets}

\index{worklet!creating|(}

A worklet is created by implementing a \textcode{class} or
\textcode{struct} with the following features.

\begin{enumerate}
\item
  The class must contain a functional type named \controlsignature, which specifies what arguments are expected when invoking the class with a dispatcher in the control environment.
\item
  The class must contain a functional type named \executionsignature, which specifies how the data gets passed from the arguments in the control environment to the worklet running in the execution environment.
\item
  The class must contain a type named \inputdomain, which identifies which input parameter defines the input domain of the data.
\item
  The class may define a scatter operation to override a 1:1 mapping from input to output.
\item
  The class must contain an implementation of the parenthesis operator, which is the method that is executed in the execution environment.
  The parenthesis operator must be declared \textcode{const}.
\item
  The class must publicly inherit from a base worklet class that specifies the type of operation being performed.
\end{enumerate}

Figure~\ref{fig:WorkletExampleAnnotated} demonstrates all of the required
components of a worklet.

%% \pagebreak
%% \begin{vtkmexample}{Example Code for Cutting/Pasting.}
%% class TriangulateCell : public vtkm::worklet::WorkletMapPointToCell
%% {
%% public:
%%   typedef void ControlSignature(CellSetIn topology,
%%                                 ExecObject tables,
%%                                 FieldOutCell<> connectivityOut);
%%   typedef void ExecutionSignature(CellShape, PointIndices, _2, _3, VisitIndex);
%%   using InputDomain = _1;

%%   using ScatterType = vtkm::worklet::ScatterCounting;
%%   VTKM_CONT
%%   ScatterType GetScatter() const
%%   {
%%     return this->Scatter;
%%   }

%%   template<typename CellShapeTag,
%%            typename ConnectivityInVec,
%%            typename ConnectivityOutVec>
%%   VTKM_EXEC
%%   void operator()(
%%       CellShapeTag shape,
%%       const ConnectivityInVec &connectivityIn,
%%       const internal::TriangulateTablesExecutionObject<DeviceAdapter> &tables,
%%       ConnectivityOutVec &connectivityOut,
%%       vtkm::IdComponent visitIndex) const
%%   {
%% \end{vtkmexample}
%% \pagebreak

\begin{figure}[htb]
  \includegraphics[width=\linewidth]{images/WorkletExampleAnnotated}
  \caption{Annotated example of a worklet declaration.}
  \label{fig:WorkletExampleAnnotated}
\end{figure}

\subsection{Control Signature}
\label{sec:ControlSignature}

\index{control signature|(}
\index{signature!control|(}
\index{worklet!control signature|(}

The control signature of a worklet is a functional type named \controlsignature.
The function prototype matches the calling specification used with the dispatcher \textcode{Invoke} function.

\vtkmlisting[ex:ControlSignature]{A \protect\controlsignature.}{ControlSignature.cxx}

%% \begin{didyouknow}
%%   If the code in Example~\ref{ex:ControlSignature} looks strange, you may be unfamiliar with \index{function types}function types.
%%   In C++, functions have types just as variables and classes do.
%%   A function with a prototype like

%%   \begin{quote}
%%     \textcode{void functionName(int arg1, float arg2);}
%%   \end{quote}

%%   has the type \textcode{void(int,float)}.
%%   \VTKm uses function types like this as a \index{signature}\emph{signature} that defines the structure of a function call.
%%   In the case of the \controlsignature, \VTKm uses the signature to build the interface to the dispatcher, which are discussed in Section~\ref{sec:Dispatchers}.
%% \end{didyouknow}

\begin{didyouknow}
  You may have notices that \VTKm code usually uses the \textcode{using} keyword to define type aliases.
  In contrast \controlsignature (and its companion \executionsignature discussed in Section~\ref{sec:ExecutionSignature}) use the \textcode{typedef} keyword to define the type alias.
  We use \textcode{typedef} rather than \textcode{using} for function signatures because some older compilers (specifically Microsoft Visual Studio 2013 and earlier) do not support the use of \textcode{using} in this case.
\end{didyouknow}

The return type of the function prototype is always \textcode{void} because
the dispatcher \textcode{Invoke} functions do not return values. The
parameters of the function prototype are \index{signature tags}\keyterm{tags}
that identify the type of data that is expected to be passed to invoke.
\controlsignature tags are defined by the worklet type and the various tags
are documented more fully in Section~\ref{sec:WorkletTypeReference}.

By convention, \controlsignature tag names start with the base concept
(e.g. \textsignature{Field} or \textsignature{Topology}) followed by the
domain (e.g. \textsignature{Point} or \textsignature{Cell}) followed by
\textsignature{In} or \textsignature{Out}. For example,
\sigtag{FieldPointIn} would specify values for a field on the points of a
mesh that are used as input (read only). Although they should be there in
most cases, some tag names might leave out the domain or in/out parts if
they are obvious or ambiguous.

\subsubsection{Type List Tags}
\label{sec:TypeListTags}

\index{type list tags|(}
\index{control signature!type list tags|(}

Some tags are templated to have modifiers. For example,
\textsignature{Field} tags have a template argument that is set to a type
list tag defining what types of field data are supported. (See
Section~\ref{sec:TypeLists} for a description of type lists.) In fact, this
type list modifier is so common that the following convenience subtags used
with \textsignature{Field} tags are defined for all worklet types.

\begin{didyouknow}
  Any type list will work as modifiers for \controlsignature tags. However,
  these common type lists are provided for convenience and to make the
  \controlsignature shorter and more readable.
\end{didyouknow}

\begin{description}
  \label{TypeTagList}
\item[\sigtag{AllTypes}] All possible types.
\item[\sigtag{CommonTypes}] The most used types in visualization. This
  includes signed integers and floats that are 32 or 64 bit. It also
  includes 3 dimensional vectors of floats. The same as
  \vtkm{TypeListTagCommon}.
\item[\sigtag{IdType}] Contains the single item \vtkm{Id}. The same as
  \vtkm{TypeListTagId}.
\item[\sigtag{Id2Type}] Contains the single item \vtkm{Id2}. The same as
  \vtkm{TypeListTagId2}.
\item[\sigtag{Id3Type}] Contains the single item \vtkm{Id3}. The same as
  \vtkm{TypeListTagId3}.
\item[\sigtag{Index}] All types used to index arrays. Contains \vtkm{Id},
  \vtkm{Id2}, and \vtkm{Id3}. The same as \vtkm{TypeListTagIndex}.
\item[\sigtag{FieldCommon}] A list containing all the types generally
  used for fields. It is the combination of \sigtag{Scalar}, \sigtag{Vec2},
  \sigtag{Vec3}, and \sigtag{Vec4}. The same as \vtkm{TypeListTagField}.
\item[\sigtag{Scalar}] Types used for scalar fields. Specifically, it
  contains floating point numbers of different widths (i.e. \vtkm{Float32}
  and \vtkm{Float64}). The same as \vtkm{TypeListTagFieldScalar}.
\item[\sigtag{ScalarAll}] All scalar types. It contains signed and unsigned
  integers of widths from 8 to 64 bits. It also contains floats of 32 and
  64 bit widths. The same as \vtkm{TypeListTagScalarAll}.
\item[\sigtag{Vec2}] Types for values of fields with 2 dimensional
  vectors. All these vectors use floating point numbers. The same as
  \vtkm{TypeListTagFieldVec2}.
\item[\sigtag{Vec3}] Types for values of fields with 3 dimensional
  vectors. All these vectors use floating point numbers. The same as
  \vtkm{TypeListTagFieldVec3}.
\item[\sigtag{Vec4}] Types for values of fields with 4 dimensional
  vectors. All these vectors use floating point numbers. The same as
  \vtkm{TypeListTagFieldVec4}.
\item[\sigtag{VecAll}] All \vtkm{Vec} classes with standard integers or
  floating points as components and lengths between 2 and 4. The same as
  \vtkm{TypeListTagVecAll}.
\item[\sigtag{VecCommon}] The most common vector types. It contains all
  \vtkm{Vec} class of size 2 through 4 containing components of unsigned
  bytes, signed 32-bit integers, signed 64-bit integers, 32-bit floats, or
  64-bit floats. The same as \vtkm{TypeListTagVecCommon}.
\end{description}

\index{control signature!type list tags|)}
\index{type list tags|)}

\index{worklet!control signature|)}
\index{signature!control|)}
\index{control signature|)}

\subsection{Execution Signature}
\label{sec:ExecutionSignature}

\index{execution signature|(}
\index{signature!execution|(}
\index{worklet!execution signature|(}

Like the control signature, the execution signature of a worklet is a functional type named \executionsignature.
The function prototype must match the parenthesis operator (described in Section~\ref{sec:WorkletOperator}) in terms of arity and argument semantics.

\vtkmlisting{An \protect\executionsignature.}{ExecutionSignature.cxx}

The arguments of the \executionsignature's function prototype are tags that
define where the data come from. The most common tags are an underscore
followed by a number, such as \sigtagnum{1}, \sigtagnum{2}, etc. These
numbers refer back to the corresponding argument in the
\controlsignature. For example, \sigtagnum{1} means data from the first
control signature argument, \sigtagnum{2} means data from the second
control signature argument, etc.

Unlike the control signature, the execution signature optionally can
declare a return type if the parenthesis operator returns a value. If this
is the case, the return value should be one of the numeric tags
(i.e. \sigtagnum{1}, \sigtagnum{2}, etc.) to refer to one of the data
structures of the control signature. If the parenthesis operator does not
return a value, then \executionsignature should declare the return type as
\textcode{void}.

In addition to the numeric tags, there are other execution signature tags
to represent other types of data. For example, the \sigtag{WorkIndex} tag
identifies the instance of the worklet invocation. Each call to the worklet
function will have a unique \sigtag{WorkIndex}. Other such tags exist and
are described in the following section on worklet types where appropriate.

\index{worklet!execution signature|)}
\index{signature!execution|)}
\index{execution signature|)}

\subsection{Input Domain}
\label{sec:InputDomain}

\index{input domain|(}
\index{worklet!input domain|(}

All worklets represent data parallel operations that are executed over
independent elements in some domain. The type of domain is inherent from
the worklet type, but the size of the domain is dependent on the data being
operated on. One of the arguments given to the dispatcher's
\textcode{Invoke} in the control environment must specify the domain.

A worklet identifies the argument specifying the domain with a
type alias named \inputdomain. The \inputdomain must be
aliased to one of the execution signature numeric tags
(i.e. \sigtagnum{1}, \sigtagnum{2}, etc.). By default, the \inputdomain
points to the first argument, but a worklet can override that to point to
any argument.

\vtkmlisting{An \protect\inputdomain declaration.}{InputDomain.cxx}

Different types of worklets can have different types of domain. For example
a simple field map worklet has a \sigtag{FieldIn} argument as its input
domain, and the size of the input domain is taken from the size of the
associated field array. Likewise, a worklet that maps topology has a
\sigtag{CellSetIn} argument as its input domain, and the size of the input
domain is taken from the cell set.

Specifying the \inputdomain is optional. If it is not specified, the first
argument is assumed to be the input domain.

\index{worklet!input domain|)}
\index{input domain|)}

\subsection{Worklet Operator}
\label{sec:WorkletOperator}

A worklet is fundamentally a functor that operates on an element of data.
Thus, the algorithm that the worklet represents is contained in or called
from the parenthesis operator method.

\vtkmlisting{An overloaded parenthesis operator of a worklet.}{WorkletOperator.cxx}

There are some constraints on the parenthesis operator. First, it must have
the same arity as the \executionsignature, and the types of the parameters
and return must be compatible. Second, because it runs in the execution
environment, it must be declared with the \vtkmexecmodifier (or
\vtkmexeccontmodifier) modifier. Third, the method must be declared
\textcode{const} to help preserve thread safety.

\section{Worklet Type Reference}
\label{sec:WorkletTypeReference}

\index{worklet types|(}

There are multiple worklet types provided by VTK-m, each designed to
support a particular type of operation. Section~\ref{sec:WorkletTypes} gave
a brief overview of each type of worklet. This section gives a much more
detailed reference for each of the worklet types including identifying the
generic superclass that a worklet instance should derive, listing the
signature tags and their meanings, and giving an example of the worklet in
use.

\newcommand{\commoncontrolsignaturetags}{
\item[\sigtag{WholeArrayIn}] This tag represents an array where all entries
  can be read by every worklet invocation. A \sigtag{WholeArrayIn} argument
  expects an \textidentifier{ArrayHandle} in the associated parameter of
  the dispatcher's \textcode{Invoke}. An array portal capable of reading
  from any place in the array is given to the worklet. Whole arrays are
  discussed in detail in Section~\ref{sec:WholeArrays} starting on
  page~\pageref{sec:WholeArrays}.

  \sigtag{WholeArrayIn} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{WholeArrayOut}] This tag represents an array where any entry
  can be written by any worklet invocation. A \sigtag{WholeArrayOut}
  argument expects an \textidentifier{ArrayHandle} in the associated
  parameter of the dispatcher's \textcode{Invoke}. An array portal capable
  of writing to any place in the array is given to the worklet. Developers
  should take care when using writable whole arrays as introducing race
  conditions is possible. Whole arrays are discussed in detail in
  Section~\ref{sec:WholeArrays} starting on page~\pageref{sec:WholeArrays}.

  \sigtag{WholeArrayOut} has a single template parameter that specifies
  what data types are acceptable for the array. The type tags are described
  in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{WholeArrayInOut}] This tag represents an array where any
  entry can be read or written by any worklet invocation. A
  \sigtag{WholeArrayInOut} argument expects an \textidentifier{ArrayHandle}
  in the associated parameter of the dispatcher's \textcode{Invoke}. An
  array portal capable of reading from or writing to any place in the array
  is given to the worklet. Developers should take care when using writable
  whole arrays as introducing race conditions is possible. Whole arrays are
  discussed in detail in Section~\ref{sec:WholeArrays} starting on
  page~\pageref{sec:WholeArrays}.

  \sigtag{WholeArrayInOut} has a single template parameter that specifies
  what data types are acceptable for the array. The type tags are described
  in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{AtomicArrayInOut}]
  This tag represents an array where any entry can be read or written by any worklet invocation.
  A \sigtag{AtomicArrayInOut} argument expects an \textidentifier{ArrayHandle} in the associated parameter of the dispatcher's \textcode{Invoke}.
  A \vtkmexec{AtomicArray} object capable of performing atomic operations to the entries in the array is given to the worklet.
  Atomic arrays can help avoid race conditions but can slow down the running of a parallel algorithm.
  Atomic arrays are discussed in detail in Section~\ref{sec:AtomicArrays} starting on page~\pageref{sec:AtomicArrays}.

\item[\sigtag{ExecObject}] This tag represents an execution object that is
  passed directly from the control environment to the worklet. A
  \sigtag{ExecObject} argument expects a subclass of
  \vtkmexec{ExecutionObjectBase}, and this same object is given to the
  worklet. Execution objects are discussed in detail in
  Section~\ref{sec:ExecutionObjects} starting on
  page~\pageref{sec:ExecutionObjects}.
}

\newcommand{\numericexecutionsignaturetags}{
\item[\sigtagnum{1}, \sigtagnum{2},$\ldots$] These reference the
  corresponding parameter in the \controlsignature.
}

\newcommand{\commonexecutionsignaturetags}{
\item[\sigtag{WorkIndex}]
  This tag produces a \vtkm{Id} that uniquely identifies the invocation of the worklet.
\item[\sigtag{VisitIndex}]
  This tag produces a \vtkm{IdComponent} that uniquely identifies when multiple worklet invocations operate on the same input item, which can happen when defining a worklet with scatter (as described in Section~\ref{sec:WorkletScatter}).
\item[\sigtag{InputIndex}]
  This tag produces a \vtkm{Id} that identifies the index of the input element, which can differ from the \sigtag{WorkIndex} in a worklet with a scatter (as described in Section~\ref{sec:WorkletScatter}).
\item[\sigtag{OutputIndex}]
  This tag produces a \vtkm{Id} that identifies the index of the output element. (This is generally the same as \sigtag{WorkIndex}.)
\item[\sigtag{ThreadIndices}]
  This tag produces an internal object that manages indices and other metadata of the current thread. Thread indices objects are described in Section~\ref{sec:ThreadIndices}, but most users can get the information they need through other signature tags.
}

\subsection{Field Map}

\index{worklet types!field map|(}
\index{field map worklet|(}
\index{map field|(}

A worklet deriving \vtkmworklet{WorkletMapField} performs a basic mapping
operation that applies a function (the operator in the worklet) on all the
field values at a single point or cell and creates a new field value at
that same location. Although the intention is to operate on some variable
over the mesh, a \textidentifier{WorkletMapField} can actually be applied
to any array.

A \textidentifier{WorkletMapField} subclass is invoked with a
\vtkmworklet{DispatcherMapField}. This dispatcher has two template
arguments. The first argument is the type of the worklet subclass. The
second argument, which is optional, is a device adapter tag.

A field map worklet supports the following tags in the parameters of its
\controlsignature.

\begin{description}
\item[\sigtag{FieldIn}] This tag represents an input field. A
  \sigtag{FieldIn} argument expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  single value out of this array.

  \sigtag{FieldIn} has a single template parameter that specifies what data
  types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on
  page~\pageref{TypeTagList}.

  The worklet's \inputdomain can be set to a \sigtag{FieldIn} argument. In
  this case, the input domain will be the size of the array.

\item[\sigtag{FieldOut}] This tag represents an output field. A
  \sigtag{FieldOut} argument expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. The array is resized before scheduling
  begins, and each invocation of the worklet sets a single value in the
  array.

  \sigtag{FieldOut} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on
  page~\pageref{TypeTagList}.

\item[\sigtag{FieldInOut}] This tag represents field that is both an input
  and an output. A \sigtag{FieldInOut} argument expects an
  \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in
  the associated parameter of the dispatcher's \textcode{Invoke}. Each
  invocation of the worklet gets a single value out of this array, which is
  replaced by the resulting value after the worklet completes.

  \sigtag{FieldInOut} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on
  page~\pageref{TypeTagList}.

  The worklet's \inputdomain can be set to a \sigtag{FieldInOut} argument. In
  this case, the input domain will be the size of the array.

  \commoncontrolsignaturetags
\end{description}

A field map worklet supports the following tags in the parameters of its
\executionsignature.

\begin{description}
  \numericexecutionsignaturetags

  \commonexecutionsignaturetags
\end{description}

Field maps most commonly perform basic calculator arithmetic, as
demonstrated in the following example.

\vtkmlisting[ex:UseWorkletMapField]{Implementation and use of a field map worklet.}{UseWorkletMapField.cxx}

\begin{didyouknow}
  Example~\ref{ex:UseWorkletMapField} is using an informal but helpful convention where worklets are defined inside another class that also contains a static method named \textcode{Run}\index{Run method} that runs the worklet using a common set of operations.
  The \textcode{Run} method helps make clear the intention and use of the worklet.
  This is especially important for operations that require a series of worklet invocations that might be non-obvious.
\end{didyouknow}

Although simple, the \textidentifier{WorkletMapField} worklet type can be
used (and abused) as a general parallel-for/scheduling mechanism. In
particular, the \sigtag{WorkIndex} execution signature tag can be used to
get a unique index, the \textsignature{WholeArray}* tags can be used to get
random access to arrays, and the \sigtag{ExecObject} control signature tag
can be used to pass execution objects directly to the worklet. Whole arrays
and execution objects are talked about in more detail in Sections
\ref{sec:WholeArrays} and \ref{sec:ExecutionObjects}, respectively, in more
detail, but here is a simple example that uses the random access of
\sigtag{WholeArrayOut} to make a worklet that copies an array
in reverse order.

\vtkmlisting[ex:WholeArray]{Leveraging field maps and field maps for general processing.}{RandomArrayAccess.cxx}

\index{map field|)}
\index{field map worklet|)}
\index{worklet types!field map|)}

\subsection{Topology Map}
\label{sec:TopologyMaps}

A topology map performs a mapping that it applies a function (the
operator in the worklet) on all the elements of a \textidentifier{DataSet}
of a particular type (i.e. point, edge, face, or cell). While operating on
the element, the worklet has access to data from all incident elements of
another type.

There are several versions of topology maps that differ in what type of
element being mapped from and what type of element being mapped to. The
subsequent sections describe these different variations of the topology
maps. Regardless of their names, they are all defined in
\vtkmheader{vtkm/worklet}{WorkletMapTopology.h} and are all invoked with
\vtkmworklet{DispatcherMapTopology}.

\subsubsection{Point to Cell Map}
\label{sec:WorkletMapPointToCell}

\index{worklet types!point to cell map|(}
\index{point to cell map worklet|(}
\index{map point to cell|(}

A worklet deriving \vtkmworklet{WorkletMapPointToCell} performs a mapping
operation that applies a function (the operator in the worklet) on all the
cells of a \textidentifier{DataSet}. While operating on the cell, the
worklet has access to fields associated both with the cell and with all
incident points. Additionally, the worklet can get information about the
structure of the cell and can perform operations like interpolation on it.

A \textidentifier{WorkletMapPointToCell} subclass is invoked with a
\vtkmworklet{DispatcherMapTopology}. This dispatcher has two template
arguments. The first argument is the type of the worklet subclass. The
second argument, which is optional, is a device adapter tag.

A point to cell map worklet supports the following tags in the parameters
of its \controlsignature.

\begin{description}
\item[\sigtag{CellSetIn}] This tag represents the cell set that defines
  the collection of cells the map will operate on. A \sigtag{CellSetIn}
  argument expects a \textidentifier{CellSet} subclass or a
  \textidentifier{DynamicCellSet} in the associated parameter of the
  dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  cell shape tag. (Cell shapes and the operations you can do with cells are
  discussed in Chapter~\ref{chap:WorkingWithCells}.)

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's
  \inputdomain must be set to this argument.

\item[\sigtag{FieldInPoint}] This tag represents an input field that is
  associated with the points. A \sigtag{FieldInPoint} argument expects an
  \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in
  the associated parameter of the dispatcher's \textcode{Invoke}. The size
  of the array must be exactly the number of points.

  Each invocation of the worklet gets a \Veclike object containing the
  field values for all the points incident with the cell being visited. The
  order of the entries is consistent with the defined order of the vertices
  for the visited cell's shape. If the field is a vector field, then the
  provided object is a Vec of Vecs.

  \sigtag{FieldInPoint} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldInCell}] This tag represents an input field that is
  associated with the cells. A \sigtag{FieldInCell} argument expects an
  \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in
  the associated parameter of the dispatcher's \textcode{Invoke}. The size
  of the array must be exactly the number of cells. Each invocation of the
  worklet gets a single value out of this array.

  \sigtag{FieldInCell} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldOutCell}] This tag represents an output field, which is
  necessarily associated with cells. A \sigtag{FieldOutCell} argument
  expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. The array is resized before scheduling
  begins, and each invocation of the worklet sets a single value in the
  array.

  \sigtag{FieldOutCell} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  \sigtag{FieldOut} is an alias for \sigtag{FieldOutCell} (since output
  arrays can only be defined on cells).

\item[\sigtag{FieldInOutCell}] This tag represents field that is both an
  input and an output, which is necessarily associated with cells. A
  \sigtag{FieldInOutCell} argument expects an \textidentifier{ArrayHandle}
  or a \textidentifier{DynamicArrayHandle} in the associated parameter of
  the dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  single value out of this array, which is replaced by the resulting value
  after the worklet completes.

  \sigtag{FieldInOutCell} has a single template parameter that specifies
  what data types are acceptable for the array. The type tags are described
  in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  \sigtag{FieldInOut} is an alias for \sigtag{FieldInOutCell} (since output
  arrays can only be defined on cells).

  \commoncontrolsignaturetags
\end{description}

A field map worklet supports the following tags in the parameters of its
\executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellShape}] This tag produces a shape tag corresponding to
  the shape of the visited cell. (Cell shapes and the operations you can do
  with cells are discussed in
  Chapter~\ref{chap:WorkingWithCells}.) This is the
  same value that gets provided if you reference the
  \textsignature{CellSetIn} parameter.

\item[\sigtag{PointCount}] This tag produces a \vtkm{IdComponent} equal to
  the number of points incident on the cell being visited. The Vecs
  provided from a \textsignature{FieldInPoint} parameter will be the same
  size as \sigtag{PointCount}.

\item[\sigtag{PointIndices}] This tag produces a \Veclike object of
  \vtkm{Id}s giving the indices for all incident points. Like values from a
  \textsignature{FieldInPoint} parameter, the order of the entries is
  consistent with the defined order of the vertices for the visited cell's
  shape.

  \commonexecutionsignaturetags
\end{description}

Point to cell field maps are a powerful construct that allow you to interpolate point fields throughout the space of the data set.
See Chapter~\ref{chap:WorkingWithCells} for a description on how to work with the cell information provided to the worklet.
The following example provides a simple demonstration that finds the geometric center of each cell by interpolating the point coordinates to the cell centers.

\vtkmlisting[ex:UseWorkletMapPointToCell]{Implementation and use of a map point to cell worklet.}{UseWorkletMapPointToCell.cxx}

\index{map point to cell|)}
\index{point to cell map worklet|)}
\index{worklet types!point to cell map|)}

\subsubsection{Cell To Point Map}
\label{sec:WorkletMapCellToPoint}

\index{worklet types!cell to point map|(}
\index{cell to point map worklet|(}
\index{map cell to point|(}

A worklet deriving \vtkmworklet{WorkletMapCellToPoint} performs a mapping
operation that applies a function (the operator in the worklet) on all the
points of a \textidentifier{DataSet}. While operating on the point, the
worklet has access to fields associated both with the point and with all
incident cells.

A \textidentifier{WorkletMapCellToPoint} subclass is invoked with a
\vtkmworklet{DispatcherMapTopology}. This dispatcher has two template
arguments. The first argument is the type of the worklet subclass. The
second argument, which is optional, is a device adapter tag.

A cell to point map worklet supports the following tags in the parameters
of its \controlsignature.

\begin{description}
\item[\sigtag{CellSetIn}] This tag represents the cell set that defines
  the collection of points the map will operate on. A \sigtag{CellSetIn}
  argument expects a \textidentifier{CellSet} subclass or a
  \textidentifier{DynamicCellSet} in the associated parameter of the
  dispatcher's \textcode{Invoke}.

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's
  \inputdomain must be set to this argument.

\item[\sigtag{FieldInCell}] This tag represents an input field that is
  associated with the cells. A \sigtag{FieldInCell} argument expects an
  \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in
  the associated parameter of the dispatcher's \textcode{Invoke}. The size
  of the array must be exactly the number of cells.

  Each invocation of the worklet gets a \Veclike object containing the
  field values for all the cells incident with the point being visited. The
  order of the entries is arbitrary but will be consistent with the values
  of all other \sigtag{FieldInCell} arguments for the same worklet
  invocation. If the field is a vector field, then the provided object is a
  Vec of Vecs.

  \sigtag{FieldInCell} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldInPoint}] This tag represents an input field that is
  associated with the points. A \sigtag{FieldInPoint} argument expects an
  \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in
  the associated parameter of the dispatcher's \textcode{Invoke}. The size
  of the array must be exactly the number of points. Each invocation of the
  worklet gets a single value out of this array.

  \sigtag{FieldInPoint} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldOutPoint}] This tag represents an output field, which is
  necessarily associated with points. A \sigtag{FieldOutPoint} argument
  expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. The array is resized before scheduling
  begins, and each invocation of the worklet sets a single value in the
  array.

  \sigtag{FieldOutPoint} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  \sigtag{FieldOut} is an alias for \sigtag{FieldOutPoint} (since output
  arrays can only be defined on points).

\item[\sigtag{FieldInOutPoint}] This tag represents field that is both an
  input and an output, which is necessarily associated with points. A
  \sigtag{FieldInOutPoint} argument expects an \textidentifier{ArrayHandle}
  or a \textidentifier{DynamicArrayHandle} in the associated parameter of
  the dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  single value out of this array, which is replaced by the resulting value
  after the worklet completes.

  \sigtag{FieldInOutPoint} has a single template parameter that specifies
  what data types are acceptable for the array. The type tags are described
  in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  \sigtag{FieldInOut} is an alias for \sigtag{FieldInOutPoint} (since output
  arrays can only be defined on points).

  \commoncontrolsignaturetags
\end{description}

A field map worklet supports the following tags in the parameters of its
\executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellCount}] This tag produces a \vtkm{IdComponent} equal to
  the number of cells incident on the point being visited. The Vecs
  provided from a \textsignature{FieldInCell} parameter will be the same
  size as \sigtag{CellCount}.

\item[\sigtag{CellIndices}] This tag produces a \Veclike object of
  \vtkm{Id}s giving the indices for all incident cells. The
  order of the entries is arbitrary but will be consistent with the values
  of all other \textsignature{FieldInCell} arguments for the same worklet
  invocation.

  \commonexecutionsignaturetags
\end{description}

Cell to point field maps are typically used for converting fields
associated with cells to points so that they can be interpolated. The
following example does a simple averaging, but you can also implement other
strategies such as a volume weighted average.

\vtkmlisting{Implementation and use of a map cell to point worklet.}{UseWorkletMapCellToPoint.cxx}

\index{map cell to point|)}
\index{cell to point map worklet|)}
\index{worklet types!cell to point map|)}

\subsubsection{General Topology Maps}
\label{sec:WorkletMapTopology}

\index{worklet types!topology map|(}
\index{topology map worklet|(}
\index{map topology|(}

A worklet deriving \vtkmworklet{WorkletMapTopology} performs a mapping
operation that applies a function (the operator in the worklet) on all the
elements of a specified type from a \textidentifier{DataSet}. While
operating on each element, the worklet has access to fields associated both
with that element and with all incident elements of a different specified
type.

The \textidentifier{WorkletMapTopology} class is a template with two
template parameters. The first template parameter specifies the ``from''
topology element, and the second template parameter specifies the ``to''
topology element. The worklet is scheduled such that each instance is
associated with a particular ``to'' topology element and has access to
incident ``from'' topology elements.

\index{topology element tag|(}
\index{tag!topology element|(}

These from and to topology elements are specified with topology element
tags, which are defined in the \vtkmheader{vtkm}{TopologyElementTag.h}
header file. The available topology element tags are
\vtkm{TopologyElementTagCell}, \vtkm{TopologyElementTagPoint},
\vtkm{TopologyElementTagEdge}, and \vtkm{TopologyElementTagFace}, which
represent the cell, point, edge, and face elements, respectively.

\index{topology element tag|)}
\index{tag!topology element|)}

\textidentifier{WorkletMapTopology} is a generic form of a topology map,
and it can perform identically to the aforementioned forms of topology map
with the correct template parameters. For example,
\begin{quote}
  \vtkmworklet{WorkletMapTopology}\textcode{<}%
  \vtkm{TopologyElementTagPoint}\textcode{, }%
  \vtkm{TopologyElementTagCell}\textcode{>}
\end{quote}
is equivalent to the \vtkmworklet{WorkletMapPointToCell} class except the
signature tags have different names. The names used in the specific
topology map superclasses (such as \textidentifier{WorkletMapPointToCell})
tend to be easier to read and are thus preferable. However, the generic
\textidentifier{WorkletMapTopology} is available for topology combinations
without a specific superclass or to support more general mappings in a
worklet.

The general topology map worklet supports the following tags in the
parameters of its \controlsignature, which are equivalent to tags in the
other topology maps but with different (more general) names.

\begin{description}
\item[\sigtag{CellSetIn}] This tag represents the cell set that defines
  the collection of elements the map will operate on. A \sigtag{CellSetIn}
  argument expects a \textidentifier{CellSet} subclass or a
  \textidentifier{DynamicCellSet} in the associated parameter of the
  dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  cell shape tag. (Cell shapes and the operations you can do with cells are
  discussed in Chapter~\ref{chap:WorkingWithCells}.)

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's
  \inputdomain must be set to this argument.

\item[\sigtag{FieldInFrom}] This tag represents an input field that is
  associated with the ``from'' elements. A \sigtag{FieldInFrom} argument
  expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. The size of the array must be exactly the
  number of ``from'' elements.

  Each invocation of the worklet gets a \Veclike object containing the
  field values for all the ``from'' elements incident with the ``to''
  element being visited. If the field is a vector field, then the provided
  object is a Vec of Vecs.

  \sigtag{FieldInFrom} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldInTo}] This tag represents an input field that is
  associated with the ``to'' element. A \sigtag{FieldInTo} argument expects
  an \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle}
  in the associated parameter of the dispatcher's \textcode{Invoke}. The
  size of the array must be exactly the number of cells. Each invocation of
  the worklet gets a single value out of this array.

  \sigtag{FieldInTo} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldOut}] This tag represents an output field, which is
  necessarily associated with ``to'' elements. A \sigtag{FieldOut} argument
  expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. The array is resized before scheduling
  begins, and each invocation of the worklet sets a single value in the
  array.

  \sigtag{FieldOut} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{FieldInOut}] This tag represents field that is both an input
  and an output, which is necessarily associated with ``to'' elements. A
  \sigtag{FieldInOut} argument expects an \textidentifier{ArrayHandle} or a
  \textidentifier{DynamicArrayHandle} in the associated parameter of the
  dispatcher's \textcode{Invoke}. Each invocation of the worklet gets a
  single value out of this array, which is replaced by the resulting value
  after the worklet completes.

  \sigtag{FieldInOut} has a single template parameter that specifies what
  data types are acceptable for the array. The type tags are described in
  Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  \commoncontrolsignaturetags
\end{description}

A general topology map worklet supports the following tags in the
parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellShape}] This tag produces a shape tag corresponding to
  the shape of the visited ``to'' element. (Cell shapes and the operations
  you can do with cells are discussed in
  Chapter~\ref{chap:WorkingWithCells}.) This is the
  same value that gets provided if you reference the
  \textsignature{CellSetIn} parameter.

  If the ``to'' element is cells, the \sigtag{CellShape} clearly will match
  the shape of each cell. Other elements will have shapes to match their
  structures. Points have vertex shapes, edges have line shapes, and faces
  have some type of polygonal shape.

\item[\sigtag{FromCount}] This tag produces a \vtkm{IdComponent} equal to
  the number of ``from'' elements incident on the ``to'' element being
  visited. The Vecs provided from a \textsignature{FieldInFrom} parameter
  will be the same size as \sigtag{FromCount}.

\item[\sigtag{FromIndices}] This tag produces a \Veclike object of
  \vtkm{Id}s giving the indices for all incident ``from'' elements. The
  order of the entries is consistent with the values of all other
  \textsignature{FieldInFrom} arguments for the same worklet invocation.

  \commonexecutionsignaturetags
\end{description}

\index{map topology|)}
\index{topology map worklet|)}
\index{worklet types!topology map|)}

\subsection{Reduce by Key}
\label{sec:ReduceByKey}

\index{worklet types!reduce by key|(}
\index{reduce by key worklet|(}

A worklet deriving \vtkmworklet{WorkletReduceByKey} operates on an array of keys and one or more associated arrays of values.
When a reduce by key worklet is invoked, all identical keys are collected and the worklet is called once for each unique key.
Each worklet invocation is given a \Veclike containing all values associated with the unique key.
Reduce by key worklets are very useful for combining like items such as shared topology elements or coincident points.

\begin{figure}[htb]
  \centering
  \includegraphics{images/ReduceByKeys}
  \caption{The collection of values for a reduce by key worklet.}
  \label{fig:ReduceByKey}
\end{figure}

Figure~\ref{fig:ReduceByKey} show a pictorial representation of how \VTKm collects data for a reduce by key worklet.
All calls to a reduce by key worklet has exactly one array of keys.
The key array in this example has 4 unique keys: 0, 1, 2, 4.
These 4 unique keys will result in 4 calls to the worklet function.
This example also has 2 arrays of values associated with the keys.
(A reduce by keys worklet can have any number of values arrays.)

Within the dispatch of the worklet, all these common keys will be collected with their associated values.
The parenthesis operator of the worklet will be called once per each unique key.
The worklet call will be given a \Veclike containing all values that have the key.

A \textidentifier{WorkletReduceByKey} subclass is invoked with a \vtkmworklet{DispatcherReduceByKey}.
This dispatcher has two template arguments.
The first argument is the type of the worklet subclass.
The second argument, which is optional, is a device adapter tag.

A reduce by key worklet supports the following tags in the parameters of its \controlsignature.

\begin{description}
\item[\sigtag{KeysIn}]
  This tag represents the input keys.
  A \sigtag{KeysIn} argument expects a \vtkmworklet{Keys} object in the associated parameter of the dispatcher's \textcode{Invoke}.
  The \textidentifier{Keys} object, which wraps around an \textidentifier{ArrayHandle} containing the keys and manages the auxiliary structures for collecting like keys, is described later in this section.

  Each invocation of the worklet gets a single unique key.

  A \textidentifier{WorkletReduceByKey} object must have exactly one \sigtag{KeysIn} parameter in its \controlsignature, and the \inputdomain must point to the \sigtag{KeysIn} parameter.

\item[\sigtag{ValuesIn}]
  This tag represents a set of input values that are associated with the keys.
  A \sigtag{ValuesIn} argument expects an \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in the associated parameter of the dispatcher's \textcode{Invoke}.
  The number of values in this array must be equal to the size of the array used with the \sigtag{KeysIn} argument.
  Each invocation of the worklet gets a \Veclike object containing all the values associated with the unique key.

  \sigtag{ValuesIn} has a single template parameter that specifies what data types are acceptable for the array.
  The type tags are described in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{ValuesInOut}]
  This tag behaves the same as \sigtag{ValuesIn} except that the worklet may write values back into the \Veclike object, and these values will be placed back in their original locations in the array.
  Use of \sigtag{ValuesInOut} is rare.

\item[\sigtag{ValuesOut}]
  This tag behaves the same as \sigtag{ValuesInOut} except that the array is resized appropriately and no input values are passed to the worklet.
  As with \sigtag{ValuesInOut}, values the worklet writes to its \Veclike object get placed in the location of the original arrays.
  Use of \sigtag{ValuesOut} is rare.

\item[\sigtag{ReducedValuesOut}]
  This tag represents the resulting reduced values.
  A \sigtag{ReducedValuesOut} argument expects an \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in the associated parameter of the dispatcher's \textcode{Invoke}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

  \sigtag{ReducedValuesOut} has a single template parameter that specifies what data types are acceptable for the array.
  The type tags are described in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

\item[\sigtag{ReducedValuesIn}]
  This tag represents input values that come from (typically) from a previous invocation of a reduce by key.
  A \sigtag{ReducedValuesOut} argument expects an \textidentifier{ArrayHandle} or a \textidentifier{DynamicArrayHandle} in the associated parameter of the dispatcher's \textcode{Invoke}.
  The number of values in the array must equal the number of \emph{unique} keys.

  \sigtag{ReducedValuesIn} has a single template parameter that specifies what data types are acceptable for the array.
  The type tags are described in Section~\ref{sec:TypeListTags} starting on page~\pageref{TypeTagList}.

  A \sigtag{ReducedValuesIn} argument is usually used to pass reduced values from one invocation of a reduce by key worklet to another invocation of a reduced by key worklet such as in an algorithm that requires iterative steps.
\end{description}

A reduce by key worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{ValueCount}]
  This tag produces a \vtkm{IdComponent} that is equal to the number of times the key associated with this call to the worklet occurs in the input.
  This is the same size as the \Veclike objects provided by \sigtag{ValuesIn} arguments.

  \commonexecutionsignaturetags
\end{description}

As stated earlier, the reduce by key worklet is useful for collected like values.
To demonstrate the reduce by key worklet, we will create a simple mechanism to generate a \index{histogram}histogram in parallel.
(\VTKm comes with its own histogram implementation, but we create our own version here for a simple example.)
The way we can use the reduce by key worklet to compute a histogram is to first identify which bin of the histogram each value is in, and then use the bin identifiers as the keys to collect the information.
To help with this example, we will first create a helper class named \textcode{BinScalars} that helps us manage the bins.

\vtkmlisting{A helper class to manage histogram bins.}{BinScalars.cxx}

Using this helper class, we can easily create a simple map worklet that takes values, identifies a bin, and writes that result out to an array that can be used as keys.

\vtkmlisting{A simple map worklet to identify histogram bins, which will be used as keys.}{IdentifyBins.cxx}

Once you generate an array to be used as keys, you need to make a \vtkmworklet{Keys} object.
The \textidentifier{Keys} object is what will be passed to the invoke of the reduce by keys dispatcher.
This of course happens in the control environment after calling the dispatcher for our worklet for generating the keys.

\vtkmlisting{Creating a \protect\vtkmworklet{Keys} object.}{CreateKeysObject.cxx}

Now that we have our keys, we are finally ready for our reduce by key worklet.
A histogram is simply a count of the number of elements in a bin.
In this case, we do not really need any values for the keys.
We just need the size of the bin, which can be identified with the internally calculated \sigtag{ValueCount}.

A complication we run into with this histogram filter is that it is possible for a bin to be empty.
If a bin is empty, there will be no key associated with that bin, and the reduce by key dispatcher will not call the worklet for that bin/key.
To manage this case, we have to initialize an array with 0's and then fill in the non-zero entities with our reduce by key worklet.
We can find the appropriate entry into the array by using the key, which is actually the bin identifier, which doubles as an index into the histogram.
The following example gives the implementation for the reduce by key worklet that fills in positive values of the histogram.

\vtkmlisting{A reduce by key worklet to write histogram bin counts.}{CountBins.cxx}

The previous example demonstrates the basic usage of the reduce by key worklet to count common keys.
A more common use case is to collect values associated with those keys, do an operation on those values, and provide a ``reduced'' value for each unique key.
The following example demonstrates such an operation by providing a worklet that finds the average of all values in a particular bin rather than counting them.

\vtkmlisting{A worklet that averages all values with a common key.}{AverageBins.cxx}

To complete the code required to average all values that fall into the same bin, the following example shows the full code required to invoke such a worklet.
Note that this example repeats much of the previous examples, but shows it in a more complete context.

\vtkmlisting{Using a reduce by key worklet to average values falling into the same bin.}{CombineSimilarValues.cxx}

\index{reduce by key worklet|)}
\index{worklet types!reduce by key|)}


\index{worklet types|)}


\section{Whole Arrays}
\label{sec:WholeArrays}

\index{whole array|(}
\index{worklet!whole array|(}
\index{control signature!whole array|(}

As documented in Section~\ref{sec:WorkletTypeReference}, each worklet type
has a set of parameter types that can be used to pass data to and from the
worklet invocation. But what happens if you want to pass data that cannot
be expressed in these predefined mechanisms.
Chapter~\ref{chap:NewWorkletTypes} describes how to create completely new
worklet types and parameter tags. However, designing such a system for a
one-time use is overkill.

Instead, all VTK-m worklets provide a trio of mechanisms that allow you to pass arbitrary data to a worklet.
In this section, we will explore a \keyterm{whole array} argument that provides random access to an entire array.
In a later section we describe an even more general mechanism to describe any execution object.

\begin{commonerrors}
  The \VTKm worklet dispatching mechanism performs many safety checks to prevent race conditions across concurrently running worklets.
  Using a whole array within a worklet circumvents this guarantee of safety, so be careful when using whole arrays, especially when writing to whole arrays.
\end{commonerrors}

A whole array is declared by adding a \sigtag{WholeArrayIn}, a \sigtag{WholeArrayInOut}, or a \sigtag{WholeArrayOut} to the \controlsignature.
The corresponding argument to the dispatcher's \textcode{Invoke} should be an \textidentifier{ArrayHandle}.
The \textidentifier{ArrayHandle} must already be allocated in all cases, including when using \sigtag{WholeArrayOut}.
When the data are passed to the operator of the worklet, it is passed as an array portal object.
This means that the worklet can access any entry in the array with \textcode{Get} and/or \textcode{Set} methods.

We have already seen a demonstration of using a whole array in
Example~\ref{ex:WholeArray} to perform a simple array copy. Here we will
construct a more thorough example of building functionality that requires
random array access.

Let's say we want to measure the quality of triangles in a mesh. A
common method for doing this is using the equation
\begin{equation*}
  q = \frac{4a\sqrt{3}}{h_1^2 + h_2^2 + h_3^2}
\end{equation*}
where $a$ is the area of the triangle and $h_1$, $h_2$, and $h_3$ are the
lengths of the sides. We can easily compute this in a cell to point map,
but what if we want to speed up the computations by reducing precision?
After all, we probably only care if the triangle is good, reasonable, or
bad. So instead, let's build a lookup table and then retrieve the triangle
quality from that lookup table based on its sides.

The following example demonstrates creating such a table lookup in an array
and using a worklet argument tagged with \sigtag{WholeArrayIn} to make it
accessible.

\vtkmlisting[ex:TriQualityWholeArray]{Using \protect\sigtag{WholeArrayIn} to access a lookup table in a worklet.}{TriangleQualityWholeArray.cxx}


\index{control signature!whole array|)}
\index{worklet!whole array|)}
\index{whole array|)}

\section{Atomic Arrays}
\label{sec:AtomicArrays}

\index{atomic array|(}
\index{worklet!atomic array|(}
\index{control signature!atomic array|(}

One of the problems with writing to whole arrays is that it is difficult to coordinate the access to an array from multiple threads.
If multiple threads are going to write to a common index of an array, then you will probably need to use an \keyterm{atomic array}.

An atomic array allows random access into an array of data, similar to a whole array.
However, the operations on the values in the atomic array allow you to perform an operation that modifies its value that is guaranteed complete without being interrupted and potentially corrupted.

\begin{commonerrors}
  Due to limitations in available atomic operations, atomic arrays can currently only contain \vtkm{Float32} or \vtkm{Float64} values.
\end{commonerrors}

To use an array as an atomic array, first add the \sigtag{AtomicArrayInOut} tag to the worklet's \controlsignature.
The corresponding argument to the dispatcher's \textcode{Invoke} should be an \textidentifier{ArrayHandle}, which must already be allocated and initialized with values.

When the data are passed to the operator of the worklet, it is passed in a \vtkmexec{AtomicArray} structure.
\textidentifier{AtomicArray} has two important methods:
\begin{description}
\item[\textcode{Add}]
  Takes as arguments an index and a value.
  The entry in the array corresponding to the index will have the value added to it.
  If multiple threads attempt to add to the same index in the array, the requests will be serialized so that the final result is the sum of all the additions.
\item[\textcode{CompareAndSwap}]
  Takes as arguments an index, a new value, and an old value.
  If the entry in the array corresponding to the index has the same value as the ``old value,'' then it is changed to the ``new value'' and the original value is return from the method.
  If the entry in the array is not the same as the ``old value,'' then nothing happens to the array and the value that is actually stored in the array is returned.
  If multiple threads attempt to compare and swap to the same index in the array, the requests are serialized.
\end{description}

\begin{commonerrors}
  Atomic arrays help resolve hazards in parallel algorithms, but they come at a cost.
  Atomic operations are more costly than non-thread-safe ones, and they can slow a parallel program immensely if used incorrectly.
\end{commonerrors}

\index{histogram}
The following example uses an atomic array to count the bins in a histogram.
It does this by making the array of histogram bins an atomic array and then using an atomic add.
Note that this is not the fastest way to create a histogram.
We gave an implementation in Section~\ref{sec:ReduceByKey} that is generally faster (unless your histogram happens to be very sparse).
\VTKm also comes with a histogram worklet that uses a similar approach.

\vtkmlisting{Using \protect\sigtag{AtomicArrayInOut} to count histogram bins in a worklet.}{SimpleHistogram.cxx}

\index{control signature!atomic array|)}
\index{worklet!atomic array|)}
\index{atomic array|)}

\section{Whole Cell Sets}
\label{sec:WholeCellSets}

\index{whole cell set|(}
\index{cell set!whole|(}
\index{worklet!whole cell set|(}
\index{control signature!whole cell set|(}

Section~\ref{sec:TopologyMaps} describes how to make a topology map filter that performs an operation on cell sets.
The worklet has access to a single cell element (such as point or cell) and its immediate connections.
But there are cases when you need more general queries on a topology.
For example, you might need more detailed information than the topology map gives or you might need to trace connections from one cell to the next.
To do this \VTKm allows you to provide a \keyterm{whole cell set} argument to a worklet that provides random access to the entire topology.

A whole cell set is declared by adding a \sigtag{WholeCellSetIn} to the worklet's \controlsignature.
The corresponding argument to the dispatcher's \textcode{Invoke} should be a \textidentifier{CellSet} subclass or a \textidentifier{DynamicCellSet} (both of which are described in Section~\ref{sec:DataSets:CellSets}).

The \sigtag{WholeCellSetIn} is templated and takes two arguments: the ``from'' topology type and the ``to'' topology type, respectively.
These template arguments must be one of the topology element tags, but for convenience you can use \sigtag{Point} and \sigtag{Cell} in lieu of \vtkm{TopologyElementTagPoint} and \vtkm{TopologyElementTagCell}, respectively.
The ``from'' and ``to'' topology types define which topological elements can be queried and which incident elements are returned.
The semantics of the ``from'' and ``to'' topology is the same as that for the general topology maps described in Section~\ref{sec:WorkletMapTopology}.
You can look up an element of the ``to'' topology by index and then get all of the ``from'' elements that are incident from it.

For example, a \sigtag{WholeCellSetIn}\tparams{\sigtag{Point}, \sigtag{Cell}} allows you to find all the points that are incident on each cell (as well as querying the cell shape). Likewise, a \sigtag{WholeCellSetIn}\tparams{\sigtag{Cell}, \sigtag{Point}} allows you to find all the cells that are incident on each point.
The default parameters of \sigtag{WholeCellSetIn} are from point to cell.
That is, \sigtag{WholeCellSetIn}\tparams{} is equivalent to \sigtag{WholeCellSetIn}\tparams{\sigtag{Point}, \sigtag{Cell}}.

When the cell set is passed to the operator of the worklet, it is passed in a special connectivity object.
The actual object type depends on the cell set, but \vtkmexec{CellSetStructured} and are two common examples \vtkmexec{CellSetExplicit}.
All these connectivity objects share a common interface.
First, they all declare the following public types.

\begin{description}
\item[\textcode{CellShapeTag}]
  The tag for the cell shapes of the cell set.
  (Cell shape tags are described in Section~\ref{sec:CellShapeTagsIds}.)
  If the connectivity potentially contains more than one type of cell shape, then this type will be \vtkm{CellShapeTagGeneric}.
\item[\textcode{IndicesType}]
  A \Veclike type that stores all the incident indices.
\end{description}

Second they all provide the following methods.

\begin{description}
\item[\textcode{GetNumberOfElements}]
  Get the number of ``to'' topology elements in the cell set.
  All the other methods require an element index, and this represents the range of valid indices.
  The return type is \vtkm{Id}.
\item[\textcode{GetCellShape}]
  Takes an index for an element and returns a \textcode{CellShapeTag} object of the corresponding cell shape.
  If the ``to'' topology elements are not strictly cell, then a reasonably close shape is returned.
  For example, if the ``to'' topology elements are points, then the shape is returned as a vertex.
\item[\textcode{GetNumberOfIndices}]
  Takes an index for an element and returns the number of incident ``from'' elements are connected to it.
  The returned type is \vtkm{IdComponent}.
\item[\textcode{GetIndices}]
  Takes an index for an element and returns a \Veclike object of type \textcode{IndicesType} containing the indices of all incident ``from'' elements.
  The size of the \Veclike object is the same as that returned from \textcode{GetNumberOfIndicices}.
\end{description}

\VTKm comes with several functions to work with the shape and index information returned from these connectivity objects.
Most of these methods are documented in Chapter~\ref{chap:WorkingWithCells}.

Let us use the whole cell set feature to help us determine the ``flatness'' of a polygonal mesh.
We will do this by summing up all the angles incident on each on each point.
That is, for each point, we will find each incident polygon, then find the part of that polygon using the given point, then computing the angle at that point, and then summing for all such angles.
So, for example, in the mesh fragment shown in Figure~\ref{fig:PointIncidentAngles} one of the angles attached to the middle point is labeled $\theta_{j}$.

\begin{figure}[htb]
  \centering
  \includegraphics{images/PointIncidentAngles}
  \caption{The angles incident around a point in a mesh.}
  \label{fig:PointIncidentAngles}
\end{figure}

\noindent
We want a worklet to compute $\sum_{j} \theta$ for all such attached angles.
This measure is related (but not the same as) the curvature of the surface.
A flat surface will have a sum of $2\pi$.
Convex and concave surfaces have a value less than $2\pi$, and saddle surfaces have a value greater than $2\pi$.

To do this, we create a map cell to point worklet (Section~\ref{sec:WorkletMapCellToPoint}) that visits every point and gives the index of every incident cell.
The worklet then uses a whole cell set to inspect each incident cell to measure the attached angle and sum them together.

\vtkmlisting{Using \protect\sigtag{WholeCellSetIn} to sum the angles around each point.}{SumOfAngles.cxx}

\index{control signature!whole cell set|)}
\index{worklet!whole cell set|)}
\index{cell set!whole|)}
\index{whole cell set|)}

\section{Execution Objects}
\label{sec:ExecutionObjects}

\index{execution object|(}
\index{worklet!execution object|(}
\index{control signature!execution object|(}

Although passing whole arrays and cell sets into a worklet is a convenient way to provide data to a worklet that is not divided by the input or output domain, they is sometimes not the best structures to represent data.
Thus, all worklets support a another type of argument called an \keyterm{execution object}, or exec object for short, that passes the given object directly to each invocation of the worklet.
This is defined by an \sigtag{ExecObject} tag in the \controlsignature.

The execution object must be a subclass of \vtkmexec{ExecutionObjectBase}.
Also, it must be possible to copy the object from the control environment
to the execution environment and be usable in the execution environment,
and any method of the execution object used within the worklet must be
declared with \vtkmexecmodifier or \vtkmexeccontmodifier.

An execution object can refer to an array, but the array reference must be
through an array portal for the execution environment. This can be
retrieved from the \textcode{PrepareForInput} method in
\vtkmcont{ArrayHandle} as described in
Section~\ref{sec:ArrayHandle:InterfaceToExecutionEnvironment}. Other VTK-m
data objects, such as the subclasses of \vtkmcont{CellSet}, have similar
methods.

Returning to the example we have in Section~\ref{sec:WholeArrays}, we are
computing triangle quality quickly by looking up the value in a table. In
Example~\ref{ex:TriQualityWholeArray} the table is passed directly to the
worklet as a whole array. However, there is some additional code involved
to get the appropriate index into the table for a given triangle. Let us
say that we want to have the ability to compute triangle quality in many
different worklets. Rather than pass in a raw array, it would be better to
encapsulate the functionality in an object.

We can do that by creating an execution object that has the table stored
inside and methods to compute the triangle quality. The following example
uses the table built in Example~\ref{ex:TriQualityWholeArray} to create
such an object.

\vtkmlisting[ex:TriQualityExecObject]{Using \protect\sigtag{ExecObject} to access a lookup table in a worklet.}{TriangleQualityExecObject.cxx}

\index{control signature!execution object|)}
\index{worklet!execution object|)}
\index{execution object|)}

\section{Scatter}
\label{sec:WorkletScatter}

\index{scatter|(}
\index{worklet!scatter|(}

The default scheduling of a worklet provides a 1 to 1 mapping from the
input domain to the output domain. For example, a
\vtkmworklet{WorkletMapField} gets run once for every item of the input
array and produces one item for the output array. Likewise,
\vtkmworklet{WorkletMapPointToCell} gets run once for every cell in the
input topology and produces one associated item for the output field.

However, there are many operations that do not fall well into this 1 to 1
mapping procedure. The operation might need to pass over elements that
produce no value or the operation might need to produce multiple values for
a single input element.

Such non 1 to 1 mappings can be achieved by defining a \keyterm{scatter}
for a worklet. The following types of scatter are provided by VTK-m.

\begin{description}
\item[\vtkmworklet{ScatterIdentity}] Provides a basic 1 to 1 mapping from
  input to output. This is the default scatter used if none is specified.
\item[\vtkmworklet{ScatterUniform}] Provides a 1 to many mapping from input
  to output with the same number of outputs for each input. The worklet
  provides a number at runtime that defines the number of output values to
  produce per input.
\item[\vtkmworklet{ScatterCounting}] Provides a 1 to any mapping from input
  to output with different numbers of outputs for each input. The worklet
  provides an \textidentifier{ArrayHandle} that is the same size as the
  input containing the count of output values to produce for each input.
  Values can be zero, in which case that input will be skipped.
\end{description}

To define a scatter procedure, the worklet must provide two items. The
first item is a type definition named \scattertype. The \scattertype
must be set to one of the aforementioned
\textidentifier{Scatter*} classes. The second item is a \textcode{const}
method named \textcode{GetScatter} that returns an object of type
\scattertype.

\vtkmlisting{Declaration of a scatter type in a worklet.}{DeclareScatter.cxx}

When using a scatter that produces multiple outputs for a single input, the worklet is invoked multiple times with the same input values.
In such an event the worklet operator needs to distinguish these calls to produce the correct associated output.
This is done by declaring one of the \executionsignature arguments as \index{visit index} \sigtag{VisitIndex}.
This tag will pass a \vtkm{IdComponent} to the worklet that identifies which invocation is being called.

It is also the case that the when a scatter can produce multiple outputs for some input that the index of the input element is not the same as the \sigtag{WorkIndex}.
If the index to the input element is needed, you can use the \index{input index} \sigtag{InputIndex} tag in the \executionsignature.
It is also good practice to use the \index{output index} \sigtag{OutputIndex} tag if the index to the output element is needed.

To demonstrate using scatters with worklets, we provide some contrived but
illustrative examples. The first example is a worklet that takes a pair of
input arrays and interleaves them so that the first, third, fifth, and so
on entries come from the first array and the second, fourth, sixth, and so
on entries come from the second array. We achieve this by using a
\vtkmcont{ScatterUniform} of size 2 and using the \sigtag{VisitIndex} to
determine from which array to pull a value.

\vtkmlisting{Using \textidentifier{ScatterUniform}.}{ScatterUniform.cxx}

The second example takes a collection of point coordinates and clips them
by an axis-aligned bounding box. It does this using a
\vtkmcont{ScatterCounting} with an array containing 0 for all points
outside the bounds and 1 for all points inside the bounds. As is typical
with this type of operation, we use another worklet with a default identity
scatter to build the count array.

\vtkmlisting{Using \textidentifier{ScatterCounting}.}{ScatterCounting.cxx}

\index{worklet!scatter|)}
\index{scatter|)}


\section{Error Handling}
\label{sec:ExecutionEnvironment:ErrorHandling}
\label{sec:Worklet:ErrorHandling}

\index{errors|(}

\index{errors!execution environment|(}
\index{errors!worklet|(}
\index{worklet!error handling|(}

It is sometimes the case during the execution of an algorithm that an error
condition can occur that causes the computation to become invalid. At such
a time, it is important to raise an error to alert the calling code of the
problem. Since VTK-m uses an exception mechanism to raise errors, we want
an error in the execution environment to throw an exception.

However, throwing exceptions in a parallel algorithm is problematic. Some
accelerator architectures, like CUDA, do not even support throwing
exceptions. Even on architectures that do support exceptions, throwing them
in a thread block can cause problems. An exception raised in one thread may
or may not be thrown in another, which increases the potential for
deadlocks, and it is unclear how uncaught exceptions progress through
thread blocks.

VTK-m handles this problem by using a flag and check mechanism. When a
worklet (or other subclass of \vtkmexec{FunctorBase}) encounters an error,
it can call its \textcode{RaiseError} method to flag the problem and record
a message for the error. Once all the threads terminate, the scheduler
checks for the error, and if one exists it throws a
\vtkmcont{ErrorExecution} exception in the control environment. Thus,
calling \textcode{RaiseError} looks like an exception was thrown from the
perspective of the control environment code that invoked it.

\vtkmlisting{Raising an error in the execution environment.}{ExecutionErrors.cxx}

\index{worklet!error handling|)}
\index{errors!worklet|)}
\index{errors!execution environment|)}

\index{errors!assert|(}
\index{assert|(}

It is also worth noting that the \vtkmmacro{VTKM\_ASSERT} macro described
in Section~\ref{sec:ErrorHandlingControl} also works within worklets and
other code running in the execution environment. Of course, a failed assert
will terminate execution rather than just raise an error so is best for
checking invalid conditions for debugging purposes.

\index{assert|)}
\index{errors!assert|)}

\index{errors|)}

\index{worklet!creating|)}
\index{worklet|)}
