This research investigated the problem of generating high-efficiency cache-oblivious code for real-world stencil computations that make good use of the memory hierarchy and processor pipelines, starting with simple-to-write linguistic specifications. The goal was to make a wide variety of stencil-based applications --- ranging across physics, biology, chemistry, energy, climate, mechanical and electrical engineering, finance, and other areas --- easier to develop and maintain, benefiting these application areas, as well as society at large. The outcome was a robust stencil compiler that handles homogeneous stencil rules on rectangular shapes, simple boundary conditions, and simple dependency rules. Approaches to handle complex boundary conditions, inhomogeneities, irregular shapes, and complicated dependencies were also investigated. Results were also obtained on performing stencil computations on unstructured graphs, achieving pipeline parallelism on the fly, and delivering optimal cache performance without trading off parallelism.

The researchers developed PRISM, a chromatic-scheduling algorithm for executing dynamic data-graph computations. Data-graph computations are an extension of stencil computations from simple grids to general unstructured graphs. PRISM uses a vertex-coloring of the graph to coordinate updates performed in a round, precluding the need for mutual-exclusion locks or other nondeterministic data synchronization. PRISM has provably good bounds on work and span, and these theoretical guarantees are matched by good empirical performance. The researchers also developed PRISM-R, a variation of PRISM that executes dynamic data-graph computations deterministically even when updates modify global variables with associative operations. PRISM-R satisfies the same theoretical bounds as PRISM, but its implementation is more involved.

The researchers investigated how a concurrency platform for fork-join parallelism can be enhanced to support pipeline parallelism in a provably efficient manner. Indeed, one can imagine performing a stencil computation as a pipeline. The researchers proposed simple linguistics for specifying pipeline parallelism, designed a provably efficient scheduling algorithm that integrates pipeline parallelism into a work-stealing scheduler for fork-join parallelism, and analyzed the algorithm. The proposed linguistics allow the structure of the pipeline to be specified "on the fly," as opposed to the "build-and-run" approach taken by existing concurrency platforms, thereby allowing a more flexible structure of the pipeline. The proposed mechanism has been incorporated into Cilk-M, a Cilk-based work-stealing runtime system. Benchmark results indicate that the prototype implementation has low serial overhead and good scalability. 

The researchers invented parallel “Cache-Oblivious Wavefront” (COW) algorithms. Unlike most state-of-the-art cache-oblivious parallel algorithms for stencils and dynamic programming (DP) problems that trade off parallelism for better cache performance, COW algorithms aim to achieve the same without sacrificing parallelism. COW algorithms perform divide-and-conquer (DAC) of the stencil/DP grid in exactly the same way as standard cache-optimal recursive DAC-based algorithms, but consider a recursive subtask ready for execution as soon as all its real dependency constraints are satisfied. COW algorithms inherit the cache-obliviousness and (serial) cache-optimality properties of the standard recursive DAC-based algorithms. But by scheduling a recursive subtask ready for execution based only on its real dependency constraints, COW algorithms lead to potentially improved parallelism. Experimental results on stencil and DP computations support these claims.

Please report errors in award information by writing to: awardsearch@nsf.gov.