% -*- latex -*-

\chapter{Global Arrays and Topology}
\label{chap:Globals}

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

When writing an algorithm in \VTKm by creating a worklet, the data each instance of the worklet has access to is intentionally limited.
This allows \VTKm to provide safety from race conditions and other parallel programming difficulties.
However, there are times when the complexity of an algorithm requires all threads to have shared global access to a global structure.
This chapter describes worklet tags that can be used to pass data globally to all instances of a worklet.


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

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

A \keyterm{whole array} argument to a worklet allows you to pass in an \textidentifier{ArrayHandle}.
All instances of the worklet will have access to all the data in the \textidentifier{ArrayHandle}.

\begin{commonerrors}
  The \VTKm worklet invoking 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 of a worklet.
The corresponding argument to the \textidentifier{Invoker} 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.
(Array portals are discussed in Section \ref{sec:ArrayPortals}.)
This means that the worklet can access any entry in the array with \classmember*{ArrayPortal}{Get} and/or \classmember*{ArrayPortal}{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{Int32} or \vtkm{Int64} 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 \textidentifier{Invoker} 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{AtomicArrayExecutionObject} structure.
\textidentifier{AtomicArrayExecutionObject} has two important methods:
\begin{description}
\item[{\classmember*{AtomicArrayExecutionObject}{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.
  \classmember{AtomicArrayExecutionObject}{Add} returns the value that was replaced.
  That is, it returns the value right \emph{before} the addition.
\item[{\classmember*{AtomicArrayExecutionObject}{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 \textidentifier{Invoker} 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 ``visit'' topology type and the ``incident'' 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 ``visit'' and ``incident'' topology types define which topological elements can be queried (visited) and which incident elements are returned.
The semantics of the ``visit'' and ``incident'' 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 ``visit'' topology by index and then get all of the ``incident'' elements from it.

For example, a \sigtag{WholeCellSetIn}\tparams{\sigtag{Cell}, \sigtag{Point}} 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{Point}, \sigtag{Cell}} allows you to find all the cells that are incident on each point.
The default parameters of \sigtag{WholeCellSetIn} are visiting cells with incident points.
That is, \sigtag{WholeCellSetIn}\tparams{} is equivalent to \sigtag{WholeCellSetIn}\tparams{\sigtag{Cell}, \sigtag{Point}}.

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[\classmember*{Connectivity}{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[\classmember*{Connectivity}{IndicesType}]
  A \Veclike type that stores all the incident indices.
\end{description}

Second they all provide the following methods.

\begin{description}
\item[\classmember*{Connectivity}{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[\classmember*{Connectivity}{GetCellShape}]
  Takes an index for an element and returns a \classmember*{Connectivity}{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[\classmember*{Connectivity}{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[\classmember*{Connectivity}{GetIndices}]
  Takes an index for an element and returns a \Veclike object of type \classmember*{Connectivity}{IndicesType} containing the indices of all incident ``from'' elements.
  The size of the \Veclike object is the same as that returned from \classmember*{Connectivity}{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 visit points with cells worklet (Section \ref{sec:WorkletVisitPointsWithCells}) 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|)}

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

