Tutorial: Array Notation

Previous: Task Parallelism Tools Up: Overview Next: SIMD-Enabled Functions

Intel Cilk Plus includes extensions to C and C++ that allows for parallel operations on arrays.  The intent is to allow users to express high-level vector parallel array operations. This helps the compiler to effectively vectorize the code.  Array notation can be used for both static and dynamic arrays. In addition, it can be used inside conditions for "if" and "switch" statements.  The extension has parallel semantics that are well suited for per-element operations that have no implied ordering and are intended to execute in data-parallel instructions.

A new operator [:] delineates an array section:

array-expression[lower-bound : length : stride]

  • Length is used instead of upper bound as C and C++ arrays are declared with a given length.
  • The three elements of the array notation can be any integer expression. The user is responsible for keeping the section within the bounds of the array.
  • Each argument to [:] may be omitted if the default value is sufficient.
    • The default lower-bound is 0.
    • The default length is the length of the array.  If the length of the array is not known, length must be specified.
    •  The default stride is 1.  If the stride is defaulted, the second ":" may be omitted.

So using array-expression[:] denotes an array section that is the entire array of known length and stride 1.

Array notation allows for multi-dimensional array sections as multiple array section operators can be used for a single array.

array-expression[:][:] denotes a two dimensional array

Two new terms are introduced for array sections:

  • The rank is the number of array sections used on a single array. A rank zero expression is a scalar expression.
  • The shape is the length of each array section.

Within a statement all expressions must have the same rank and shape or must be rank zero. A rank zero expression will be evaluated once and broadcast for each element in the array section.

Array notation also provides a set of built-in functions to provide reductions, shifts, and rotations of array sections.

Note that it is undefined behavior if there is overlap between the right hand side array expression and the left hand side unless it is exact overlap.

The Language Specification for an implementation of Cilk Plus Array Notation can be found at the Open Specifications section of the Download page of this website.

Array Notation for Static and C99 Variable-Length Arrays

The introduction of array section does not introduce new types in C or C++. The array section operations are on existing array types in C and C++. When we deal with arrays having known length, whether static or dynamic, we can use the short-hand notation for the entire array [:].

The best way to explain array notation is through a series of examples. In the set of examples below, we assume A, B and D are static integer arrays of size 10. Array C is a 2 Dimensional array of size 10x10. The equivalent C/C++ code is for illustrations and will of course have serial semantics where the array notation has parallel semantics, that is there is no implied ordering.

Scenario ArrayNotation Equivalent Scalar C/C+ Code

Set all the elements of array A to 5.

Sample program: set-array.cpp

A[:] = 5;
for (i = 0; i < 10; i++)
    A[i] = 5;

Set the first 7 elements of array A to 5 and the last 3 elements to 4.

Sample program: set-sequence.cpp

A[0:7] = 5;
A[7:3] = 4;
for (i = 0; i < 7; i++)
    A[i] = 5;
for (i = 7; i < (7 + 3); i++)
    A[i] = 4;

Set all the even array indices of A to 5 and the odd array indices to 4.

Sample program: set-stride.cpp

A[0:5:2] = 5;
A[1:5:2] = 4;
for (i = 0; i < 10; i += 2)
    A[i] = 5;
for (i = 1; i < 10; i += 2
    A[i] = 4;

Set each element of array A to the corresponding value of array B.

Sample program: copy-array.cpp

A[:] = B[:];
for (i = 0; i < 10; i++)
    A[i] = B[i];

Set each element of array A to the corresponding value of array B, adding 5 to each element.

Sample program: copy-and-add.cpp

A[:] = B[:] + 5;
for (i = 0; i < 10; i++)
    A[i] = B[i] + 5;

Add arrays A and B together, giving D.

Sample program: add-arrays.cpp

D[:] = A[:] + B[:];
for (i = 0; i < 10; i++)
    D[i] = A[i] + B[i];

Set the first 'n' elements of array A to 5.

Sample program: set-first-n.cpp

A[0:n] = 5;
for (i = 0; i < n; i++)
    A[i] = 5;

Set all the elements of the two-dimensional array C to 12.

Sample program: set-2d-array.cpp

C[:][:] = 12;
for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
        C[i][j] = 12;

Set all elements in even rows of array C to 12.

Sample program: set-2d-stride.cpp

C[0:5:2][:] = 12;
for (i = 0; i < 10; i += 2)
{
    for (j = 0; j < 10; j++)
        C[i][j] = 12;
}

Set all elements in row 'X' (where X is a variable, #define or an expression) in array C to the corresponding elements of array A.

Sample program: set-2d-row.cpp

C[X][:] = A[:];
for (j = 0; j < 10; j++) 
    C[X][j] = A[j]

Pass all elements one by one into function "func()".

Sample program: call-scalar-function.cpp

func (A[:]);
for (i = 0; i < 10; i++)
    func (A[i]);

As we can tell from the examples above, large complex C/C++ loops can be collapsed into simple 1 or 2 lines of code that are easier to understand.

Array Notation with Dynamically Allocated Arrays

Arrays allocated from the heap can use array notation just like statically allocated arrays with one exception; to access all the elements in the array, the user must specify the start and the number of elements to be accessed. For example, to access all the elements of the dynamic array 'dA,' you cannot use the notation dA[:].  You must explicitly state the start_index and length. For multi-dimensional arrays the length must be known of all array sections except the outermost.

Array Notation for Conditions

Array notation can be used inside conditions. In the examples below, we provide several scenarios. For simplicity, we are using a static array 'A' of size 10. Please note that N-dimensional arrays can be represented in the same way.


Scenario Array Notation Equivalent Scalar C/C+ Code

For each element of array A, print "Matched" if the value is 5. Otherwise print "Not Matched".

Sample program: check-for-5.cpp

if (5 == a[:])
    results[:] = "Matched";
else
    results[:] = "Not Matched";
for (int i = 0; i < array_size; i++)
{
    if (5 == a[i])
        results[i] = "Matched";
    else
        results[i] = "Not Matched";
}

Determine the type of each letter in array A.

Sample program: letter-type-if.cpp

if (('a' == A[:]) ||
    ('e' == A[:]) ||
    ('i' == A[:]) ||
    ('o' == A[:]) ||
    ('u' == A[:]))
    types[:] = "Vowel";
else
    types[:] = "Consonant";
for (i = 0; i < 10; i++)
{
    if (('a' == A[i]) ||
        ('e' == A[i]) ||
        ('i' == A[i]) ||
        ('o' == A[i]) ||
        ('u' == A[i])))
        types[i] = "Vowel";
    else
        types[i] = "Consonant";
}

Array Notation and Function Maps

A scalar function is mapped to the elements of an array section argument. The element type of the array section match to the function argument type. The element type is used to resolve overloading in C++.

A[:] = sin(B[:]);  

The above example invokes the math function sin() to every element of the array section B[:] and assign the results to the array section A[:].

A function map is executed in parallel and implies no specific ordering. The compiler may use a vector version of a function either built-in functions or user defined SIMD-enabled functions.

A[:] = pow(B[:], c);  // B[:]**c  

A[:] = pow(c, B[:]);  // c**B[:]

Given the function map it is possible to apply C++ operators to array sections:

A[:] = B[:] + C[:];  // A[:] = operator+(B[:], C[:]);

Builtin Functions for Array Sections

Array notation provides several functions to do basic computations among elements in an array. Input to all the functions is an array section. Please see the table below for their explanations. It is worth mentioning that any of the array notation formats allowed for dynamic/static arrays can be used as input parameters for the following builtin functions.

Bultin function Meaning
__sec_reduce_add (A[:]) 

Returns a scalar that is a sum of all the elements in the array section.

__sec_reduce_mul (A[:])

Returns a scalar that is a product of the 10 elements from index '0' (inclusive).

__sec_reduce_max (A[:])

Returns a scalar that is the largest element in the array section.

__sec_reduce_min (A[:])

Returns a scalar that is the smallest element in the array section.

__sec_reduce_max_index (A[:])

Returns the integer index of the largest element in the array section.

__sec_reduce_min_index (A[:])

Returns the integer index of the smallest element in the array section

__sec_reduce_all_zero (A[:])

Returns 1 if all the elements of the array section are zero, else returns 0.

__sec_reduce_all_nonzero (A[:])

Returns 1 if all elements of the array section are non-zero, else returns 0.

__sec_reduce_any_zero (A[:])

Returns 1 if any of the elements in the array section are zero, else returns 0.

__sec_reduce_any_nonzero (A[:])

Returns 1 if any of the elements in the array section are non-zero, else returns 0.

Gather and Scatter Operations

Array notation can be used for array indicies. This technique is useful for gather scatter operations. For example, let's say we need to gather elements from array A given by indices in another array B and move it to another array C; we can do the following.

C[:] = A[B[:]] 

Similarly, to scatter elements from Array A into various locations in C given by indices in array B, we can do the following:

A[B[:]] = C[:]
Previous: Task Parallelism Tools Up: Overview Next: SIMD-Enabled Functions