A Stream Compiler for Communication-Exposed Architectures - Gordon, Michael I.; Thies, Bill; Karszmarek, Michal; Lin, Jasper; Meli, Ali S.; Lamb, Andrew A.; Leger, Chris; Wong, Jeremy; Hoffmann, Henry; Maze, David; Amarasinghe, Saman (International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2002). San Jose, CA, 2002)
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 ¯rst step towards a portable programming model for communication-exposed architectures.