CAREER: Efficient Algorithms for Modern Computer Architecture

University Of California-Riverside, Riverside CA

Investigators

Abstract

Recent computer hardware advances have brought parallel processors to the mainstream and provided the potential for higher efficiency and productivity in computing. To enjoy the benefit of modern multicore machines, an algorithm must fit the data and auxiliary space in memory. On modern hardware, using too much space in an algorithm limits the solvable problem size on a multicore machine and may slow down the performance in practice. Consequently, designing efficient algorithms nowadays faces very different challenges from decades ago. This CAREER project focuses on two critical challenges in parallel algorithm design and analysis: space efficiency and communication efficiency. The project will provide efficient computational models to better meet multiobjective optimization formulations, new graph algorithms and data structures with improved theoretical guarantees, as well as open-source software for the new data structures and algorithms. This project aims to bridge the gap between theory and practice, which is crucial for promoting the accessibility of parallelism to a diverse set of problems. The educational plan comprises redesign of algorithm courses to include memory storage considerations as well as support for a coding club and coding competition designed to make computer science more attractive to students. This project has two major thrusts. The first thrust is to study space-efficient parallel algorithms. This project will first study a simple yet effective computational model for measuring space usage of a parallel algorithm with the objective of investigating space-efficient parallel graph algorithms and data structures using auxiliary space sublinear to the input size. The second thrust is to study algorithm design on the new processing-in-memory (PIM) system, which has recently been developed to reduce the need for expensive data transfers between CPU and memory. The algorithmic challenge here is that the PIM system is a combination of shared memory and distributed memory, so efficient algorithms on PIM must utilize advantages of each. This project will study algorithms and data structures that are efficient on the PIM architecture. The expected outcome of this project will be algorithms with strong theoretical guarantees and good practical performance, and general lessons in designing and performance engineering efficient algorithms on modern computer architectures. 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.