Recent trends in both applications and architectures point towards streaming computations as a cornerstone of next-generation systems. On the software side, applications centered around streams of data are becoming increasingly important and widespread; examples range from embedded applications for cell phones and sensor networks to high-performance applications such as cell phone base stations and radar image processing. Also, as wire delay becomes a significant factor in on-chip performace, the stream abstraction offers the task and data parallelism necessary to effectively harness the power of communication-exposed architectures.
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 will describe recent advances in programming language and architectural support for stream programs. We will focus on lessons learned in the development of StreamIt, a language and compiler for high-performance streaming applications. Topics will include:
Overview. What are the characteristics of stream programs? Examples of modern streaming applications.
Stream architectures. Historical trends in computer architecture; building the case for streaming; overview of the Raw, Imagine, TRIPS, and VIRAM stream processors; initial performance comparison.
Stream programming models. History of streaming models of computation, languages, and modeling environments; the Ptolemy project; programming in object-oriented, procedural, and assembly style; introduction to StreamIt, Brook, and Cg; the Stream Virtual Machine.
Compiling stream programs. How to schedule a stream program for execution; time multiplexing vs. space multiplexing; focus on compiling StreamIt to Raw: partitioning, layout, communication scheduling.
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.
Scheduling algorithms for streams. Introduction to scheduling synchronous dataflow graphs; finding a steady state; building steady state and initialization schedules; optimization tradeoffs; single-appearance scheduling. Overview of our recent work on phased scheduling, which incorporates multiple-appearance schedules; minimal latency scheduling; deadlock avoidance for hierarchical systems.
Saman P. Amarasinghe is an Associate Professor in the Department of Electrical Engineering and Computer Science at Massachusetts Institute of Technology and a member of the MIT Computer Science and Artificial Intelligence Laboratory. Currently he leads the Commit compiler group and is the co-leader of the Raw project. Saman's research interests are in discovering novel approaches to improve the performance of modern computer systems without unduly increasing the complexity faced by either application developers, compiler writers, or computer architects. He received his BS in Electrical Engineering and Computer Science from Cornell University in 1988, and his MSEE and Ph.D from Stanford University in 1990 and 1997, respectively.
Rodric M. Rabbah is a research scientist in the MIT Department of Engineering and Computer Science, and a member of the MIT Computer Science and Artificial Intelligence Laboratory. His current areas of research include novel program characterizations methodologies, compiler optimizations, and architecture design. For the last several years, Rabbah has maintained the Trimaran compilation and simulation infrastructure for research in instruction level parallelism, and continues to provide support for the Trimaran user-community world wide.
Bill Thies is a graduate student at the MIT Computer Science and Artificial Intelligence Laboratory. Along with other members of Saman's group, he is working on the design and implementation of StreamIt.