Advances in Dataflow Programming LanguagesWESLEY M. JOHNSTON, J. R. PAUL HANNA, AND RICHARD J. MILLARUniversity of UlsterAbstract. Many developments have taken place within dataflow programminglanguages in the past decade. In particular, there has been a great deal of activity andadvancement in the field of dataflow visual programming languages. The motivation forthis article is to review the content of these recent developments and how they cameabout. It is supported by an initial review of dataflow programming in the 1970s and1980s that led to current topics of research. It then discusses how dataflowprogramming evolved toward a hybrid von Neumann dataflow formulation, andadopted a more coarse-grained approach. Recent trends toward dataflow visualprogramming languages are then discussed with reference to key graphical dataflowlanguages and their development environments. Finally, the article details four keyopen topics in dataflow programming languages.Categories and Subject Descriptors: A.1 [Introductory and Survey]; C.1 [ProcessorArchitectures]; D.2 [Software Engineering]; D.3 [Programming Languages]General Terms: Languages, TheoryAdditional Key Words and Phrases: Dataflow, software engineering, graphicalprogramming, component software, multithreading, co-ordination languages, data flowvisual programming1. INTRODUCTIONThe original motivation for research intodataflow was the exploitation of mas-sive parallelism. Therefore, much workwas done to develop ways to programparallel processors. However, one schoolof thought held that conventional “vonNeumann” processors were inherently un-suitable for the exploitation of parallelism[Dennis and Misunas 1975; Weng 1975].The two major criticisms that were lev-eled at von Neumann hardware were di-rected at its global program counter andglobal updatable memory [Silc et al. 1998],Authors’ addresses: Faculty of Engineering, University of Ulster, Newtownabbey, Northern Ireland, BT370QB; email: W. M. Johnston, [email protected]; J. R. P. Hanna and R. J. Millar, {p.hanna,rj.millar}@ulster.ac.uk.Permission to make digital/hard copy of part or all of this work for personal or classroom use is grantedwithout fee provided that the copies are not made or distributed for profit or commercial advantage, thecopyright notice, the title of the publication, and its date appear, and notice is given that copying is bypermission of ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requiresprior specific permission and/or a fee.c2004 ACM 0360-0300/04/0300-0001 $5.00both of which had become bottlenecks[Ackerman 1982; Backus 1978]. The al-ternative proposal was the dataflow archi-tecture [Davis 1978; Dennis and Misunas1975; Weng 1975], which avoids both ofthese bottlenecks by using only local mem-ory and by executing instructions as soonas their operands become available. Thename dataflow comes from the conceptualnotion that a program in a dataflow com-puter is a directed graph and that dataflows between instructions, along its arcs[Arvind and Culler 1986; Davis and Keller1982; Dennis 1974; Dennis and Misunas1975]. Dataflow hardware architecturesACM Computing Surveys, Vol. 36, No. 1, March 2004, pp. 1–34.2 Johnston et al.looked promising [Arvind and Culler 1986;Dennis 1980; Treleaven and Lima 1984;Veen 1986], and a number of physical im-plementations were constructed and stud-ied (for examples, see Davis [1978], Keller[1985], Papadopoulos [1988], Sakai et al.[1989], and Treleaven et al. [1982]).Faced with hardware advances, re-searchers found problems in compil-ing conventional imperative programminglanguages to run on dataflow hardware,particularly those associated with side ef-fects and locality [Ackerman 1982; Arvindet al. 1977; Arvind and Culler 1986;Kosinski 1973; Wail and Abramson 1995;Weng 1975; Whiting and Pascoe 1994].They found that by restricting certainaspects of these languages, such as as-signments, they could create languages[Ackerman 1982; Ashcroft and Wadge1977; Dennis 1974; Hankin and Glaser1981; Kosinski 1978] that more naturallyfitted the dataflow architecture and couldthus run much more efficiently on it. Theseare the so-called dataflow programminglanguages [Ackerman 1982; Whiting andPascoe 1994] that developed distinct prop-erties and programming styles as a conse-quence of the fact that they were compiledinto dataflow graphs—the “machine lan-guage” of dataflow computers.The often-expressed view in the 1970sand early 1980s that this form of dataflowarchitecture would take over from vonNeumann concepts [Arvind et al. 1977;Treleaven et al. 1982; Treleaven and Lima1984] never materialized [Veen 1986]. Itwas realized that the parallelism usedin dataflow architectures operated at toofine a grain and that better performancecould be obtained through hybrid vonNeumann dataflow architectures. Manyof these architectures [Bic 1990] tookadvantage of more coarse-grained paral-lelism where a number of dataflow in-structions were grouped and executed insequence. These sets of instructions are,nevertheless, executed under the rules ofthe dataflow execution model and thusretain all the benefits of that approach.Most dataflow architecture efforts beingpursued today are a form of hybrid[Iannucci 1988; Nikhil and Arvind 1989],although not all, for example, Verdosciaand Vaccaro [1998].The 1990s saw a growth in the field ofdataflow visual programming languages(DFVPLs) [Auguston and Delgado 1997;Baroth and Hartsough 1995; Bernini andMosconi 1994; Ghittori et al. 1998; Greenand Petre 1996; Harvey and Morris 1993,1996; Hils 1992; Iwata and Terada 1995;Morrison 1994; Mosconi and Porta 2000;Serot et al. 1995; Shizuki et al. 2000; Sh¨urr1997; Whiting and Pascoe 1994; Whitley1997]. Some of these, such as LabViewand Prograph were primarily driven byindustry, and the former has become asuccessful commercial product that is stillused today. Other languages, such as NL[Harvey and Morris 1996], were createdfor research. All have software engineer-ing as their primary motivation, whereasdataflow programming was traditionallyconcerned with the exploitation of paral-lelism. The latter remains an importantconsideration, but many DFVPLs are nolonger primarily concerned with it. Ex-perience has shown that many key ad-vantages of DFVPLs lie with the soft-ware development lifecycle [Baroth andHartsough 1995].This article traces the development ofdataflow programming through to thepresent. It begins with a
View Full Document
Unlocking...