In HeNCE, the programmer is responsible for explicitly specifying parallelism by drawing graphs which express the dependencies and control flow of a program. HeNCE provides a class of graphs as a usable yet flexible way for the programmer to specify parallelism. The user directly inputs the graph using a graph editor which is part of the HeNCE environment. Each node in a HeNCE graph represents a subroutine written in either Fortran or C. Arcs in the HeNCE graph represent dependencies and control flow. An arc from one node to another represents the fact that the tail node of the arc must run before the node at the head of the arc. During the execution of a HeNCE graph, procedures are automatically executed when their predecessors, as defined by dependency arcs, have completed. Functions are mapped to machines based on a user defined cost matrix.
There are six types of constructs in HeNCE graphs; subroutine nodes, simple dependency arcs, conditional, loop, fan, and pipe constructs. Subroutine nodes represent a particular subroutine and parameter list that will be invoked during the execution of the program graph. A subroutine node has no state other than its parameter list. That is, it cannot read any global information from other subroutine nodes, nor can can it write any global variables (outside its parameter list) that will be read by other subroutine nodes. Dependency arcs represent dependencies between subroutine nodes in a HeNCE graph. The bottom window of the trace tool in Figure 1 shows a simple HeNCE graph containing only subroutine nodes and dependency arcs. This graph represents a simple fractal computation. (In the convention for drawing HeNCE graphs, they are shown to execute from bottom to top.) The initialize node, at the bottom of the graph, reads input parameters describing which part of the complex plane to use for the computation. After the initializing node (mkwork) completes, the dependency arcs from it to the compute nodes are satisfied and they may begin execution. In this case they are invoked on different parts of the complex plane. Once all of the compute nodes are finished the display procedure (kollekt) can execute and display the resulting fractal.
Figure 1: Trace mode of the HeNCE graphical interface.
In addition to simple dependency arcs, HeNCE provides constructs which denote four different types of control flow: conditionals, loops, fans, and pipes. These four constructs can be thought of as graph rewriting primitives. These constructs add subgraphs to the current program graph based upon expressions which are evaluated at runtime. Using the conditional construct the programmer may specify a subgraph to be executed conditionally. If the boolean expression attached to the begin-conditional node evaluates to true then the subgraph contained between the begin- and end-conditional nodes is added to the program graph. If the expression evaluates to false then the contained subgraph is not added. The loop construct is similar to the conditional in that it specifies a subgraph to be conditionally executed. However, the loop construct also allows iteration on a subgraph as a loop body. In other words, the subgraph making up the loop body is repeatedly added to the program graph based upon a boolean expression that is evaluated each time through the loop. The fan construct in HeNCE allows the programmer to specify a parallel fanning out and in of control flow to a dynamically created number of subgraphs. The integer expression attached to the begin-fan node is evaluated to determine how many subgraphs will be created. Each subgraph created by the fan construct executes in parallel. The pipe construct in HeNCE provides for pipelined execution of a subgraph. The expression attached to the begin-pipe node indicates whether another data item is to be piped though the subgraph. If the expression evaluates to true then another subgraph is added to the graph in order to execute the additional data item in a pipelined fashion. Thinking of these constructs as graph rewriting primitives not only provides a mechanism for specifying parallelism but also a natural way of viewing the dynamic parallelism as a graph unfolds at runtime.
Figure 2: HeNCE loop, fan, pipe, and conditional graph constructs.
The parameter passing interface is one of the strengths of HeNCE. HeNCE programmers need only specify which parameters are to be used to invoke each subroutine node. These parameters are specified when the programmer attaches a subroutine to a node in the graph. By automatically passing parameters, HeNCE programs are easier to build from pieces of code that have already been written. Thus, re-usability is enhanced. Based on the user input graph, HeNCE automatically distributes the parameters to the subroutines at runtime using PVM for data transmission and conversion.