Stream processing applications are naturally described as dataflow programs. Dataflow programs modelled as actor networks are well suited to describe concurrent and computationally intensive problems. Realistic dataflow programs are typically characterized by highly dynamic behaviour, limiting the applicability of static analysis techniques. In this work we explore using dynamic analyses of dataflow programs by making use of causation traces; graphs which capture instances of the program's execution. We outline how they can be used to inform pipelining and architectural decisions and conclude by delineating how this research can be expanded upon using multiple traces and doing more types of analyses.

FPGAs play an increasing role in the reconfigurable accelerator landscape. A key challenge in designing FPGA-based systems is partitioning computation between processor cores and FPGAs. An appropriate division of labor is difficult to predict in advance and requires experiments and measurements. When an investigation requires rewriting part of the system in a new language or with a new programming model, its high cost can delay design-space exploration. A single-language system with an appropriate programming model and compiler that targets both platforms transforms this tedious exploration to a simple recompile with new compiler directives.

Hardware-software codesign for FPGAs requires flexible and changeable boundaries between hardware and software. Design space exploration is facilitated by expressing programs in a language that can be compiled for both CPU and FPGA execution. Such an approach requires efficient and general communication mechanisms between hardware and software. We present a practical solution to this problem for heterogeneous programs expressed in CAL, an actor based language running on a PCIe-based FPGA system where communication between a processor and FPGA is relatively expensive. We show how a network of continuously executing software and hardware actors with fine-grained communication can be expressed as a coprocessor model that executes the network in discrete steps with efficient coarse-grained transfers across the PCIe bus.

Many application areas for embedded systems, such as DSP, media coding, and image processing, are based on stream processing. Stream programs in these areas are often naturally described as graphs, where nodes are computational kernels that send data over the edges. This structure also exhibits large amounts of concurrency, because the kernels can execute independently as long as there are data to process on the edges. The explicit data dependencies also help making efficient sequential implementations of such programs, allowing programs to be more portable between platforms with various degrees of parallelism. The kernels can be expressed in many different ways; for example, as imperative programs with read and write statements for the communication or as a set of actions that can be performed and conditions for when these actions can be executed. Traditionally, there has been a tension between how the kernels are expressed and how efficiently they can be implemented. There are very efficient implementation techniques for stream programs with restricted expressiveness, such as synchronous dataflow. In this article, we present a framework for building stream program compilers that we call Tÿcho. At the core of this framework is a common kernel representation, based on a machine model for stream program kernels called actor machine , on which transformations and optimizations are performed. Both imperative and action-based kernels are translated to this common representation, making the same optimizations applicable to different kinds of kernels, and even across source language boundaries. An actor machine is described by the steps of execution that a kernel can take, and the conditions for taking them, together with a controller that decides how the conditions are tested and the steps are taken. We outline how kernels of an imperative process language and an action-based language are decomposed and translated to the common kernel representation, and we describe a simple backend that generates sequential C code from this representation. We present optimization heuristics of the decision process in the controller that we evaluate using a few dozen kernels from a video decoder with various degrees of complexity. We also present kernel fusion, by merging the controllers of actor machines, as a way of scheduling kernels on the same processor, which we compare to prior art.

This paper investigates the reduction of dynamic power for streaming applications yielded by asynchronous dataflow designs by using clock gating techniques. Streaming applications constitute a very broad class of computing algorithms in areas such as signal processing, digital media coding, cryptography, video analytics, network routing, packet processing, etc. This paper introduces a set of techniques that, considering the dynamic streaming behavior of algorithms, can achieve power savings by selectively switching off parts of the circuits when they are temporarily inactive. The techniques being independent from the semantic of the application can be applied to any application and can be integrated into the synthesis stage of a high-level dataflow design flow. Experimental results of at-size applications synthesized on field-programmable gate arrays platforms demonstrate power reductions achievable with no loss in data throughput.

Embedded DSP computing is currently shifting towards manycore architectures in order to cope with the ever growing computational demands. Actor based dataflow languages are being considered as a programming model. In this paper we present a code generator for CAL, one such dataflow language. We propose to use a compilation tool with two intermediate representations. We start from a machine model of the actors that provides an ordering for testing of conditions and firing of actions. We then generate an Action Execution Intermediate Representation that is closer to a sequential imperative language like C and Java. We describe our two intermediate representations and show the feasibility and portability of our approach by compiling a CAL implementation of the Two-Dimensional Inverse Discrete Cosine Transform on a general purpose processor, on the Epiphany manycore architecture and on the Ambric massively parallel processor array.

In this paper we address the problem of generating efficient software implementations for a large class of dataflow programs that is characterized by highly data-dependent behavior and which is therefore in general not amenable to compile-time scheduling. Previous work on implementing dataflow programs has emphasized classes of stream processing algorithms that exhibit sufficiently regular behavior to permit extensive compile-time analysis and scheduling, however many real-world stream programs, do not fall into these classes and exhibit behavior that can, for example, depend on the values and even the timing of their input data. Based on an abstract machine model, we partition the problem of implementing such programs in software into three parts, viz. reduction, composition, and code emission, and present solutions for each of them. Using the reference code of an MPEG decoder, we evaluate the resulting code quality and compare it to the state of the art compilers for the same class of stream programs, with favorable results.

While research on the design of heterogeneous concurrent systems has a long and rich history, a unified design methodology and tool support has not emerged so far, and thus the creation of such systems remains a difficult, time-consuming and error-prone process. The absence of principled support for system evaluation and optimization at high abstraction levels makes the quality of the resulting implementation highly dependent on the experience or prejudices of the designer. This is particularly critical when the combinatorial explosion of design parameters overwhelms available optimization tools. In this work we address these matters by presenting a unified design exploration framework suitable for a wide range of different target platforms. The design is unified and implemented at high level by using a standard dataflow language, while the target platform is described using the IP-XACT standard. This facilitates different design space heuristics that guide the designer during validation and optimization stages without requiring low-level implementations of parts of the application. Our framework currently yields exploration and optimization results in terms of application throughput and buffer size dimensioning, although other co-exploration and optimization heuristics are available.

The trade-off between throughput and memory constraints is a common design problem in embedded systems, and especially for streaming applications, where the memory in question usually occurs in the form of buffers for streams of data. This paper presents a methodology, based on the post-processing of dataflow execution traces, that enables designers to make principled choices in the design space for arbitrary streaming applications in a scalable manner. It significantly extends the class of applications over traditional compile-time-only techniques, and effectively enables designers to find a close-to-minimum solution for this NP-complete problem. A heuristic algorithm exploring different buffer size configurations lets designers choose appropriate alternatives and enables them to rapidly navigate the design space. Methodology and experimental results are demonstrated in an at-size scenario using a real-world MPEG-4 SP decoder.

Current video coding standards, and their reference implementations, are architected as large monolithic and sequential algorithms, in spite of the considerable overlap of functionality between standards, and the fact that they are frequently implemented on highly parallel computing platforms. The former leads to unnecessary complexity in the standardization process, while the latter implies that implementations have to be rebuilt from the ground up to reflect the parallel nature of the target.

Dataflow descriptions have been used in a wide range of Digital Signal Processing (DSP) applications, such as multi-media processing, and wireless communications. Among various forms of dataflow modeling, Synchronous Dataflow (SDF) is geared towards static scheduling of computational modules, which improves system performance and predictability. However, many DSP applications do not fully conform to the restrictions of SDF modeling. More general dataflow models, such as CAL, have been developed to describe dynamically-structured DSP applications. Such generalized models can express dynamically changing functionality, but lose the powerful static scheduling capabilities provided by SDF. This paper focuses on detection of SDF-like regions in dynamic dataflow descriptions - in particular, in the generalized specification framework of CAL. This is an important step for applying static scheduling techniques within a dynamic dataflow framework. Our techniques combine the advantages of different dataflow languages and tools, including CAL, DIF and CAL2C. The techniques are demonstrated on the IDCT module of MPEG Reconfigurable Video Coding (RVC).

This demonstration presents an integrated environment that translates a CAL-based dataflow specification [1] into a heterogeneous implementation, composed by HDL and C codes. The demonstration focuses on the capability of the co-design environment to automatically build an executable heterogeneous system implementation running on a platform composed of a processor and a FPGA from the annotation of the CAL specification. The possibility of direct synthesis from a high level specification is a crucial issue for enabling efficient re-design cycles that include rapid prototyping and validation of performances of the final implementation. The design approach enabled by such integrated environment is particularly suited for development of complex processing systems such as video codecs. As a case study, the demonstration provides the analysis and validation of different software and hardware partitioning of a MPEG-4 simple profile decoder.

This paper presents an in-depth case study on dataflow-based analysis and exploitation of parallelism in the design and implementation of a MPEG reconfigurable video coding decoder. Dataflow descriptions have been used in a wide range of digital signal processing (DSP) applications, such as applications for multimedia processing and wireless communications. Because dataflow models are effective in exposing concurrency and other important forms of high level application structure, dataflow techniques are promising for implementing complex DSP applications on multicore systems, and other kinds of parallel processing platforms. In this paper, we use the client access license (CAL) language as a concrete framework for representing and demonstrating dataflow design techniques. Furthermore, we also describe our application of the differential item functioning dataflow interchange format package (TDP), a software tool for analyzing dataflow networks, to the systematic exploitation of concurrency in CAL networks that are targeted to multicore platforms. Using TDP, one is able to automatically process regions that are extracted from the original network, and exhibit properties similar to synchronous dataflow (SDF) models. This is important in our context because powerful techniques, based on static scheduling, are available for exploiting concurrency in SDF descriptions. Detection of SDF-like regions is an important step for applying static scheduling techniques within a dynamic dataflow framework. Furthermore, segmenting a system into SDF-like regions also allows us to explore cross-actor concurrency that results from dynamic dependences among different regions. Using SDF-like region detection as a preprocessing step to software synthesis generally provides an efficient way for mapping tasks to multicore systems, and improves the system performance of video processing applications on multicore platforms.

As dataflow descriptions of media processing become popular, the techniques for analyzing and profiling the performance of sequential algorithms are no longer applicable. This paper describes some of the basic concepts and techniques for analyzing the computations described by dataflow programs, and illustrates them on an MPEG-4 decoder.

We present an interface theory based approach to static analysis of actor models. We first introduce a new interface theory, which is based on interface automata, and which is capable of counting with numbers. Using this new interface theory, we can capture temporal and quantitative aspects of an actor interface as well as an actor's token exchange rate. We will show, how to extract this information from actors written in the cal actor language (CAL), and we also present a method to capture the interface information as well as the structure of dataflow models into an interface automaton. This automaton acts as glue between the automata of all actors in the model, and by successfully composing all actor automata with it, we can prove interface compatibility of all actors with the composition framework. After successful composition, the resulting automaton will contain information that can be used for further static analysis of the composite actor model.

Abstract. Modern environments for modelling and designing concurrent computational systems increasingly supportheterogeneoussystem models, which are characterised by different coordination mechanisms governing the interaction between concurrent components in different parts or at different levels of the model. These interaction semantics, also calledmodels of computation, pose a major challenge to the definition of the meaning of heterogeneous models, especially if such a definition is to be independent of any specific set of models of computation, ways of describing actors, or notations for describing models. This paper makes three main contributions. (1) It presents a framework for describing the semantics of actors and models of computation. Its central notion is the concept of a model of computation as a program transformation that composes actor descriptions into a description of a composite actor. This framework is entirely independent of any specific syntax for describing actors, or any particular modelling language. (2) It uses this framework to describe properties of actor compositions and models of computation, and to classify and analyse them. (3) Finally, it discusses the implications of this theory for the design of languages for describing actors and models of computation.

Modern embedded computing systems tend to be heterogeneous in the sense of being composed of subsystems with very different characteristics, which communicate and interact in a variety of ways-synchronous or asynchronous, buffered or unbuffered, etc. Obviously, when designing such systems, a modeling language needs to reflect this heterogeneity. Today's modeling environments usually offer a variant of what we call amorphous heterogeneity to address this problem. This paper argues that modeling systems in this manner leads to unexpected and hard-to-analyze interactions between the communication mechanisms and proposes a more structured approach to heterogeneity, called hierarchical heterogeneity, to solve this problem. It proposes a model structure and semantic framework that support this form of heterogeneity, and discusses the issues arising from heterogeneous component interaction and the desire for component reuse. It introduces the notion of domain polymorphism as a way to address these issues.

Petri nets are an established and well researched means for systems modeling and simulation, but its use in the engineering community is not as widespread as the applicability of the formalism would suggest. A reason for this might lie in the fact that there is no established concept for the concise presentation of reusable Petri net design knowledge. This paper proposes Petri net design patterns as a style of presentation of such design knowledge ranging from building blocks to architectural considerations. The template for description is introduced using a number of examples taken from our design experience.