Eduction

There are two basic methods of evaluating the dependency graph which describes a program: demand-driven (or call-by-need) and data-driven (call-by-value). A data-driven approach performs a computation as soon as the required input values are available. While this ensures that a computation is performed as soon as possible, it generally results in unneeded computations being performed. Visualize, for example, a program that only wants to output a small region of interest of a large input dataset.

The demand-driven evaluation, or eduction, of a dependency graph is described by two rules:

1. The need for a data value at the output of a process causes it to be demanded.
2. If a data object (or a particular sub-context of one) is demanded, then and only then are values demanded that are known directly to determine the data object.

Thus, eduction is simply tagged, demand-driven dataflow, where the ``tag'' includes the multidimensional context of the data being processed [3].

When particular contexts of a set of streams is demanded, the streams are partitioned across the nodes of the systems in a cost constrained manner. Even in a single processor system, streams may be partitioned in order to maximize the use of cache memory. This partitioning is done in a distributed manner. Once partitioned and assigned to a processing node, a task is held until all needed parameter and function data is available in storage local to the node. It is then moved into a ready queue, from which it is executed when the processor becomes available. In order to support real-time systems, tasks may be educed with a desired time of execution, which is used to prioritize the tasks in a processing element's ready queue.