A stream compiler for communication-exposed architectures

By Michael I. Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali S. Meli, Andrew A. Lamb, Chris Leger, J.S.S.M. Wong, H. Hoffmann, David Maze and 1 more. ASPLOS X, 2002

386 citations recorded by the source corpus.

With the increasing miniaturization of transistors, wire delays are becoming a dominant factor in microprocessor performance. To address this issue, a number of emerging architectures contain replicated processing units with software-exposed communication between one unit and another (e.g., Raw, SmartMemories, TRIPS). However, for their use to be widespread, it will be necessary to develop compiler technology that enables a portable, high-level language to execute efficiently across a range of wire-exposed architectures.In this paper, we describe our compiler for StreamIt: a high-level, architecture-independent language for streaming applications. We focus on our backend for the Raw processor. Though StreamIt exposes the parallelism and communication patterns of stream programs, some analysis is needed to adapt a stream program to a software-exposed processor. We describe a partitioning algorithm that employs fission and fusion transformations to adjust the granularity of a stream graph, a layout algorithm that maps a stream graph to a given network topology, and a scheduling strategy that generates a fine-grained static communication pattern for each computational element.We have implemented a fully functional compiler that parallelizes StreamIt applications for Raw, including several load-balancing transformations. Using the cycle-accurate Raw simulator, we demonstrate that the StreamIt compiler can automatically map a high-level stream abstraction to Raw without losing performance. We consider this work to be a first step towards a portable programming model for communication-exposed architectures.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/4ce393506dc1e0ddbc65225d2dad24d31d430c90

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

The Landscape of Parallel Computing Research: A View from Berkeley (2006, background): “…et al 1998] HPC Explicit Explicit Explicit Implicit Implicit Pthreads [Pthreads 2004] General Explicit Explicit Implicit Implicit Explicit StreamIt [Gordon et al 2002] DSP Explicit Implicit Explicit Implicit Implicit MapReduce [Dean and Ghemawat 2004] Large Data sets Explicit Implicit Implicit…”
Evaluating MapReduce for Multi-core and Multiprocessor Systems (2007, methodology): “StreamIt uses a synchronous data-flow model that allows a compiler to automatically map a streaming program to a multi-core system [ 13 ].”
Exploiting coarse-grained task, data, and pipeline parallelism in stream programs (2006, background): “Previous data-parallel streaming architectures have focused on designing a special memory hierarchy to support this communication [18].”
Automatic thread extraction with decoupled software pipelining (2005, background): “Success has also been achieved for streaming applications, through the use of specialized programming languages [9], in effect requiring the programmer to rewrite the application to expose parallelism.”
Halide (2017, background): “12 Halide’s model of scheduling addresses the problem of multidimensional stencils with parallelism, where recomputation versus storage becomes a critical but complex choice.”
A catalog of stream processing optimizations (2014, methodology): “StreamIt uses fusion to coarsen the granularity of the graph to the target number of cores, based on static cost estimates [Gordon et al. 2002].”
Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines (2013, methodology): “Graph-structured programs have been studied in the context of streaming languages [4, 11, 29].”
Flask (2008, methodology): “Like Flask and unlike StreamIT (Gordon et al. 2002), WaveScript focuses on asynchronous data streams.”