ITR: A Language, Compilers and Tools for the Streaming Application Domain

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Applications centered around streams of data are becoming increasingly important and widespread. In the distributed realm, there are sensor networks, location-aware devices, and intelligent appliances, which require decentralized processing and robust communication via streams. In the embedded domain, there are handheld computers and cell phones which process data streams under tight resource con-straints. There are also high-performance applications such as software routers, cell phone base stations, and radar image processing, in which the stream abstraction must be mapped efficiently to the latest supercomputers. In all, we believe that streams will be the cornerstone of next-generation software. The goal of the StreamIt project is to establish a high-level programming paradigm for the streaming domain. In all of the applications listed above, there are intense demands on the programmer. StreamIt provides a high-level stream language in which the inherent complexities of the domain are handled by a stream-aware compiler. A program is written as a set of autonomous filters, each of which contains its own memory and communicates with its neighbors through data channels. This exposes the parallelism and communication patterns, giving more power to the compiler. We believe that this will lead to a dramatic improvement in programmer productivity, program robustness, and portability in three distinct communities. The first target is heterogeneous distributed computing, in which unreliable devices are communicating in ad-hoc networks with applications spread across multiple nodes. To address the challenge of partitioning a program across multiple nodes, StreamIt provides a "single machine abstraction" to the programmer. Filters are specified at the granularity of the algorithm, and the compiler maps them to nodes according to run-time resource constraints. StreamIt will also provide high-level support for fault-tolerance. If an unreliable node fails, a lightweight runtime system can leverage static compiler analysis to recover crucial data from a backup node, automatically relocate the computation, and continue processing. The second focus area for StreamIt is domain-specific optimization for the embedded and DSP communities. To eradicate costly hand-written assembly code, StreamIt will include domain-specific code generation strategies such as cache-constrained scheduling, stream-aware storage management, and new calling conventions for stream programs. To lower the expertise needed for high-level algorithm design, StreamIt will also include novel algorithmic transformations such as detection of linear nodes and automated translation to the frequency domain. The third thrust of StreamIt is with regards to high-performance computer architecture. StreamIt aims to provide a common machine language (CML) for the emerging class of communication-exposed machines. Just as C was a CML for von-Neumann architectures, StreamIt will hide the variations from one machine from another while capturing the properties that are important for obtaining performance. This will provide the foundation for a portable programming model for communication-exposed machines. A final focus of StreamIt is one that interweaves through all of the preceding themes: a full characterization and understanding of the streaming application domain. The project will include the study and implementation of a wide range of state-of-the-art stream algorithms, thereby exposing their common properties and providing a framework for future research on stream languages and compilation. To show the feasibility of this project, we have created a prototype version of the StreamIt language, a large collection of streaming programs written in StreamIt, a compiler that maps StreamIt to uniprocessors, and an optimizing compiler that maps StreamIt onto the Raw communication-exposed architecture.