A descriptive and prescriptive model for dataflow semantics
Rangaswamy Jagannathan · 1988
Dataflow operational semantics have been described informally in terms of implementation notions such as data-driven execution and demand-driven execution. We claim that these mechanisms do not form the bases for dataflow semantics embodied by dataflow computers as has been previously thought. Instead, we present a general model that provides the necessary bases for dataflow semantics. The model allows various dataflow semantics to be described and prescribed in abstract terms without using implementation notions. It assumes that programs are expressed using a simple, graphical language called flat operator nets. In the model, a dataflow semantics is described using rules that assert which data items of a program instance are desired to be computed and when these data items are desired. Using the model, we describe four dataflow (operational) semantics which are embodied by various dataflow computing engines. We refer to these dataflow semantics as piped eager, tagged eager, piped lazy and tagged lazy. The model allows us to determine whether a dataflow semantics is correct; that is, for a given program instance, is the operationally-derived meaning identical to the mathematical meaning. We show that the tagged eager and tagged lazy dataflow semantics are correct for all program instances whereas the piped eager and the piped lazy dataflow semantics are correct only for certain program instances. The model allows us to compare efficiencies of the dataflow semantics. We define efficiency to be how fast a dataflow semantics evaluates needed results of a program instance without causing unbounded waste. We show that tagged lazy dataflow semantics is the only one of the four that we consider which does not cause unbounded waste. The model also allows us to prescribe new dataflow semantics. One such dataflow semantics that we develop is called easyflow. We show that the easyflow semantics is correct and that it is most efficient amongst the dataflow semantics we consider. Furthermore, we demonstrate that demand-driven and data-driven are implementation notions by showing how the easyflow semantics can be implemented in two different ways: using only demand-driven execution and using a hybrid of data-driven and demand-driven execution.