Next: Defining a Cost Up: Creating HeNCE Programs Previous: Definitions

## HeNCE Node Types

This section provides an overview of the different types of nodes that may appear in a HeNCE program. We will first summarize their use and then delve into the details of their node programs.

### Overview of HeNCE Node Types

The HeNCE language contains a number of different node types. Each type is represented by an icon. Figure 4 shows all of HeNCE's node types. Notice that all but one of the icons come in pairs.

The circle icon represents a sequential computation node. It calls a user-supplied subroutine when it executes. This node type represents the basic unit of parallelism in HeNCE. Sequential computation nodes may fire when all of their predecessors in the graph have fired.

The icons that come in pairs represent ``special-purpose'' nodes. These generally define control flow within the HeNCE graph. There must always be a subgraph between a ``begin'' and an ``end'' node. The special-purpose nodes can be thought of as graph rewriting primitives. They add subgraphs to the current HeNCE graph at runtime, based upon expressions that are evaluated at runtime.

It is legal to include special-purpose nodes within the subgraph of some other special-purpose node. For example, one can place a fan inside a loop. However, the constructs must be nested. It is not legal to interleave them.

Conditional node pairs define an ``if-then'' structure. The Conditional-Begin node program contains an expression. If the expression evaluates to TRUE (meaning non-zero, following the C language convention), the subgraph between the pairs is executed. Otherwise, it is not. Note that HeNCE does not contain an ``if-then-else'' structure. In terms of graph rewriting, the subgraph is added to the graph if the expression is TRUE. Otherwise, it is replaced by an arc. See Figure 5.

Loop node pairs define iterations much like a C ``for'' loop. The subgraph between the loop begin and the loop end node is repeated as an index variable takes on successive values. Viewed in terms of graph rewriting, the subgraph is replaced by a sequence of copies of itself. See Figure 5.

Fan node pairs create parallel structures. They replicate the subgraph between them and evaluate the replications in parallel. Figure 6 shows the effect of a Fan. The number of nodes created is determined by the Fan Begin node's program and can depend on values of runtime variables.

Pipe node pairs create a pipeline structure. Figure 6 also shows the effect of a pipe and delineates which nodes within the pipe can execute in parallel. The subgraph within the pipe is replicated, somewhat like a Fan node, but the dependence structure differs.

### HeNCE Node Programs

The precise action of a HeNCE node must be defined by the user. For example, a computation node executes a sequential subroutine, but the user must specify which subroutine. This is done by means of a textual description called the node program.

The syntax of node programs varies among HeNCE's node type. Computation nodes are the most complex and so will serve as the starting point. Discussion of special-purpose nodes will follow.

##### Computation Node Programs

Computation node programs consist of three parts, but not all nodes will need all three. The purpose of the parts is described in the list below. The parts must be entered into nodes in this order.

1. Input Declarations. The input declarations specify which variables the node will use. These variables are defined and set by predecessor nodes in the graph.

2. Subroutine Call. The subroutine call is what it sounds like- a call to a sequential subroutine that will be executed when the node fires. The call includes both the subroutine name and all actual parameters.

3. Output Declarations. The output declarations part defines new variables that are declared and set within the node and that will be made available to successor nodes in the graph.

##### Input declarations

Input declarations are of the form:

```
< [type] param-name [ = expression ] ;```
They state that a node is to find and load the variable param-name from its ancestors. If a type is not specified, then the parameter is assumed to exist in ancestor nodes, and it will retain the type declared there. If a type is specified and disagrees with the type declared by an ancestor, then HeNCE will flag an error. If no ancestors contain the parameter, then it is created and initialized to expression . If there is a type but no ancestors contain that variable and no expression is given, then it is created and initialized to a null value. The following are examples:
```
< a;
< int b = 5;
< char c[25] = "Foo";
< int d[10][15];```
The first example states to load from ancestors. The type of is inherited from the ancestor's declarations. If doesn't exist, then HeNCE will flag an error. The second example says to load the integer from ancestors, and if it doesn't exist in an ancestor, initialize it to 5. The third example is similar, except is an array of 25 char's. If no ancestor has , then 25 chars are allocated, and the first four are initialized to ``foo''. Finally, the last example retrieves the two-dimensional integer array from ancestors. If no ancestor has , then it is allocated, and all its elements are set to zero.

This is a bit counter-intuitive, since writing < int b = 5; doesn't mean that will be initialized to 5 (in other words, if the node's parent sets to 10, then will be 10, and not 5). Thus, there is an alternate input declaration form:

```
NEW '<' type param-name [ '=' expression ] ';'```
which means that the parameter will be created anew here. Therefore, if a node specifies NEW < int b = 5; , then will indeed be initialized to 5 in this node, regardless of its value (or type) in ancestor nodes.

Input parameters are for input only. They will not get sent to descendents. Thus, when a node declares a parameter for input, it is free to modify that parameter and those modifications will not be seen by any descendents.

If a node wants parameters to be loaded from ancestors and to be seen by descendents, then it can declare them to be Input/Output. This is done by substituting `<>' for `<' in the above syntax. Thus the following examples:

```
<> a;
NEW <> int b = 5;
<> char c[25] = "Foo";
<> int d[10][15];```
mean the same as above, except that after their subroutine completes, their values can be sent to descendent nodes.

#### Expressions and default parameters

Previously we stated that parameters may be initialized to expressions. Expressions may also be used to define array dimensions and subroutine arguments. An expression is defined as a combination of constants, parameters and C operators. Thus, the following are expressions:

```
5
a
b[3][5] + c * 5.0
(d != 0) ? &d : &e```
If an expression uses a parameter that is not declared, then that parameter is defaulted to be an input/output parameter. Thus, in the declaration:
```
<> a;
< int b = a;```
the first line can be omitted: Since mentions in its expression, is defaulted to an input/output parameter. Even if an expression is not used (e.g. is loaded from an ancestor, and is never initialized to ), the undeclared parameters that it uses are still defaulted to input/output parameters.

Circular references are not allowed. For example:

```
NEW < int a = b;
NEW < int b = a;```
will be flagged as an error.

#### Arrays

Arrays are declared as in C. Each dimension's specification is enclosed in square brackets. These specifications may be expressions involving other parameters. When an array is first declared, it must be with a type. This defines the size of the array, which must remain constant throughout the lifetime of the computation. If a node redeclares an array that an ancestor has already declared, then it is an error if the declarations differ in type or in the size of any dimension.

After an array has been defined, nodes may use rectangular portions of it. Thus, nodes can split up an array to perform parallel computations. In the simplest case, a node can specify a single element of an array. For example, if node 1 wants to use element of integer array , then it can declare:

```
<> p[5][6];```
or simply use it:
```
foo(p[5][6]);```
Larger, rectangular portions of arrays can also be specified by giving the dimension's low and high values. An empty dimension will default to the entire contents of the dimension. The following are examples of specifying portions of a two-dimensional array :
• : This specifies all of .
• : This also specifies all of .
• : This specifies the rectangular portion of starting with and ending with . If this is used in an expression, for example:
```
NEW <> int B[6][6] = A[0 : 5][10 : 15];```
then is created and its values are copied from that rectangular portion of . will be equal to , and will be equal to .
• : This specifies a 6-element one-dimensional array whose first value is , and whose last value is .
• : This is a 20-element one dimensional array whose first value is , and whose last value is .
• : This is a 1x6, two dimensional array whose first value is , and whose last value is .
One can use these array specifications in expressions, and one can legally specify different portions of the same array. For example, the declaration:
```
NEW <> int b[6][6] = A[0 : 5][10 : 15];
NEW <> int c[6][6] = A[1 : 6][10 : 15];```
are perfectly legal. Each portion of is considered to be a different I/O parameter. This could be the source of nondeterminacy problems if the partitions of overlap.

The current implementation of HeNCE has been written so that some expressions involving arrays are illegal. In particular, scalar parameters can not be set to array values. The reason for this has to do with implementation details and future versions of HeNCE should remove these restrictions. The following are illegal expressions:

```
NEW <> int b = c[5];
NEW <> d[1 : c[5]];
FANOUT 1 i = c[5] TO 10;
foo(d[c[5]]);```
however, the following are legal:
```
NEW <> int b[5] = c[5 : 9];
foo(c[5] + c[6]);```

#### The Subroutine Call

Each node is bound to a subroutine. The subroutine call is where the arguments to the subroutine are defined, and the return value is bound. The subroutine call is a part of the node program. The syntax of the subroutine call is:

```
[ param = ] sub-name ( [ expression [ , expression ]* ] ) ;```
For example, the following are subroutine calls:
```
foo();
update_array(&(A[r][c]));```
The first example simply calls the subroutine foo. The second calls the subroutine add with the parameters and as arguments, and binds the return value to . The last example calls update_array with the address of element of array .

Parameters may be updated by subroutines in three ways:

1. By binding it to the return parameter: e.g. foo.
2. By sending its address as an argument: e.g. foo.
3. By passing an array as an argument: e.g. foo.

If the parameter to which the return value is bound has not been declared, then it is defaulted to be output-only.

#### Output Declarations

There may be some parameters which have been created or initialized by the subroutine call. These parameters can be declared as output-only after the subroutine call. Output declarations are of the form:

```
> type param-name ;```
Thus, if node 1 wants to create the parameter and initialize it to the result of foo, then it can be declared as follows:
```
NODE 1
a = foo();
> int a;```
A major difference between output and I/O parameters is in the assumptions about allocation: If an array is declared to be an I/O parameter, then HeNCE will allocate the space for it, and initialize it from its ancestors, if any contain the array. If it is declared as output-only, however, HeNCE assumes that the subroutine will allocate the array. Moreover, the size of the output array is determined after the subroutine call, as those determining parameters might be output-only as well.

(Note: This behavior is not fully debugged in the current release of htool.) For example, suppose the subroutine reads a bunch of text from a file, and returns the length in its first parameter, and the text in its second parameter. Then the HeNCE declaration for should be:

```
NODE 0
> int len;
> char txt[len];```
Output declarations can also be used for parameters that need to be created, but aren't used in the subroutine call. For example, suppose that the array is going to be distributed among many nodes, but no one node is ever going to hold in its entirety. must be declared by some node, so that HeNCE knows its type and size; however, if it is declared as an input or input/output parameter, then HeNCE will allocate it and set its values to null. If it is declared as an output parameter, then HeNCE does not allocate it, but does note its type and size. Therefore the user can use output declarations to declare, but not allocate or use, an array.

Array parameters cannot change size during HeNCE's execution (unless a new parameter is created using NEW). For example, if we made the following declaration:

```
NODE 0
NEW <> int len = 400;
<> char txt[len];
and changes to 300, will not undergo a size change - it will remain 400 characters long.

#### Special-Purpose Nodes

Below is a description of the special-purpose nodes and their textual syntax. As stated before, special-purpose nodes all come in pairs surrounding a subgraph. In reality, special-purpose nodes aren't nodes at all, but specify graph rewriting rules. The nature of the special-purpose node, and the values of runtime variables determine how the subgraph gets written. For example, if a conditional node evaluates to false, then the subgraph does not get included in the graph's execution.

##### Conditional Nodes

Conditional nodes allow the user to choose whether or not subgraphs get executed, according to the runtime conditions of parameters. Like all other special-purpose nodes, conditionals come in begin/end pairs. The nodes between the pairs must form a subgraph. Otherwise, HeNCE will flag an error before performing any execution.

The syntax of conditional nodes are as follows:

```
'BEGINSWITCH' [ <x location> <y location> ] id '(' expression ')' ';'
'ENDSWITCH' [ <x location> <y location> ] id ';'```
The expression is like any expression discussed above. It may contain constants or parameters. All parameters are defaulted. Like C, if the expression evaluates to 0, then it is treated as false, and the enclosed subgraph is ignored. If it evaluates to true, then the subgraph is executed normally.

##### Fanout/fanin Nodes

Fanout nodes allow the user to dynamically create copies of a subgraph which will execute in parallel. Fanin nodes mark the end of the subgraph to be spawned. Their syntax is as follows:

```
'FANOUT' [ <x location> <y location> ] id ';'
var '=' expression 'TO' expression ';'
'FANIN' [ <x location> <y location> ] id ';'```
The two expression's denote a range of values for an var, which it treated as an output integer parameter. For each value of var, a separate copy of the subgraph is spawned. That copy of the subgraph may access its value of var as an integer parameter. If the first expression evaluates to a value less than the second, then no copys are spawned; execution continues from the fanin node.

##### Loop Nodes

Loop nodes are like fanout/fanin nodes, except that the copies of the subgraph are performed serially. The syntax is like the for syntax in C:

```
'BEGINLOOP' [ <x location> <y location> ] id
'(' [ var '=' expression ] ';'
expression           ';'
[ var '=' expression ] ')' ;
'ENDLOOP' [ <x location> <y location> ] id ';'```
when the loop is first encountered, an output integer parameter (var) is created, and set to the first expression . If the middle expression evaluates to non-zero, then the subgraph inside the loop is expanded and executed. When it finishes, then var is updated using the last expression , and the second expression is rechecked. If it evaluates to zero, then execution continues from the ENDLOOP. Otherwise, the subgraph is expanded and evaluated again. And so on.

A current restriction enforced by HeNCE is that the vars in the first and third expression must be the same. If the vars are not the same, the parser emits an error.

##### Pipe Nodes

Pipe nodes allow control flow to be pipelined through a subgraph. The syntax is similar to fans:

```
'BEGINPIPE' [ <x location> <y location> ] id
var '=' expression 'TO' expression ';'
'ENDPIPE' [ <x location> <y location> ] id ';'```
Again, for each value of var, a separate copy of the subgraph is spawned. However, now, for each node in the subgraph, there is an arc from its instance in one copy of the subgraph to its instance in the next copy of the subgraph (i.e. from the instance where to .

Thus, pipes allow for a more restricted type of parallelism than fanout/fanin nodes. Specifically, if node instances need to be serialized in a certain algorithm, then the pipe construct can be used effectively.

#### More on Array Passing

The internal representation of arrays has two ways of storing them: As a big 1-dimensional chunk of bytes (which is what you'd get in C if you declared an array with constant sizes: e.g.int a[4][5]; gives you a pointer to a chunk of 20 ints), and as a tree of pointers (which is what you get in C otherwise - e.g.char **argv). When HeNCE allocates an array, it allocates the chunk of bytes, and then builds the pointer-tree on top of it, so either representation can be used by the programmer. Currently, HeNCE stores arrays in row major. Thus multidimensional arrays do not work as expected in FORTRAN - the programmer is advised to stick to single-dimensional arrays.

A by-product of HeNCE's storing of arrays is that one can initialize 1-d arrays from -dimensional ones, and vice-versa. For example, the declaration:

```
NODE 0
NEW <> char a[10] = "abcdefghij";
NEW <> char b[2][5] = a;
NEW <> char c[2][5] = "abcdefghij";
<> char a[0 : 4];
null();```
is perfectly legal. Here and will both equal{"abcde", "fghij"}. Also, when HeNCE initializes such arrays, it makes them all point to separate chunks of memory. Therefore, changes to won't affect , even though the syntax might look that way. Moreover, changes to won't affect a[0 : 4] , as they both point to different chunks of memory.

HeNCE attempts to perform type conversion as much as possible. Therefore, in the following declaration:

```
NODE 0
NEW <> char a[3] = "abc" ;
NEW <> int b[3] = a;
NEW <> float c[3] = b;
NEW <> int d = 3;
NEW <> double e = d;
null()```
will be{97, 98, 99}, will be{97.0, 98.0, 99.0} and will be 3.0.

Next: Defining a Cost Up: Creating HeNCE Programs Previous: Definitions

newton@utkcs.cs.utk.edu
Wed Jun 15 15:13:55 EDT 1994