Architectures, Languages, and
Compilers for the Streaming Domain
Saman P. Amarasinghe,
Bill Thies; MIT
The streaming application class is becoming increasinly important and
widespread. Encompassing programs for embedded signal processing, sensor
networks, intelligent software routers, high-performance graphics and image
processing, the streaming domain offers a fresh set of challenges for
architects, language designers, and compiler writers. Unlike the scientific
domain, stream programs are characterized by abundant parallelism, regular
communication patterns, and short data lifetimes, all of which can be exploited
to improve programmability and performance.
In this tutorial, we describe recent advances in programming
language and architectural support for stream programs. We focus on
lessons learned in the development of StreamIt, a language and
compiler for high-performance streaming applications. Topics include:
- Overview. What is stream
processing? Characteristics of stream programs; examples of
streaming applications.
- Stream
architectures. Recent trends in computer architecture; building
the case for streaming; overview of the Raw, Imagine, TRIPS, and
VIRAM stream processors; initial performance comparison.
- Stream languages and
programming models. History of streaming models of computation,
stream programming, and modeling environments; the Ptolemy system;
programming in object-oriented, procedural, and assembly style;
introduction to StreamIt, Brook, and Cg.
- Stream compilers. How to
execute a stream program; time multiplexing vs. space multiplexing;
focus on compiling StreamIt to Raw: partitioning, layout,
communication scheduling; initial results.
- Domain specific optimizations.
Leveraging properties of the streaming domain to perform aggressive
optimizations; focus on linear analysis and optimization in
StreamIt, where the compiler can collapse large-scale linear
operations and transform them into the frequency domain when
profitable.
- Stream scheduling
algorithms. First, an introduction to scheduling synchronous
dataflow graphs; finding a steady state; building steady state and
initialization schedules; optimization tradeoffs; single-appearance
scheduling. Then, an overview of our recent work on phased
scheduling, which incorporates multiplpe-appearance schedules;
minimal latency scheduling; deadlock avoidance for hierarchical
systems; initial results.
Acknowledgements
Many people contributed slides for the tutorial, largely from their
presentations at the 2003
Workshop on Streaming Systems:
- Mark Horowitz
- Bill Dally
- Christos Kozyrakis
- Steve Keckler
- Edward A. Lee
- Peter Mattson
- Bill Mark
- Robert Bond
- Vivek Sarkar
- Jinwoo Suh
Links
The following is an initial (and very incomplete!) set of links to
resources on stream processing. If you have a link you would like us
to add, we would love to hear from you -- please send mail to
streamit@cag.lcs.mit.edu.
- General Streaming Resources
- Stream Architectures
- Stream Languages and Development Environments
- Stream Tools and Systems
- Domain Specific Optimization