SHF: Small: Provably Efficient Dynamic Analysis Tools for Task Parallel Computations

Washington University, Saint Louis MO

Investigators

Abstract

The widespread deployment of multicore platforms --- from personal computers to mobile devices to supercomputers --- has made it critical to develop support for writing correct and efficient parallel software that can efficiently utilize the multicore platforms. Parallel programming is no longer a trade performed by only experts, or a practice required by a specific domain such as scientific computing; it is now required for general-purpose computing. Yet, writing correct parallel code that utilizes multicore efficiently is still notoriously difficult. This project aims to develop a suite of software engineering tools to aid the task of writing efficient parallel code. The project's impacts include simplifying the task of writing correct and efficient parallel code and thereby improving both the programmer's productivity and efficient utilization of modern multicore hardware. The project focuses on developing tools for task parallelism, a programming model widely employed by modern parallel software platforms, such as OpenMP, Intel Threading Building Blocks, and various dialects of Cilk and Habanero. With task parallelism, the language constructs express the logical parallelism of the computation, and let an underlying runtime scheduler automate tasks such as load balancing and coordinations among subcomputations. The task parallel model provides many benefits: it allows the programmer to focus on implementing the functionality of the application without worrying about scheduling logics; the programming model is processor-oblivious and has a well-defined cost model; finally, the scheduler can provide provable guarantees on resource usage. In this project, the investigators study and develop both algorithms and software support for tools to debug unstructured and nondeterministic synchronization primitives, to analyze scalability of nondeterministic code, and to combat work inflation in task parallel computations. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.