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.