-
Notifications
You must be signed in to change notification settings - Fork 71
scan
While the well-known reduce operation reduces an array into a single value, it can also be useful to store the intermediate results of a reduction. To implement this parallel pattern, ParallelArray supports a scan method.
An example of a computation that can be done using scan is the prefix-sum operation that, given a vector of numbers, computes another vector of numbers such that each position contains the sum of all elements of the source vector up to that position.
We implement what is known as an inclusive scan, which means that the value of the ith element in the result array is the result of reducing the elements from index 0 to index i in the source array. Notice that the first element of the result is the same as the first element in the original ParallelArray.
An exclusive scan can be implemented by shifting the result array of an inclusive scan to the right by one, and inserting the identity element at index 0.
Like reduce, scan can arbitrarily reorder the calls to the elemental function. Ignoring things like overflow and floating-point anomalies, reordering cannot be detected if the elemental function is associative. So, for instance, using an associative operation such as addition to compute a partial sum will produce the same result, regardless of the order in which calls to the elemental function occur. However, using a non-associative operation can produce nondeterministic results. Although scan will produce a result consistent with some ordering, the ordering and the result may differ for each call to scan.
It is up to the programmer to only call scan with associative functions; nothing in the programming model prevents them from doing otherwise.
myParallelArray.scan(elementalFunction, arg1, arg2, ...)-
elementalFunction: described below. -
arg1,arg2, ...: optional arguments, passed unchanged toelementalFunction.
function(a, b, arg1, arg2, ...) { <body> }-
a: The partial result of the reduction so far. -
b: The next element to be processed. -
arg1,arg2, ...: The same as the optional arguments passed toscan.
The result of the elemental function is a new partial result of reduction, which then becomes an element of the result array.
Inside the elemental function, the value of this will be the ParallelArray object on which scan was invoked. For example, in the invocation of scan above, this would refer to myParallelArray.
A freshly minted ParallelArray whose ith element is the result of using the elemental function to reduce the elements between 0 and i in the original ParallelArray.
// an identity function
var pa = new ParallelArray([1,2,3,4,5]);
var paIdentical = pa.scan(function(a, b){return b;})
// compute a partial sum; `psum` is a ParallelArray containing [1, 3, 6, 10, 15]
var source = new ParallelArray([1,2,3,4,5]);
var psum = source.scan(function plus(a,b) { return a+b; });