Classification-Based Optimization of Dynamic Dataflow Programs

Classification-Based Optimization of Dynamic Dataflow Programs

Hervé Yviquel (IRISA, France), Emmanuel Casseau (IRISA, France), Matthieu Wipliez (Synflow SAS, France), Jérôme Gorin (Telecom ParisTech, France) and Mickaël Raulet (IETR/INSA, France)
DOI: 10.4018/978-1-4666-6034-2.ch012


This chapter reviews dataflow programming as a whole and presents a classification-based methodology to bridge the gap between predictable and dynamic dataflow modeling in order to achieve expressiveness of the programming language as well as efficiency of the implementation. The authors conduct experiments across three MPEG video decoders including one based on the new High Efficiency Video Coding standard. Those dataflow-based video decoders are executed onto two different platforms: a desktop processor and an embedded platform composed of interconnected and tiny Very Long Instruction Word-style processors. The authors show that the fully automated transformations presented can result in a 80% gain in speed compared to runtime scheduling in the more favorable case.
Chapter Preview

Dataflow Programming

The concept of dataflow representation was introduced by Sutherland in 1966 as a visual way to describe a sequence of arithmetic statements (Sutherland, W. R. (1966)). Then, the first dataflow programming language was presented by Dennis in 1974 (Dennis, J. B. (1974)). In this language, a program is modeled as a directed graph where the edges represent the flow of data and the nodes describes control and computation.

Thus, a dataflow program is defined as a graph composed of a set of computational units interconnected by communication channels. The one presented in Figure 1 contains a network of five components interconnected using communication channels. In the dataflow approach, the communication corresponds to a stream of data composed of a list of tokens.

Figure 1.

A dataflow graph

Complete Chapter List

Search this Book: