|
Abstract : |
Dataflow has different meanings depending on the context in which it is used. Perhaps the most popular usage of dataflow (or data flow) is in software engineering where it refers to the flow of information between data processing entities. The earliest use of the word "dataflow " in the context of parallel computing dates back to 1966 when Karp and Miller studied theoretical properties of a dataflow-like model of computation [21]. The earliest description of dataflow models of computation were by Adams in 1968 [1] and by Rodriguez in 1969 [24]. Dataflow got its theoretical underpinnings when Kahn [20] in 1974 conjectured correctly that a dataflow network can be given mathematical meaning by thinking of it as a set of recursion equations and deriving its least fix point. At the same time, Dennis proposed the first architecture to embody the dataflow computing model [12, 15]. It is this model, or more accurately, this family of computing models that is the principal focus of this chapter. (What we will not discuss in this chapter is the considerable theoretical work since Kahn's seminal paper on nondeterministic dataflow computing models.) A computing model is a method that describes how a program is to be evaluated. It is tied to a particular model of programming that has primacy. It is abstract in the sense that it assumes an idealized implementation. The most common computing model is the "von Neumann " control-flow computing model. This model assumes that a program is a series of addressable instructions, each of which either specifies an operation along with memory locations of the operands or specifies transfer of control to another instruction unconditionally or when some condition holds. The method for executing this program is to start at the first instruction of the program, execute it, and proceed to the next instruction unless the executed instruction requires transfer of control. In the latter case, instruction execution continues from the instruction to which control is transferred. For example, consider a program to evaluate the following expression. c = if n = = 0 then a+b else a-b fi, |
