CAREER: Parallel Algorithms: Theory for Practice

University Of California-Riverside, Riverside CA

Investigators

Abstract

Recent hardware advances have brought multicore parallel machines to the mainstream. Parallelism offers the promise of high performance, and theoretical research is important in supporting high performance. However, there remains a significant gap between the theory and practice of multicore parallelism. First, many simple problems in the traditional (sequential) setting become more complicated in parallel and still remain open in theory. This creates difficulty in teaching and popularizing parallel algorithms to a broader audience. Second, some important practical ideas are not captured by existing theory, and researchers need to consider theory and practice separately. As a result, it is important to develop new theoretical results for parallel algorithms that are simple to understand and can better capture practice. The goal of this project is to study the theory of shared-memory parallelism, including designing new parallel algorithms with improved theoretical guarantees, studying new parallel models to better capture practice, as well as promoting accessibility (to a broad audience and in education) and practicality (with good performance) for parallel algorithms. This project focuses on two thrusts. The first thrust is to design simple and efficient parallel algorithms from sequential iterative algorithms by carefully analyzing the true dependencies between iterations. A broader goal is to find conditions that make a sequential algorithm highly parallelizable and methodologies for exploiting parallelism. The second thrust is to design new models and algorithms to reduce synchronization costs. Although viewed as a constant cost in most existing parallel models, synchronizing threads is expensive in practice, and more accurate modeling is needed. This project will study new models to systematically understand the synchronization costs in parallel algorithms. This project places a strong emphasis on combining theory and practice. In addition to new theoretical bounds, the research team will also evaluate the practicality of the results for simplicity (are they suitable in the classroom setting) and programmability/performance (can they be implemented to achieve high performance). 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.