Scans
A scan is an operation that takes a vector and produces a
vector. Each element in the result represents the combination of all
the elements preceding the corresponding element in the original
vector. For example, a sum scan (prefix sum) puts the sum of elements
0..i-1 in element i of the result (element 0 of the result gets a 0,
since it is the sum of no elements).
DAPPLE includes many different kinds of scans:
<![CDATA[
intVector A(N), B(N);
...
A = plus_scan(B); // A[i] = B[0] + B[1] + ... + B[i-1]
A = max_scan(B); // A[i] = max of B[j], for j in 0..i-1
A = min_scan(B); // A[i] = min of B[j], for j in 0..i-1
...
booleanVector C(N), D(N);
...
C = or_scan(D); // C[i] = D[0] || D[1] || ... || D[i-1]
C = and_scan(D); // C[i] = D[0] && D[1] && ... && D[i-1]
]]>
Note that the arithmetic scans can be applied to anything but boolean
vectors, while OR and AND scans apply only to boolean vectors.
Note that the value of the first element is independent of the
contents of the vector. For plus_scan, the value is 0. For max_scan,
the value is the smallest which that type can hold (for integers,
-2147483647). For min_scan, the value is the largest which that type
can hold (for integers, 2147483647). For or_scan, the value is
false , and for and_scan, the value is true.
If some of the virtual processors are inactive, they do not
participate in the scan, that is, no value is produced at those
elements, and their value is not included in the scan.
Matrices.
Scans can be applied to Matrix objects as well. In this case, each
row or column is independently scanned like a vector. The same scans
are available, both for rows and for columns.
<![CDATA[
intMatrix A(N), B(N);
...
A = plus_scan_rows(B); // A[i][j] = B[i][0] + B[i][1] + ... + B[i][j-1]
A = plus_scan_cols(B); // A[i][j] = B[0][j] + B[1][j] + ... + B[i-1][j]
A = max_scan_rows(B); // A[i][j] = max of B[i][k], for k in 0..j-1
A = max_scan_cols(B); // A[i][j] = max of B[k][j], for k in 0..i-1
A = min_scan_rows(B); // A[i][j] = min of B[i][k], for k in 0..j-1
A = min_scan_cols(B); // A[i][j] = min of B[k][j], for k in 0..i-1
...
booleanMatrix C(N), D(N);
...
C = or_scan_rows(D); // C[i][j] = D[i][0] || D[i][1] || ... || D[i][j-1]
C = or_scan_cols(D); // C[i][j] = D[0][j] || D[1][j] || ... || D[i-1][j]
C = and_scan_rows(D); // C[i][j] = D[i][0] && D[i][1] && ... && D[i][j-1]
C = and_scan_cols(D); // C[i][j] = D[0][j] && D[1][j] && ... && D[i-1][j]
]]>
Again, if some of the virtual processors are inactive, they do not
participate in the scan, that is, no value is produced at those
elements, and their value is not included in the scan.