Orchestrating systems of recurrent equations/dependences on SIMD cores within heterogeneous systems

Programmability of (potentially heterogeneous) multicore architectures is a grand challenge problem. While the goal may be unattainable for arbitrary programs, some constructs such as streaming and MapReduce have shown enormous promise. Both streaming and MapReduce have been demonstrated on homogeneous multicores, accelerators (e.g., Cell, GPGPU), and heterogeneous multicores. However, the two programming models are both limited to expressing embarrassing forms of parallelism. My thesis adopts systems of recurrent equations/dependences (SRE/SRDs) as a programming abstraction that facilitates expression of coarse-grain data-parallelism with rich dependences. Like MapReduce and streaming, SRE/SRDs capture an easy-to-describe form of parallelism wherein the dependences are regular and repetitive. Because SRE/SRDs specify dependences without imposing orchestration details like tiling and synchronization granularity that affect architectural cost, SRE/SRDs may be compiled to various backends including multicores, heterogeneous multicores and accelerator-based systems. The main contribution of my thesis is the design and development of a source-to-source translator to compile SRE/SRD-based code to a GPGPU streaming language (nVidia\u27s CUDA). The generated code achieves significant parallel speedups for a variety of dynamic programming, linear algebra and partial differential equation solver kernels. Beyond the performance benefits, the SRE/SRD abstraction/implementation also captures the two key programmability benefits of raising the level of abstraction: (a) reduced programmer burden and (b) iterative performance optimization of the SRE/SRD orchestration transparent to the application programmer