Supported C Syntax

The following tables enumerate all ANSI C keywords and operators. Entries that are shaded gray are not supported in Sequoia. In general, the excluded features deal with pointers/references, or with memory allocation; Sequoia forbids the use of pointers, and decouples the physical location of data from its logical use, and thus keywords such as volatile don't have as much meaning in the context in which Sequoia operates.

Keywords

In addition, the C++ keyword inline is supported in Sequoia.

Unary Operators

Binary and Ternary Operators

Preprocessing

A Sequoia (.sq) source file will be run through a C preprocessor before the Sequoia compiler sees it, and thus the full range of C comments, defines, macros, includes and other preprocessor features are supported. The C preprocessor is external to the Sequoia system; "g++ -E" is used in the Cell build infrastructure, for example.

Sequoia Extensions to C

Sequoia extends C by adding four categories of constructs.

Tasks

Tasks, similar to C functions, are used to express an independent unit of computation that occurs in an isolated (private) namespace.

General C functions are not supported in Sequoia, although inline C functions are. Such inline functions may only refer to the subset of C that Sequoia supports (and not any of the C extensions which it defines), and may only take scalar arguments.

Abstract Arrays and Array Blocks

Abstract arrays are logical collections of data that are decoupled from their physical locations and layouts, and array blocks are used to refer to sub-arrays in a manner reminiscient of Matlab matrices. These Sequoia abstract arrays and array blocks replace C's arrays, except in the case of arrays contained within a struct or union; these are still C-style arrays.

The built-in copy operator can be used to transfer data between Sequoia array blocks.

Iteration Constructs

Sequoia adds some simple iteration constructs to C's set of loop constructs (while, for, etc.). These iteration constructs are conceptually like the map operator of functional languages, in which a task is mapped over a collection of data elements (which are array blocks, in Sequoia). There is a parallel iteration construct (mappar), a sequential iteration construct (mapseq), and a construct which expresses a parallel reduction (mapreduce).

Parameters

Sequoia parameters are variables whose values are set at compile time, rather than in the Sequoia program code.

Sequoia Keywords

Sequoia extends the set of C keywords with the keywords in the following table.

The copy keyword is used to copy data betwen array blocks, in, out, inout, and task are used in task definitions, mappar, mapreduce, mapseq, and reducearg are part of Sequoia's iteration constructs, and tunable is used to declare Sequoia parameters.

Scalars

Scalar data objects can be of any of the non-array C types (int, float, struct, etc.). Conceptually, a scalar object is a single, indivisible piece of data that resides in a single location in the machine, spanning a set of contiguous memory addresses. Scalar objects are often referred to as records in Sequoia's nomenclature.

The intent is that scalar data objects in Sequoia are "small" and are used mainly for the purposes of program control (counters, iteration variables, etc.). "Large" data objects should be expressed as Sequoia arrays.

Arrays

In C, arrays and pointers are closely coupled, and an array variable refers to a specific memory location in the machine. In Sequoia, on the other hand, physical memory locations have been abstracted, and pointers of any sort are not used, and so arrays in Sequoia are more "logical" than "physical". On some machines, an array may be physically distributed over multiple disjoint memory modules or nodes, though in the programming model an array is abstracted as being contained within a single namespace.

Array Declarations

Sequoia natively supports both one- and multi-dimensional arrays using C's "[]" notation. Arrays can be of any scalar type. A Sequoia array is declared in a similar way to a C array, although in Sequoia, arrays must have a value specifying the size of every dimension of the array.

float A[20][10];

An array declaration's size value may be an arithmetic expression over constant literals and parameters (see the Parameters section for details), and may have a dynamic size. For example:

double B[100+S][2*T];

Accessing Arrays

A Sequoia array element is accessed using the same syntax as for C arrays, and can be used as an rvalue in any C expression, for example:

x += A[i][j];
if (A[2*m][B[n]] == 2) {
    ...
}
...

However, an array element can not, in general be used as an lvalue; this is described in the section on "task types". Put another way, array elements may be freely read, but there are constraints on the manner in which they can be written to.

Note that while a program may refer to array elements in the usual manner (e.g. A[i][j]), unlike with C there is no way to refer to the physical location of an array element in the machine. The array is an abstract collection of scalar records that has been decoupled from physical factors such as where in the machine the array elements reside, whether the array is distributed over multiple machines, and the array's layout in memory (row- or column-major, etc.). (For consistency, all diagrams in this documentation visually present arrays as being row-major, but their physical layout on a target machine need not be).

In addition to single-element indexing, Sequoia adds syntax for referring to collections of array elements that can be moved through the machine together in single bulk data transfers; see the Array Blocks section of the documentation for details.

Arrays Within Structs

Sequoia abstract arrays and array blocks, with their decoupling of element locations and data layout from logical structure, completely replace C's arrays in the language, except in one situation: arrays contained within a struct or union are still C-style arrays. Further, a struct or union containing an array is still considered a scalar object.

The reason for this distinction is that the physical layout of an array that is packed within a struct is exposed to the user, while Sequoia's arrays abstract these physical details. Moreover, Sequoia's arrays are intended to be decomposed into sub-arrays, while structures and other scalar objects are treated as indivisible data units.

However, despite being native C arrays, these contained arrays can only be accessed using C's "[]" array indexing and not via pointer notation. In addition, Sequoia's array block notation can't be used on such arrays, nor can they be passed as arguments to task calls or the copy operator.

Introduction to Array Blocks

A Sequoia array is an abstract collection of scalar records, and an array block refers to a subset of the elements in an array. An array block can be considered a "window" or "view" into the base array from which it is derived; it is not a separate copy of the array elements.

Range Array Blocks

Consider the following example; the array block notation used is A[start:end;].

The same example, but with a non-unit stride array block, is as follows. Note that the yellow array block only refers to 4 elements of A. The notation used is A[start:end:stride;].

The first of the two kinds of array blocks, range array blocks, is depicted above in the two examples. In each dimension of the array, a range of elements is specified, in the form [start:end:stride;max]. The stride field is omitted from the first example, and the max field is omitted from both. (The default values used in the case that certain fields are omitted are described in the Array Block Default Values section).

The four fields of range array blocks are defined as follows.

• Start: The index of the first element in the range.
• End: The index just after the last element in the range. That is, the end value is non-inclusive. For example, if the range was 2:6, then the values referred to would be 2,3,4,5.
• Stride: The per-element stride of the range; for example, a stride of 3 refers to every third element. The first element is always that referred to by start, regardless of the stride.
• Max: The maximum number of elements referred to by the range, in that dimension. The other three fields are seen in array notations in other languages, such as Matlab and Python, but the max field is unique to Sequoia, and is described in its own section.

An N-dimensional array can be used as the source of a N-dimensional range array block; that is, the number of dimensions must match.

Indexed Array Blocks

The second kind of array block is an indexed array block, in which a second "index" array is used to specify which elements of the base array are referred to. Unlike range array blocks, indexed array blocks can only be formed from 1-dimensional arrays, and the index array must also be 1-dimensional. Consider the following example; the notation is BaseArray[IdxArray].

Note that as with range array blocks, the indexed array block is a "view" or "window" into its base array; the yellow sub-array in the diagram was just drawn to illustrate that the order of the elements in the indexed array block is not necessarily the same as their order in the base array from which they are selected.

As a second example, consider the following, in which a range array block of the index array is used to specify an indexed array block of array A. Note that indexed array blocks may not be nested; that is, Array1[Array2[Array3]] isn't a valid Sequoia array block. (This is evident in the array block grammar).

Clearly, the size of the resultant indexed array block is identical to the size of array block of the index array.

Array Block Usage

Array blocks can only be used in two ways: as arguments to tasks, or as arguments to the built-in copy operator. In each of these cases, the array block refers to a region of some base array, but the actual transfer of data to or from that region only occurs when the array block is passed as an argument. See these two sections for details, in particular the section on the copy operator, as it contains several array blocks examples.

The "Max" Field

Sequoia is intended as a language for programming machines with explicitly managed memory hierarchies. That is, there will often be some form of local memory, such as the LS in Cell, that the program is managing, and data must be explicitly allocated in this memory. Given that such local memories are small and of fixed size, it is important for the Sequoia program to reason about the precise amount of space that a collection of data will consume; there are no efficient "spilling" or replacement mechanisms such as a cache provides in conventional architectures to enable a large working set to be staged in a small local memory.

To enable the Sequoia compiler to reason about space, range array blocks have a max field associated with them. The start, end, and stride fields are used to refer to a range of elements, and the max field specifies the largest possible number of elements that the corresponding range could refer to. This becomes important due to the fact that the other three fields may be arbitrary expressions whose values aren't known until runtime. The max field allows the programmer to express to the compiler a program invariant: that the maximum amount of space needed to stage the array block is bounded by some value.

Consider this range array block, in which i and j are dynamic variables:

// start      end    max
A[ (i+j)*32 : j*64 ; 128 ]

Just by looking at the start and end fields, there is no way to statically determine how large this array block may be, which is a problem if the program instructs that the array block should be copied into a fixed-size local memory. The max field specifies that no matter what the values of the variables i and j are, the array block will contain at most 128 elements of A, enabling the compiler to allocate space for it in the local memory.

At runtime, when the actual values of start and end are known, a check will be perfomed to ensure that the actual size of the array block is indeed at most 128 elements.

Static vs. Dynamic Array Blocks

While start, end, and stride may be arbitrary C expressions, max may only be an arithmetic expression over constant literals and parameters. The description of these parameters is left to the Parameters section, but for the purposes of the description of array blocks in this section, there are two types of parameters: tunable and array size. Tunable parameters are compile-time constants, while array size parameters may or may may not be.

Ideally, the max expression will evaluate to a compile-time constant, and if it only uses tunable parameters, then this will always be the case. An array block whose maximum size in each dimension is statically known is referred to as a static array block.

If, however, the max expression refers to any array size parameters, then it is possible that its value may not be statically determinable, and in this case, max will default to the full size of the base array that the array block is over; the same default applies if the max field is omitted. Further, it is possible that the base array itself is dynamically sized, and thus no static bound will be known for the size of the array block; in this case, the array block is referred to as being dynamic.

Dynamic array blocks are not illegal in Sequoia, however only static array blocks may be transferred to software-managed memories such as the LS in Cell (assuming that they will fit); dynamic array blocks may only be transferred between memory modules with an effectively "infinte" size, such as global memory that is paged to disk.

Array Block Grammar

The following grammar defines the syntax for specifying array blocks.

array-block <- range-array-block-Nd
            <- indexed-array-block

range-array-block-1d <- array-ident dim-range0
                     <- array-ident

range-array-block-Nd <- array-ident dim-range0 { dim-range1 ... }
                     <- array-ident

indexed-array-block <- array-ident "[" range-array-block-1d "]"

dim-range <- "[" start-expr ":" end-expr ":" stride-expr ";" max-expr "]"
          <- "[" start-expr ":" end-expr ";" max-expr "]"
          <- "[" start-expr ";" max-expr "]"

max-expr <- const-param-expr
         <-

start-expr <- expr

end-expr <- expr

stride-expr <- expr

The three base terms in the grammar are:

• expr: A general C expression that evaluates to an integer rvalue. The terms in the expression can be constants, variables, array elements, parameters, or any other term that can be an rvalue.
• const-param-expr: A general C expression that evaluates to an integer rvalue. The terms in the expression may only be constant literals (including preprocessor constants) or parameters.
• array-ident: The identifier (name) of the base array; for example, if the array is A[100], and the array block is A[10;30], then the array-ident is just the symbol A.

Array Block Default Values

There are six different range array block syntax styles, each allowing different fields to be omitted; these are described by the array block grammar. Note that in a multi-dimensional range array block, different styles may be used in different dimensions, for example A[5:8;][i:j:2;10]. The six styles are listed below, with the latter five essentially being short-hand forms of the first style.

• [start:end:stride;max]
• [start:end;max]
• [start;max]
• [start:end:stride;]
• [start:end;]
• [start;]

Consider an array with N_i elements in its i^th dimension. The end_i, stride_i, and max_i fields may all be omitted, depending on which short-hand notation is used, and if they are, then they will default to certain values in the following manner.

• end_i <- min(start_i + stride_i*max_i, N_i)
• stride_i <- 1
• max_i <- N_i

Note that N_i may be an unbounded value, if the base array is dynamically sized, and max_i and end_i will both default to an unbounded value in this case, resulting in a dynamic array block.

The utility of omitting the end field is that it allows the expression that an array block covers at most a certain range; if the end field is present, then it specifies that the block exactly covers a precise range. This is convenient when handling boundary cases, such as tiling an array into array blocks when the array block's size doesn't evenly divide the base array's size in some dimension, leaving an array block at the "edge" of the base array which is smaller than the rest of the array blocks. The following diagram shows some example array blocks which use this technique:

Trivial Array Blocks

An entire array may be used as an array block, un-annotated by the "[::;]" range syntax. The above defaults for omitted fields apply, in addition to the default that start_i <- 0 in each dimension.

Array Block Valid Ranges

Consider an array with N_i elements in its i^th dimension. The valid values for the range array block fields start_i, end_i, stride_i and max_i are as follows:

• 0 <= start_i <= N_i
• 0 <= end_i <= N_i
• 1 <= stride_i
• 0 <= max_i

Further, the following relationships must hold, else the array block isn't valid:

• start_i <= end_i
• end_i - start_i <= max_i * stride_i

An array block can actually refer to zero elements of its base array, if any of the following are true:

• start_i = end_i
• start_i = N_i
• end_i = 0
• max_i = 0

Introduction to Tasks

Tasks are void functions that can only access their arguments and their locally declared data. In the Sequoia language, tasks replace C-style functions (although external functions written in other languages, such as C/C++, can be called from Sequoia code; see the Sequoia API section for details).

A simple example task is as follows, with Sequoia keywords in bold:

void task<leaf> VectScale::Kernel(in float A[128], in float x, out float Y[128])
{
    for (int i = 0; i < 128; i++) {
        Y[i] = x * A[i];
    }
}

This task takes as inputs an array A and scalar value x, and outputs the array Y which results from multiplying each element of A by x. The only data objects which the body of this task may access are its task arguments (A, x, and Y) and its local variables (i). (The meaning of the task<leaf> keyword is described in the Task Types section, and the naming convention for tasks is described in the Task Variants section).

Sequoia adds three keywords for specifying whether a task's argument is an input (in), an output (out), or both an input and an output (inout). Exactly one of these keywords must be the first term in the type expression for each of the task's arguments. The above example used in and out, and the following modified example uses inout, and accumulates the vector-scalar product into the output array.

void task<leaf> VectScaleAccum::Kernel(in float A[128], in float x, inout float Y[128])
{
    for (int i = 0; i < 128; i++) {
        Y[i] += x * A[i];
    }
}

An in argument will have been initialized before the task is called, an out argument will be uninitialized at the start of the task's execution and will be copied back to the task's caller when it completes, and an inout argument is both initialized before the task begins and copied back to the task's caller when it returns.

A constraint on the use of in arguments is that they can only be read from; they cannot be written to. This applies to both "single-element" accesses, such as "x = A[i];", and also to accessing the array via array blocks passed to tasks or to the copy operator. There is no constraint on inout or out arguments, which can be both read from and written to.

An important property of Sequoia's tasks is that they execute in "isolation" of the rest of the program. Put another way, the data that a task can access (its arguments and local variables) are private to the task during its entire execution, and there is no way for concurrent tasks to communicate with each other. This is explained more fully in the Calling Semantics section.

Task Types

There are three types of task in Sequoia: inner, leaf, and external tasks. (The reason for these names will be made clear in the Task Variant Call Graph section.) These types are distinguished by their intent as well as their syntax.

First, recall the abstract machine model that Sequoia assumes. A characteristic of machines which fit this model is that there are a number of efficient processing elements (PEs) that operate out of small, local memories, which are backed by one or more levels of larger/slower memories, in a memory hierarchy. For example, in Cell, the SPEs only access data in the LSes, which stage data transferred into them from main memory.

A leaf task is intended to execute directly on the machine's efficient PEs (the SPEs in Cell) and a leaf task's dataset must completely fit into the local memory. Leaf tasks perform the "actual computation" of a program, and operate on individual array elements.

Inner tasks, on the other hand, are intended to operate on large datasets, simply decomposing them such that they can be passed to subtasks. Inner tasks express the decomposition of an algorithm, and manipulate array blocks rather than individual array elements. On Cell, an inner task could execute in the PPE, and its two main roles would be to transfer blocks of data between the LS and memory, and to invoke leaf tasks in the SPEs that will execute out of the data in the LS.

An external task is any function written outside of Sequoia that will be called from within Sequoia code. The external implementation must conform to the Sequoia API.

The type of a task is specified in its definition; note that external tasks don't have bodies.

void task<inner> TaskName::VariantName( ... ) { ... }
void task<leaf> TaskName::VariantName( ... ) { ... }
void task<ext> TaskName::VariantName( ... );

The following table enumerates the capabilities and limitations of inner and leaf tasks. As a quick summary of this table, leaf tasks (mostly) only use Sequoia's supported subset of C, while inner tasks use Sequoia's extensions to C, in addition to this C subset. One important difference is that leaf tasks may read and write their array variables directly using single-element indexing, while inner tasks may only read them in this manner.

Task Variants

Sequoia allows multiple algorithmic variants of tasks to be defined. Task variants are different implementations of the same task, and variants of a task all have the same function type signatures.

The variant name is just an arbitrary label that follows the "::" symbols in the full task identifier; the programmer is free to choose any variant name, and isn't limited to those used in the examples in this documentation ("Leaf", "Inner", etc.). No two variants of the same task may have the same variant name.

Note that different variants need not have the same symbolic names for their arguments, nor the same symbolic names for their array size parameters; just as with C function signatures, Sequoia task signatures only relate to the type of the arguments, not their symbolic names.

The utility of having multiple variants relates to the way that tasks are called in Sequoia. A task callsite only refers to the base name of the task and not to any specific task variant, allowing the target-specific process of mapping the Sequoia program to select which variant to call, based on which would be a more appropriate implementation for the target machine.

Task Prototypes

All tasks must have a prototype, similar to a C function prototype. There is a single prototype per task, not per task variant, and the prototype has no variant specifier or task type specifier. For example:

// Prototype
void task MyTask(in float A[P][Q], inout int x);

// Inner task variant definition #1
void task<inner> MyTask::InnerVariant1(in float A[P][Q], inout int x)
{
    ...
}

// Inner task variant definition #2
void task<inner> MyTask::InnerVariant2(in float A[P][Q], inout int x)
{
    ...
}

// Leaf task variant definition
void task<leaf> MyTask::LeafVariant(in float A[P][Q], inout int x)
{
    ...
}

// External task variant definition; has no body
void task<ext> MyTask::ExtVariant(in float A[P][Q], inout int x);

All task variant definitions are required to have an identical signature to the task's prototype.

Task Calling Semantics

A property of inner tasks, but not leaf tasks, is that they can call other tasks, as in the example below, in which a 128x128 matrix A is scaled by variable x, resulting in the matrix Y. The MatrixScale128::Inner task calls the MatrixScale64::Leaf task 4 times, once for each of the top-left, top-right, bottom-left, and bottom-right regions of its argument arrays A and Y, passing the corresponding 64x64 array blocks to the subtask.

void task<inner> MatrixScale128::Inner(in float A[128][128], in float x, out float Y[128][128])
{
    for (unsigned int i = 0; i < 2; i++) {
        for (unsigned int j = 0; j < 2; j++) {

            // Task call:
            MatrixScale64( A[i*64;64][j*64;64], x, Y[i*64;64][j*64;64] );
        }
    }
}

void task<leaf> MatrixScale64::Leaf(in float A[64][64], in float x, out float Y[64][64])
{
    for (unsigned int i = 0; i < 64; i++) {
        for (unsigned int j = 0; j < 64; j++) {
            Y[i][j] = A[i][j] * x;
        }
    }
}

Task calling syntax resembles C-style function calling syntax, though the only arguments that may be passed to a task call are array blocks and scalars.

Callee Variant not Specified

Note that a task callsite only specifies the "base" name of the task being called, and not the specific task variant. The choice of which variants to call at a task's callsites is made during the process of mapping a Sequoia program to a target machine; see the task instances section for more details.

Copy-In, Copy-Out

The task calling semantics are call-by-value-result (CBVR), also referred to as "copy in, copy out". The data that the calling (parent) task passes as arguments to the call are copied into the child (callee) task's namespace. The copies that take place between the parent and child task namespaces in the above example are illustrated in the following diagram:

If the child (callee) task's argument is in or inout, then a copy from the parent's namespace to the child's namespace occurs before the child task begins executing, and if the child task's argument is inout or out, then a copy from the child's namespace back to the parent task's namespace occurs after the child completes.

Recall that array blocks are "views" or "windows" into their base arrays. Passing an array block as an argument to a subtask call implies that copies will occur between the base array of the array block and the subtask's namespace. Hence, due to the constraint that a task may not modify its in arguments, such arguments may not be passed to subtask calls if the subtask's corresponding argument type is inout or out.

Array Block Aliasing

Just as the copy operator doesn't permit its source and destination array blocks to overlap if they are derived from the same base array, array blocks passed as task arguments are similarly prohibited from overlapping if passed to an inout or out argument of the callee subtask. That is, input-output and output-output aliasing of task arguments is not permitted, though it is the responsibilty of the programmer to ensure that this doesn't occur. The section on undefined behavior has more details.

Input-input aliasing is permitted, however; overlapping array blocks (of the same base array) may be passed to different subtask arguments, provided that they are all in.

In the case of scalar variables, the compiler will indicate an error if the same variable is passed to more than one subtask argument, unless all of the subtask arguments that the scalar variable is passed to are in.

Concurrent Execution

Child tasks do not run concurrently with their parent tasks. Rather, when the parent task makes a task call, it will wait until the child task completes before continuing. The only way for tasks to run concurrently in Sequoia is via its parallel iteration constructs mappar and mapreduce, and in these cases, such tasks are "sibling" tasks, rather than "parent" and "child".

Semantic Copies != Physical Copies

An important point to understand is that the copies of data between task namespaces that are implied by the calling semantics of tasks do not necessarily correspond to physical copies within the machine; this is covered in the section on mapping a Sequoia program to a task machine. In general, copies only physically occur when absolutely required, such as when the calling task passes an array that is located in one memory module to a callee subtask whose argument data lives in a different memory module.

Relationship to the Built-in copy Operator

Passing array blocks to subtask calls and using them as arguments to the copy operator are the only two ways that array blocks can be used in Sequoia, and in fact, these two usages have the same semantics.

Consider the following example of using the copy operator to copy a 1D array block of the source array A to a 1D array block of destination array B, where each array is an array of float scalars.

copy(B[IdxB], A[0:100:2;50]);

This could have been implemented by the programmer by writing their own MyCopy task, such as:

void task<leaf> MyCopy::Leaf(out float Dst[N], in float Src[N])
{
    for (unsigned int i = 0; i < N; i++) {
        Dst[i] = Src[i];
    }
}

and then calling the task as follows, rather than the above call to the copy operator:

MyCopy(B[IdxB], A[0:100:2;50]);

(The value N in the MyCopy::Leaf task example is an array size parameter; these are described in the Array Size Parameters section).

Parameters

Sequoia tasks have two different types of parameters, tunable parameters and array size parameters.

void task<inner> VectScale::Inner(in float A[128], in float x, out float Y[128])
{
    tunable BLKSIZE;
         
    unsigned int numBlks = 128/BLKSIZE;
    for (unsigned int i = 0; i < numBlks; i++) {
        VectScale( A[i*BLKSIZE;BLKSIZE], x, Y[i*BLKSIZE;BLKSIZE] );
    }
}

void task<leaf> VectScale::Leaf(in float A[N], in float x, out float Y[N])
{
    for (int i = 0; i < N; i++) {
        Y[i] = x * A[i];
    }
}

void task<leaf> Conv1d::Leaf(in float A[N+U-1], in float H[U], out float C[N])
{
    for (unsigned int n = 0; n < N; n++) {
        C[n] = 0;
        for (unsigned int u = 0; u < U; u++) {
            C[n] += H[u] * A[n+u];
        }
    }
}

    c0 * p0 + c1 * p1 + ... + cn * pn + c

void task<leaf> Conv2d::Leaf(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N])
{
    for (unsigned int m = 0; m < M; m++) {
        for (unsigned int n = 0; n < N; n++) {
            C[m][n] = 0;
            for (unsigned int u = 0; u < U; u++) {
                for (unsigned int v = 0; v < V; v++) {
                    C[m][n] += H[u][v] * A[m+u][n+v];
                }
            }
        }
    }
}

Task Instances

Sequoia task variants are parameterized in several ways.

• Tunable parameters are compile-time integer constants.
• Array size parameters are computed from the actual runtime sizes of a task's argument arrays, though these can also be statically determined and treated as compile-time task parameters in many cases.
• Task callsites don't refer to the specific task variant that is being called, instead just calling a "base" task name.
• Local arrays in a task, including its arguments, are "abstract" collections of data which don't refer to any machine-specific details such as the memory levels in the target machine in which they reside, their layout within a physical memory module (pitch, row- vs. column-major, etc.), and whether they are distributed across multiple physical memory modules (block-cyclic, etc.).
• Control logic in a task doesn't refer to the specific control processor on which it will execute in a target machine.

All of these program parameters are left unspecified in the Sequoia source code and are set by the programmer at compile time during the process of mapping the Sequoia program to a specific target machine.

The process of filling in all of a task variant's parameters is called instantiating the task variant, and a task variant which has all of its parameters filled in is called a task instance. A task instance is a task variant that has been specialized for a specific target machine.

The same task variant can be instantiated multiple times to become multiple different task instances.

See the Sequoia Mapping Reference for details of how Sequoia's abstract tasks are instantiated for a target machine.

Task Variant Call Graph

A Sequoia program consists of a set of abstract, parameterized task variants. The task variant call graph is a figure in which the parameterized variants are nodes and edges represent possible caller-callee relationships. Note that each subtask callsite in a task's body just refers to the "base" task name, and not to the specific variant which is being called, and hence there may be a number of task variants that may be called from any given callsite.

Consider the following example Sequoia program (which implements a 1D FFT using a recursive, divide-and-conquer algorithm). The leaf task bodies aren't shown.

typedef struct { float re; float im; } cmplx;

void task<inner> FFT::InnerVariant(inout cmplx A[N], in cmplx W[N-1])
{
    Butterfly(A[0:N/2;], A[N/2:N;], W[0:N/2;]);
    for (int i = 0; i < 2; i++) {
        FFT(A[i*N/2;N/2], W[N/2:N-1;]);
    }
}

void task<leaf> FFT::LeafVariant(inout cmplx A[N], in cmplx W[N-1])
{
    // Leaf task body not shown
}

void task<inner> Butterfly::InnerVariant(inout cmplx A[N], inout cmplx B[N], in cmplx W[N])
{
    tunable T;
    for (int i = 0; i < N/T; i++) {
        Butterfly(A[i*T;T], B[i*T;T], W[i*T;T]);
    }
}

void task<leaf> Butterfly::LeafVariant(inout cmplx A[N], inout cmplx B[N], in cmplx W[N])
{
    // Leaf task body not shown
}

This is represented as the following task variant call graph.

The "leaf" and "inner" task terminology comes from this notion of a task call graph:

• Leaf tasks are at the leaves (or edges) of the graph, and the intent is that they will perform the bulk of the arithmetically-intensive computation of the Sequoia application on the target machine's processing elements. Leaf tasks don't call other tasks.
• Inner tasks are the inner nodes of the graph, and the intent is that they will mostly perform a "control" role, and won't perform much of the arithmetically-intensive computation of the Sequoia application. The function of inner tasks is to decompose a program by calling subtasks.

Introduction to Sequoia's Iteration Constructs

Sequoia supports all of the C iteration constructs (while, for, and do). Although some optimizing compilers are able to analyze such loops in simple cases and parallelize them, in general, these are all sequential, and possibly data-dependent iteration constructs. Consider the following example inner task, which blocks its argument arrays into length-T subarrays that are passed to subtask calls.

void task<inner> VectScale::Inner(in float A[N], in float x, out float Y[N])
{
    tunable T;
    unsigned int numBlks = (128+T-1)/T;
    for (unsigned int i = 0; i < numBlks; i++) {
        VectScale( A[i*T;T], x, Y[i*T;T] );
    }
}

Given that for is a sequential loop, the semantics here are that the VectScale subtask will be called on array blocks A[0;T] and Y[0;T] in iteration i=0, and when this subtask returns, VectScale will again be called, this time on array blocks A[T;T] and Y[T;T] in iteration i=1, and so on.

Clearly, all of the VectScale subtask calls made in the above program are independent, since (1) they operate on non-overlapping ranges of arrays A and Y, and (2) it is known that the subtask calls are side-effect-free as a consequence of the fact that all tasks run in isolation on private copies of data, and thus the VectScale subtask calls should be able to run in parallel, if there are parallel exectuion resources available in the hardware.

To make it explicit when subtasks can be executed in parallel, and to allow the programmer to express their iteration spaces using compiler-analyzable loops in general, Sequoia adds three iteration constructs to the set that C provides: mappar, mapseq, and mapreduce. These are conceptually similar to the map and reduce operators of functional languages: they express a task call being applied to every member of a collection of array blocks.

mappar

The same example task as in the introduction section, but using the Sequoia mappar construct ("map in parallel") instead of a C for loop, is as follows:

void task<inner> VectScale::Inner(in float A[N], in float x, out float Y[N])
{
    tunable T;
    unsigned int numBlks = (128+T-1)/T;

    mappar (unsigned int i = 0 : numBlks) {

        VectScale( A[i*T;T], x, Y[i*T;T] );
    }
}

This syntax specifies that each VectScale subtask call can occur in parallel, or in any arbitrary sequential order. Each subtask call has the same "copy in, copy out" task calling semantics as if it were called directly by its parent task (rather than inside a mappar), with the copies between the parent task's and each child's namespace implied by these semantics all happening in parallel.

In the example above, the VectScale task instance correponding to i=0 will copy the array block A[0;T] and the scalar x to its local namespace, compute their product, and copy the result back into the array block Y[0;T], while potentially simultaneously, the i=1 VectScale task instance will copy A[T;T] and x to its local namespace, compute their product, and copy the result back into Y[T;T], and so on for the rest of the mappar iterations.

Syntax

The mappar iteration range specifies how many parallel task calls to make. Its syntax is as below; this is explained in detail in the grammar section.

mappar(type loopvar = start : end) { taskcall(); }

There is an implicit "loopvar++" in the construct, and start must be less than or equal to end for there to exist any iterations to be executed (although it's not an error if start > end). As with the element ranges in the array block notation, the iteration range is non-inclusive of the end value. For example, if the range was (int i = 5 : 9), then the loop variable i would take on the values 5,6,7,8.

Syntactic Rules

Some syntactic rules for mappar are as follows:

• The loop variable must be declared inside the mappar header, and it can be of any integer type.
• The body of the mappar construct must consist of a single task call.
• Any scalar arguments of the subtask called inside a mappar must be declared as in in the subtask's argument list; inout and out scalar arguments are not permitted, since undefined behavior would result if parallel subtasks were copying to the same output variable.

Unlike scalar subtask arguments, array block subtask arguments may be in, inout, or out, though the programmer has the responsibility to ensure that there is no input-output or output-output aliasing of array blocks, either within an iteration (which is the same constraint that applies to any task call), or across iterations; see the section on undefined behavior for details.

mapseq

The mapseq (map sequential) iteration construct is syntactically the same as mappar, with the difference being that its iterations are executed serially, and not in parallel. It is essentially a more constrained version of a C for loop.

The syntactic rules for mapseq are the same as mappar except for the rule dealing with scalar arguments of the called subtask; in mappar iteration spaces, subtasks may only have in arguments, while in mapseq iteration spaces, subtasks may also have inout and out arguments. Since the subtask calls occur sequentially, with each iteration's call completing before the next iteration's call begins, the resultant values in scalar variables passed to such subtask arguments are well defined.

Array blocks that are passed as arguments to a subtask inside a mapseq construct may freely overlap across iterations, but overlapping array blocks that are passed to the same iteration's subtask call will still result in undefined behavior if there is input-output or output-output aliasing, just as with any task call; see the section on undefined behavior for details.

The main utility of a mapseq iteration construct over a C for loop is its ability to be used in a Sequoia nested iteration space.

mapreduce

Background

Sequoia's third iteration construct, mapreduce, is inspired by the reduce operator of functional languages, in which a collection of data is "collapsed" or "reduced" to a single data item. An example of a reduction is summing the numbers of an array: the input is a sequence of numbers, and the output is a single number, into which every number in the array was summed.

A reduction has two components: a collection of data items, and a combiner function which take two inputs, a data element from that collection and a value representing a partial aggregation of data elements, and produces as a single output an updated partial aggregation. In the example of summing the numbers of an array, the combiner function takes a single array element and a running tally as inputs, adds the array element to the running tally and returns it as an updated running tally. Once all the array elements have been processed, the running tally value will be the full sum of the array's elements.

An important property of reductions is that they can be done in parallel, since the order that elements are aggregated isn't important. This assumes that the combiner function is both associative and commutative.

Sequoia Reductions

In Sequoia, the mapreduce construct allows the epxression of such reductions, though in a slightly different way. A mapreduce statement is syntactically similar to a mappar statement, and it runs in two phases. First, the mapreduce iterations are run in parallel, just as with a mappar, and second, once all iterations have completed, a combining phase occurs, in which a combining function is applied to all parallel results of the first phase, collapsing them into single elements. Only after the combining phase is complete will control return to the calling task.

Combiner functions may be either inner tasks or leaf tasks; see the section on mapping the Sequoia program to the target machine for details.

As an example, consider the histogram program below. This program takes as input an array of numbers in the range 0:B, and counts (or "bins") how many occurrences of each number there are in the array, returning these counts in the bins array.

void task<inner> Histo::Inner(in int data[N], inout int bins[B])
{
    tunable T;
    unsigned int numBlks = (N+T-1)/T;
    mapreduce (int i = 0 : numBlks) {
        Histo(data[i*T;T], reducearg<bins, HistoCombiner>);
    }
}
    
void task<leaf> Histo::Leaf(in int data[N], inout int bins[B])
{
    for (int i = 0; i < N; i++) {
        bins[data[i]]++;
    }
}
    
void task<leaf> HistoCombiner::Leaf(in int bins1[B], inout int bins2[B])
{
    for (int i = 0; i < B; i++) {
        bins2[i] += bins1[i];
    }
}

To get more concrete, suppose that this program was run on a machine with 16 parallel PEs, and there were numBlks=1024 iterations to the mapreduce construct in the Histo::Inner task. The program behavior would be as follows.

• The parent Histo::Inner task would reach the mapreduce statement.
• The mapreduce would be parallelized 16 ways, so that each of the 16 PEs would execute 1024/16 = 64 iterations of the mapreduce.
• Each PE would execute its 64 Histo::Leaf subtask calls sequentially, with each iteration updating a local copy of the bins array. The 16 PEs would all be doing this in parallel, and thus there would be 16 copies of the bins array in the system.
• Once all the PEs are finished their 64 iterations, each would have a bins array that represents the histogram of one sixteenth of the full input array; these are "partial" results, which need to be combined together to yield a histogram of the full input array.
• The 16 partial results, each a bins array in a PE, would be combined together in the combining phase, using the HistoCombiner::Leaf task. The compiler or the runtime system is responsible performing the combining phase, and a simple "tree combining" approach will be used.

Reducing Multiple Arguments

More than one argument can be reduced in a single mapreduce construct, such as in the following example, which both histograms numbers, as above, and also sums them all up.

void task<inner> HistoAndSum::Inner(in int data[N], inout int bins[B], inout int sum)
{
    tunable T;
    unsigned int numBlks = (N+T-1)/T;
    mapreduce (int i = 0 : numBlks) {
        HistoAndSum(data[i*T;T], reducearg<bins, HistoCombiner>, reducearg<sum, SumCombiner>);
    }
}
    
void task<leaf> HistoAndSum::Leaf(in int data[N], inout int bins[B], inout int sum)
{
    for (int i = 0; i < N; i++) {
        bins[data[i]]++;
        sum += data[i];
    }
}
    
void task<leaf> HistoCombiner::Leaf(in int bins1[B], inout int bins2[B])
{
    for (int i = 0; i < B; i++) {
        bins2[i] += bins1[i];
    }
}

void task<leaf> SumCombiner::Leaf(in int sum1, inout int sum2)
{
    sum2 += sum1;
}

Note that each reduction argument of the task call is combined independently, using its own combiner function.

Reduction Arguments

Notice that the arguments being reduced in the task called inside the mapreduce construct are inout. This is required for reduction arguments. Further, the combiner task must have a signature like that in the examples above: it must have two arguments of the same type as the reduction argument, the first being in and the second being inout.

If the mapreduce is parallelized over multiple PEs, then the local copy of the reduction variable (that is being aggregated into) will be initialized to the value passed in to the inout argument. In the above example, this would imply that the bins array and the sum scalar should both be zeroed in the code that makes the initial call to HistoAndSum::Inner.

Syntactic Rules

The syntactic rules for mapreduce are as follows; these are the same as for mappar, except for the way in which reduction arguments are handled.

• The loop variable must be declared inside the mapreduce header, and it can be of any integer type.
• The body of the mapreduce construct must consist of a single task call.
• Any non-reduction scalar arguments of the subtask called inside a mapreduce must be declared as in in the subtask's argument list; inout and out scalar arguments are not permitted, since undefined behavior would result if parallel subtasks were copying to the same output variable.
• Reduction arguments (array and scalar) of the subtask must be inout.

Unlike scalar subtask arguments, array block subtask arguments may be in, inout, or out, though the programmer has the responsibility to ensure that there is no input-output or output-output aliasing of array blocks, either within an iteration (which is the same constraint that applies to any task call), or across iterations; see the section on undefined behavior for details.

Nested Iteration Constructs

Sequoia's three iteration constructs may be nested around a single task call, as in the following example program:

void task<inner> MatrixMult::Inner(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    tunable Mblk, Pblk, Nblk;
    mappar (int i = 0 :  M/Mblk) {
        mappar (int j = 0 :  N/Nblk) {
            mapreduce (int k=0 : P/Pblk) {
                MatrixMult(A[i*Mblk; Mblk][k*Pblk; Pblk],
                           B[k*Pblk; Pblk][j*Nblk; Nblk],
                           reducearg);
        }
    }
}

In addition, as a shorthand, multiple loops may be defined within a single iteration statement, such as the following (equivalent) version of the above example:

void task<inner> MatrixMult::Inner(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    tunable Mblk, Pblk, Nblk;
    mappar (int i = 0 :  M/Mblk,
            int j = 0 :  N/Nblk) {
        mapreduce (int k=0 : P/Pblk) {
            MatrixMult(A[i*Mblk; Mblk][k*Pblk; Pblk],
                       B[k*Pblk; Pblk][j*Nblk; Nblk],
                       reducearg);
        }
    }
}

The rules for such nests of iteration constructs are as follows:

• The loop variable for each iteration dimension must be unique within the nest.
• Any combination of nested mappar and mapseq constructs is permitted.
• A mapreduce construct must be innermost in the nest, and there may be at most one mapreduce iteration dimension.

Iteration Construct Grammar

The following grammar details the syntax of the three Sequoia iteration constructs.

iter-stmt -> mappar-stmt
          -> mapseq-stmt
          -> mapreduce-stmt

mappar-stmt -> "mappar" "(" iter-range { "," iter-range } ")" "{" body-stmt "}"

mapseq-stmt -> "mapseq" "(" iter-range { "," iter-range } ")" "{" body-stmt "}"

mapreduce-stmt -> "mapreduce" "(" iter-range ")" "{" reduce-task-call-stmt "}"

body-stmt -> iter-stmt
          -> task-call-stmt

iter-range -> loopvar-type loopvar-ident "=" start-expr ":" end-expr

loopvar-ident -> scalar-var-ident

start-expr -> expr

end-expr -> expr

task-call-stmt -> task-ident "(" task-arg { "," task-arg } ")" ";"

reduce-task-call-stmt -> task-ident "(" reduce-task-arg { "," reduce-task-arg } ")" ";"

task-arg -> array-block
         -> scalar-var-ident

reduce-task-arg -> task-arg
                -> "reducearg" "<" task-arg "," task-ident ">"

scalar-var-ident -> var-ident

The base terms in this grammar are:

• expr: A general C expression that evaluates to an integer rvalue. The terms in the expression can be constants, variables, array elements, parameters, or any other term that can be an rvalue.
• type: Any C integer type (e.g.) unsigned int, long, etc.
• var-ident: A variable identifier (name).
• array-block: A Sequoia array block, which has the grammar described on the Array Block Grammar page.

Instantiating Tasks

A Sequoia program is comprised of a set of abstract, parameterized task variants, and the process of mapping such a Sequoia program to a target machine consists of instantiating the abstract tasks, yielding a set of task instances.

Tasks contain four types of contructs which must be mapped to a target machine.

• Tunable parameters; these must be set to compile-time constant integer values.
• Program variables (both scalars and arrays); every data object must be placed in a concrete memory level of the machine. Further, array variables may have their layout within a memory level specified as a mapping directive.
• Control constructs, including C control statements (for, if, while, etc.), Sequoia iteration statements (mappar, mapseq, etc.), and code that operates on scalar variables in general; these control constructs must all be assigned to the control processor in the target machine that will execute them.
• Task callsites; a callsite only names the "base" task which is called, not the variant or instance. Mapping directives control which instance is called at every task callsite in the program.

The process of instantiating a task consists of making all of the above parameter choices and mapping decisions. A task instance is a task variant which has been specialized for a target machine by mapping all the above constructs.

As a running example for the explanations in the subsections of this section, consider the following implementation of matrix multiplication:

void task<inner> MatMul::Inner(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    tunable Mblk, Pblk, Rblk;
    mappar (int i = 0 : M/Mblk,
        mappar (int j = 0 : N/Nblk) {
            mapseq (int k = 0 : P/Pblk) {
                MatMul(A[i*Mblk;Mblk][k*Pblk;Pblk],
                       B[k*Pblk;Pblk][j*Nblk;Nblk],
                       C[i*Mblk;Mblk][j*Nblk;Nblk]);
            }
        }
    }
}

void task<leaf> MatMul::Leaf(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < P; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

The above implementation multiplies input matrices A and B and accumulates the result into matrix C, decomposing the algorithm by splitting up the problem of multipling an M*P matrix by a P*N matrix into subproblems which multiply submatrices of sizes Mblk*Pblk and Pblk*Nblk together.

The task variant call graph corresponding to this program is as follows:

Creating Task Instances

The first step in instantiating a program's tasks is actually specifying what instances are going to be created. Suppose that the matrix multiplication running example program is to be mapped to a Cell target machine with the following abstract machine model, and that the program will be operating on very large (many-GB) matrices that are staged on disk.

The programmer would create three task instances in this case, one instance of MatMul::Inner to decompose the large (on-disk) matrices into medium-sized submatrices that would fit in machine's main memory, a second instance of MatMul::Inner to split the main-memory medium-sized submatrices up into small, LS-sized sub-submatrices, and then an instance of MatMul::Leaf to actually perform a small matrix multiplication operation on the Cell SPEs. These three instances are illustrated in the following task instance call graph:

Mapping Data

Every program variable must reside in a specific memory level of the target machine, and it's typically the case that the decision about what task instances to create is interlinked with the decision about where data will live and how much space it will take.

In the matrix multiplication running example, the data objects in the task instances will be mapped as follows:

• MatMulInstLarge : A, B, C -> Memory level 2 (disk)
• MatMulInstMedium : A, B, C -> Memory level 1 (main memory)
• MatMulInstSmall : A, B, C -> Memory level 0 (LS)

This is illustrated in the updated task instance call graph below:

Setting Tunables

Each task instance will have its own "versions" of the task variant's tunable parameters, and the programmer must specify a compile-time constant for every tunable in every instance when mapping the program to a machine.

The tunables in the matrix multiplication running example are used to set the submatrix sizes that are passed to subtask calls. They will be set as follows:

• MatMulInstLarge: Mblk = Pblk = Nblk = 8192
• MatMulInstMedium: Mblk = Pblk = Nblk = 64

These numbers were chosen to arrive at arrays in each level that are as large as possible, by the following method.

• For a given memory level, consider the amount of space that there is to work with; on this machine, this is 256KB for level 0 and 2GB for level 1.
• Divide this amount by 3, since 3 submatrices will be stored simultaneously.
• Divide this amount again by 4, since the tunables set the number of array elements, each of which is a 4-byte floating point value.
• Divide this amount again by 2, since the loops will be double-buffered (a.k.a. software-pipelined); see the section on mapping control for details.
• For simplicity, just make the submatrices square, and so Mblk, Pblk, and Nblk are all equal to the square root of the remaining amount.

The selection of tunable values is illustrated in the updated task instance call graph below:

Note that the most common use of tunable values in Sequoia is to set array block sizes, and in particular, the "max" field of array blocks may only refer to tunable and array size parameters.

The amount of freedom that a programmer has to choose tunables depends upon the particular Sequoia application and the particular machine being mapped to. For example, a program may be written assuming that a tunable value will evenly divide some other application parameter, and on a machine such as Cell, hardware alignment constraints require that the start addresses of array blocks be aligned on 16-byte boundaries; each of these can constrain the space of "valid" values that the tunables can be set to.

In general, the heuristic that a programmer should use when setting tunable values is to try to make the arrays that reside in fixed size, local memories as large as possible without exceeding their capacity. Also, it's common for a programmer to try out a handful of choices for their program's tunable values before choosing the ones that yield the highest program performance.

Mapping Control

Just as data objects in a Sequoia program must be mapped to physical storage locations in the target machine, so must control statements be mapped to processors that will execute them.

Sequoia draws a distinction between control and computation in a program, though the distinction is really a difference of the intent of the code, rather than its syntax.

• A Sequoia leaf task encapsulates a program's computation, in that the intent is that the code in a leaf task will be executed on the efficient processing elements of the target machine, such as the SPEs in Cell.
• Sequoia inner tasks can also use arbitrary C expressions and control flow statements, including C loops (for, while, etc.) arithmetic operations ("+", "-", etc.), and in addition, they can use Sequoia's iteration constructs. In the Sequoia world, all of these inner task statements are generally referred to as being control, as the intent is that the logic in an inner task will serve the purpose of decomposing a problem to a small enough size that it will fit into a local memory and a leaf task will be able to perform the "actual computation" of the program.

All inner task control constructs must be mapped to a control processor in the target machine. This is the processor that will execute the statements.

Current Mapping Interface

It would be unwieldy and impractical for a mapping directive to be required for every operation in an inner task, such as the addition and assignment statement "int x = y + z;", and yet statements such as this must be executed somewhere. A general method that would allow the programmer to conveniently map control operations as a group is under development, however there is a mapping interface supported that provides a working solution.

The current mapping interface that Sequoia supports handles the mapping of control by associating a control level with every Sequoia iteration construct (mappar, mapseq, and mapreduce), and then implicitly placing every other type of control operation in the same control level as its "closest" parent iteration construct. The mapping interface will assign a memory level in the target machine to each such Sequoia iteration construct, and this will cause the Sequoia compiler to emit code for that loop into a file that will be executed by a control processor at that memory level. The exception to this rule is a leaf task call; leaf tasks are always "controlled" by the level-0 controller.

If a Sequoia loop that is running on a control processor in level L contains a nested Sequoia loop whose control level is set to level L-1, then this will result in the level-L processor calling into the L-1 processor to execute the contained loop; this call will be emitted as the appropriate communication operation on the target machine by the Sequoia compiler. For example, on a Cell machine, if a mapseq that is running in the PPE has a nested mappar inside it that is set to run in the SPE level, then each PPE mapseq iteration a thread call will be made from the PPE to the SPE to execute the nested mappar contruct.

In the matrix multiplication running example, the control level of the Sequoia iteration constructs would be mapped as in the following updated task instance call graph diagram.

Sequoia Loop Transformations

In addition to being assigned to a memory level, mapping a Sequoia loop (mappar, mapseq, or mapreduce) to a machine involves specifying any (or none) of the following set of loop transformations that will be performed on the loop.

• SPMD: If the loop is mapped to a memory level, such as level 0 in the Cell model being used in the running example, that has parallel control processors, then the loop can be parallelized over these processors. The Sequoia compiler/runtime will assign an equal share of the loop's iterations to each processor. Note that only mappar and mapreduce can be parallelized; mapseq cannot. This process is also referred to a "SPMD-izing" the loop, since the same program code will be run on each of the parallel control processors; that is, they will all run the same loop, with different processors executing different iterations.
• SWP: A loop can be software-pipelined (also referred to as multi-buffered), a transformation which can enable asynchronous operations to overlap with each other by running multiple iterations simultaneously (if the hardware supports asynchronous operations). An example of the utility of this is software-pipelining level-0 loops in the running example Cell target; the hardware supports asynchronous DMA operations that can be issued by the SPE processors, and if a level-0 parallel loop is software-pipelined, then the DMA operations from one iteration can potentially be overlapped with leaf task executions from other iterations, allowing the program to effectively utilize the machine's resources.

Note that if a loop is software-pipelined, then the amount of space that each iteration has to work with will be reduced, since multiple iterations will be running in parallel.

In the matrix multiplication running example, these transformations would be applied as follows, yielding a fully mapped/instantiated program, with all mapping details having been filled in. This mapped program represents a concrete implementation of the MatMul abstract Sequoua code.

There are 8 parallel SPEs in level 0 in the Cell machine model, and thus the program will be parallelized 8 ways over these processors, though this is acheived via a 2D parallelization mapping. Further, at both the disk-to-memory and memory-to-LS interfaces there are asynchronous transfer operations provided by the underlying hardware/OS, and so at each interface in the program a loop was software-pipelined to acheive overlap between computation and communication.

Data Layout and Distribution

Arrays can be laid out in various different ways within a memory module, for example in row-major, column-major, or block-major order, and they can be distributed across multiple parallel memory modules with a virtual memory level using the standard array distributions that array languages support (block-cyclic, etc.)

Documentation and examples of these mapping interfaces are yet to be written.

Statically Bounding Array Sizes

As Sequoia deals with the explicit management of fixed-size memory modules, it is important for the Sequoia compiler to be able to statically determine the maximum possible amount of space that data objects may consume, and this is something that is done during the process of mapping a program to a target machine.

Downward Constant Propagation

Consider the matrix multiplication running example from the section on instantiating tasks.

void task<inner> MatMul::Inner(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    tunable Mblk, Pblk, Rblk;
    mappar (int i = 0 : M/Mblk,
        mappar (int j = 0 : N/Nblk) {
            mapseq (int k = 0 : P/Pblk) {
                MatMul(A[i*Mblk;Mblk][k*Pblk;Pblk],
                       B[k*Pblk;Pblk][j*Nblk;Nblk],
                       C[i*Mblk;Mblk][j*Nblk;Nblk]);
            }
        }
    }
}

void task<leaf> MatMul::Leaf(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < P; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

In this example, the program was mapped on to a Cell processor, yielding the following task instance call graph that illustrates the various mapping decisions that were made.

Recall that the semantics of array size parameters are that at runtime, they are computed from the actual sizes of the array arguments that are passed to the task instance call. It is often the case, however, that despite this "dynamic" definition, they can be determined statically by the compiler when the program is mapped to a target machine; this is a deliberate design point of the Sequoia language.

Consider the array size parameters (M, P, and N) in the MatMulInstSmall instance in the above figure. Since (1) this particular mapping of this program has specified that the MatMulInstSmall is only called by the MatMulInstMedium instance, (2) the MatMulInstMedium instance has tunable values Mblk = Pblk = Nblk = 64, and (3) these tunable values are used to set the array block "max" sizes of the arguments to the MatMulInstSmall call, the compiler is able to propagate information "downwards" through this call chain and determine that the array size parameters in the MatMulInstSmall instance must are constrained such that M <= 64, P <= 64,and N <= 64. By a similar downward propagation, the array size parameters of the MatMulInstMedium instance can be statically determined to be M <= 8192, P <= 8192, and N <= 8192, however there is no information available for the compiler to determine the array size parameters of the MatMulInstLarge instance; these parameters are "dynamic". This is illustrated in the following updated task instance call graph for this example program.

After the programmer's mapping decisions have been applied, resulting in instantiated tasks with tunables set to constant values, the compiler performs a "downward constant propagation" pass, where for each task instance, starting at the program entry points and working "downwards" through the task instance call graph from caller to callee, the "max" values of all array blocks that are passed as arguments to a subtask call will be propagated to the subtask's instance's array size parameters, if possible. And once a program's array size parameters are bounded to some statically known value, the maximum possible sizes of the arrays in a task will also be known, since (1) argument arrays are sized exlusively by array size parameters, and (2) locally declared arrays within a task may only be sized by array size or tunable parameters, and the latter are compile-time constants. Once the maximum possible sizes of a task's arrays are known, the compiler/runtime can statically allocate space for them in explicitly managed, fixed-size local memories (if they fit).

Array Size Preconditions: Trust But Verify

The above compiler pass will not always be successful in determining static (compile-time) values for all array size parameters in the system. The following example illustrates two different cases where this isn't possible.

void task<inner> MyTask::Inner(inout float A[N])
{
    MyTask2(A);
    mappar (unsigned int i = 0 : 4) {
        MyTask3(A[i*N/4;N/4]);
    }
}

Suppose that this task has been instantiated, to MyTaskInst (say). If the above "downward" constant propagation compiler pass was able to statically bound the value of the argument's array size parameter N, then a static bound will be able to be propagated to the calls to the MyTask2 and MyTask3 instances. If, however, N is "dynamic", just as the array size parameters of the MatMulInstLarge instance in the above matrix multiplication example are, then niether of these task calls will enable the compiler to propagate any static bounds do the callee instances, since in the call to MyTask2, the full (dynamically sized) array A is passed as the argument, and in the call to MyTask3, the size of the argument is at most N/4, which doesn't help since this expression is not staically bounded if N isn't.

In general, there are occasions when the downward propagation of constants by the compiler isn't sufficient to statically bound all array size parameters (and hence all array sizes) in the program. This fact could be problematic, however, due to the requirement that only data objects whose size is statically bounded can be copied to a fixed-size, software-managed memory such as the Cell's LS. To solve this dilemma, the Sequoia mapping interface provides the ability to specify an array size precondition on a task instance's argument array.

An array size precondition on a task instance simply specifies that the instance may only be called if its argument array's size would be at most (or exactly) a certain value (at runtime). If this condition isn't true, then it would be a runtime program error to call the task instance.

This same mapping interface also supplies a static bound for the size of an array argument to the task; the programmer "plugs in" a constant value for a bound on an array's size, just as they do when setting tunables. The compiler will then propagate this constant size downward just as it would any other array size that it had statically determined a bound for.

In the above example, supposing that the MyTaskInst instance was called with a dynamically sized array, the programmer could provide an array size precondition for the MyTaskInst instance which would force the compiler to treat its argument A[N] as having a statically known bound on its size, which would in turn permit the MyTask2 and MyTask3 instances called by MyTaskInst to have a static bound propagated to their argument arrays.

The compiler has a "trust but verify" approach with array size preconditions; it will statically take it on faith that the arrays will be bounded by the size the programmer tells it, but at runtime, checks will be performed to ensure that the array does in fact satisfy the instance's precondition.

Task Calling Conditions

Recall that a callsite in a Sequoia task doesn't refer to the specific instance that is being called; rather, it just refers to the "base" task name, and the programmer will specify which instance is to be called by each callsite when instantiating the task, during the process of mapping the program to a target machine.

The Sequoia mapping interface actually allows the programmer to specify a list of possible instances which may be called from a given callsite, with calling conditions on each instance (not to be confused with the array size preconditions described in the section on statically bounding array sizes).

The semantics of providing a list of instances as possible targets are that at runtime, the calling conditions of each target instance will be evaluated, starting from the head of the list, until one of the instances has its calling conditions evaluate to true; this is the instance which will be called.

Calling conditions may be on the size of an array in the calling task, for example, "call instance InstX at this callsite if array A has fewer than 1024 elements". In addition, other types calling conditions may be defined in the mapping interface for a specific target.

Note that the compiler will still perform its downward propagation of constants pass through callsites which have a list of possible targets with calling conditions, by evaluating the calling conditions statically where possible.

Contractual Compiler Optimizations

The Sequoia compiler and runtime is one particular implementation of the Sequoia language, and it's possible that there could exist completely different systems which take Sequoia code as an input language. This section describes the optimizations which any Sequoia implementation must perform; these can be considered a "contract" between the programmer and the system, and the programmer may rely on these optimizations being performed when writing their code. (The Sequoia compiler performs these optimizations, and more.)

CBVR Copy Elimination of Stride-1 Range Array Blocks

The task calling semantics of the Sequoia language are call-by-value-result (CBVR), also known as "copy in, copy out". Clearly, if every task call in the program required a physical memory copy of array arguments then performance would be very poor, but the copies may only be semantic copies; that is, as far as the program is concerned, the copy did occur, but "under the hood", the Sequoia compiler or runtime system may have optimized the copy away, converting it instead into an alias or reference to another array if it proves that it is safe to do so.

There is a very common case of argument passing, in which a multi-dimensional stride-1 range array block is passed as an argument to a subtask call, such as in the following example.

void task<inner> MyTask1::Inner(in float A[M][N], out float B[M][N])
{
    tunable T, U;
    MyTask2(A, B);
    MyTask2(A[0;T][u0:u1;U], B[0;T][u0:u1;U]);
}

void task<inner> MyTask2::Inner(in float X[U][V], out float Y[U][V])
{
    ...
}

Suppose that these tasks were instantiated as in the following diagram:

In the event that the mapping interface specifies that the MyTask1Inst instance's array A and the MyTask2Inst instance's array X are in the same memory level, the semantic copy from the namespace of MyTask1Inst into MyTask2Inst that occurs on a task call would actually be a copy within the same memory module, and further, the calling semantics of tasks specify that when MyTask1Inst executes the task call "MyTask2(A);" (say), it will actually pause there until the child task returns, and thus, the compiler can actually alias array X to array A and not perform an underlying physical copy of the data. As far as the program is concerned, however, arrays X and A are completely different physical objects. Similarly, arrays Y and B can be aliased to the same physical array object.

In essence, the compiler is taking a language with copy semantics on task calls and optimizing away unnecessary copies when it is safe to do so. The Sequoia compiler actually eliminates copies in other cases too (if safe), though the basic copy elimination of stride-1 range array arguments to task calls is a guaranteed feature of any Sequoia implementation.

Copy Hoisting

Consider the following example, consisting of an inner task implementation from a Sequoia 2D convolution program.

void task<inner> Conv2D::Inner(in float A[M+U-1][N+V-1], in float H[U][V], out float C[M][N])
{
    tunable S, T;
    mappar (unsigned int i = 0 : (M+S-1)/S) {
        mappar (unsigned int j = 0 : (N+T-1)/T) {
            Conv2D(A[i*S;S+U-1][j*T;T+V-1], H, C[i*S;S][j*T;T]);
        }
    }
}

The language semantics are that every iteration of the nested mappar statement, the Conv2D task is called, passing array blocks of A and C and the entire array H as arguments. Suppose that the instance called at the Conv2D callsite was in a different memory level to the calling instance of Conv2D::Inner: the semantics of this code would be that every iteration, the two input array arguments would be physically copied between memory levels (which could be an expensive memory transfer operation), the subtask instance would run, and then the subtask's output data would be copied back to the calling task's C array.

Clearly, the exact same array H is passed every iteration, and it would be inefficient to recopy it every time. The compiler will perform an optimization known as "loop hoisting", also known as "loop-invariant code motion", and only perform the copy of H once, at the start of the nested mappar construct, with every iteration's Conv2D call operating on this copy.

The contractual optimization that any Sequoia implementation must perform is to identify the iteration variables that are used to describe an array block passed to a task call inside a nest of Sequoia iteration constructs and "hoist" out the copy of any arguments as far as possible.

As a second example, consider the following inner task from a Sequoia implementation of matrix multiplication.

void task<inner> MatMul::Inner(in float A[M][P], in float B[P][N], inout float C[M][N])
{
    tunable Mblk, Pblk, Rblk;
    mappar (int i = 0 : M/Mblk,
        mappar (int j = 0 : N/Nblk) {
            mapseq (int k = 0 : P/Pblk) {
                MatMul(A[i*Mblk;Mblk][k*Pblk;Pblk],
                       B[k*Pblk;Pblk][j*Nblk;Nblk],
                       C[i*Mblk;Mblk][j*Nblk;Nblk]);
            }
        }
    }
}

In this example, the array block C[i*Mblk;Mblk][j*Nblk;Nblk] doesn't depend on the k loop variable, only i and j, and so rather than copying C on every (i, j, k) iteration, it is only copied on every (i, j) iteration, with each k iteration using the same copy.