research-article

Tÿcho: A Framework for Compiling Stream Programs

Authors:

Gustav Cedersjö,

Jörn W. JanneckAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 18, Issue 6

Article No.: 120, Pages 1 - 25

https://doi.org/10.1145/3362692

Published: 14 December 2019 Publication History

Get Access

Abstract

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.

References

[1]

Marianne Baudinet and David MacQueen. 1985. Tree pattern matching for ML. (1985). http://www.smlnj.org/compiler-notes/85-note-baudinet.ps.

Abstract

References

Cited By

Index Terms

Recommendations

McLab: an extensible compiler toolkit for MATLAB and related languages

Modeling with monads: extensible modeling semantics as syntactic sugar

Compiler algorithm language (CAL): an interpreter and compiler

Comments

Information

Published In

Publisher

Journal Family

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

HTML Format

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations