next up previous contents
Next: Computational Model Up: The Communications Language Previous: Communicating in Subsets of

Expressing Run-Time Values

  A key issue is how to handle values that are not known until run time. For example, for Gaussian elimination a pivot row may be chosen based on the input dataset, then broadcast to all the other rows. With dynamic routing, this sort of thing is easily done. With scheduled routing, as much information as possible needs to be supplied to the compiler so it can determine how best to implement the operator.

Run-time values are expressed with a special compile-time construct, (runtime); this construct is a `pseudo run-time' value, since its only use is at compile time, but it represents a run-time value. Used in lieu of a constant argument, this construct indicates that the value in question will be provided by the application at run time. For example, broadcasting from an unknown row position in a $4\times 4$ matrix is expressed as:


\begin{singlespace}
\begin{verbatim}
(subset '((0 4 8 12) (1 5 9 13) (2 6 10 14) (3 7 11 15))
 (broadcast 'b (runtime)))\end{verbatim} \end{singlespace}

The possible values that a (runtime) operand can take on are limited by the operand it is used for. Thus, for a broadcast source, the run-time argument must be a valid node number from the current subset in effect; in this example, it must be in the range 0...3 .

The use of this construct is a large part of the power of COP, since it describes a limited form of data-dependency which can be implemented by using a variety of efficient techniques to avoid defaulting to pure online routing. The presence or absence of such run-time values for a given operator determines the extent to which the operator's schedule can be computed strictly at compile time, partly at compile time and partly at run time, or entirely at run time. The HLL compiler does not need to know how the compiler implements the operator, so the language does not expose where the schedule-generation actually takes place.

This construct does not indicate that an operator may (for example) deliver data to a different destination on each invocation; the value of the run-time argument must be provided before the I/O function is called, and the same value must be provided on all the nodes involved in the operation. If the operator is used within a loop, a new run-time argument may be provided each time through the loop.

Constraining Run-Time Values

An important requirement for a run-time value is that the application be able to provide as many constraints on its value as can be determined at compile-time. Without the ability to express these constraints in the language, in many cases an unknown communications pattern might have to be expressed with dynamic routing, at some performance penalty. The more information available on the run-time values, the better the compiler will be at choosing the most efficient implementations.

An important implicit constraint is the type of the operator itself. For example, a permute operator that specifies a run-time permutation yields more information than a set of stream operators with run-time sources and run-time destinations. In particular, it may be possible to efficiently generate a VFSM schedule at run-time to handle a permutation, whereas handling arbitrary communications with a run-time stream operator may require a much less efficient solution.

The (runtime) construct takes optional arguments that can be used to constrain the possible range of run-time values. The :values argument allows the application to specify that a given run-time value will only take on values from the specified list. Thus, a broadcast that may occur from one corner of the mesh or the other can be specified as:

(broadcast 'b (runtime :values '(0 15)))

A runtime value for an operator must normally be specified consistently by every node in the operator's subset. This allows for any necessary changes to be made consistently to the routers' schedules across the mesh. However, sometimes the application does not have complete knowledge on every node, and a way to express that is useful. An optional runtime argument, :distributed, indicates that knowledge of the run-time value is distributed across the mesh. For a broadcast, this means that each node only knows whether or not it is broadcasting, rather than knowing which node is broadcasting; this is expressed as:

(broadcast 'b (runtime :distributed t))

Implementations of operators which use this partial-knowledge flag can be as efficient, in some cases, as those in which all nodes have complete knowledge.



 
next up previous contents
Next: Computational Model Up: The Communications Language Previous: Communicating in Subsets of
Back to Chris Metcalf's home page