Generating, Optimizing, and Scheduling a Compiler Level Representation of Stream Parallelism

Stream parallelism is often cited as a powerful programming model for expressing parallel computation for multi-core and heterogeneous computers. It allows programmers to concisely describe the concurrency and communication requirements found in a program and it allows compilers and runtime systems to easily generate efficient code targeting parallel hardware. This type of stream parallelism is often restricted to use the Synchronous Dataflow (SDF) model and implemented using static compilation and scheduling techniques. While powerful, SDF and the associated static methods have real limitations when applied to general purpose programing on general purpose hardware. To increase generality, we can define stream parallelism as a graph of processes communicating with one another over unidirectional data channels. Although dynamic scheduling techniques have been developed for this more general model, the powerful compiler transformations that are available under the SDF model no longer apply. This is made worse by the fact that general purpose models are typically implemented as software frameworks on top of high-level general purpose languages. The Stream and Kernel Intermediate Representation (SKIR) is a compiler level representation of stream parallelism for general purpose languages. A SKIR compiler is able to recognize and take advantage of SDF style parallelism while allowing more general programs. This thesis presents the SKIR program representation and describes how it can be used as compiler target for several different high level languages. We show a dynamic scheduling mechanism for SKIR programs based on the concepts of coroutines and task stealing. We also propose code optimizations to reduce runtime overhead associated with dynamic scheduling. Such techniques are not possible in a high-level software framework and provide performance that meets or exceeds the performance of existing systems while providing greater generality and portability than static methods