SHF: Small: Solving the Parallel Functional Programming Challenge

Nearly all computers today ranging from mobile devices to servers are multicore systems that contain as many as hundreds of cores. Many applications therefore demand parallel software, but parallel programming is understood and practiced by few expert programmers (it is simply too hard). Researchers have argued for decades that functional programming can be a game changer for parallel programming, because functional programs can be parallel by default, and in principle require no additional effort for parallelization.

However, functional languages have been unable to deliver the efficiency and performance expected of parallel programs. Prior research has identified memory management as the key performance bottleneck in functional programs. This project aims to solve this problem.

The projects novelties are 1) a theory of "disentanglement" that, based on the principles of parallel programming, unlocks efficient and scalable memory management 2) techniques for detecting and handling entanglement dynamically on the fly and 3) provably and practically efficient memory-management techniques. The projects impacts are 1) development of the foundations for parallel programming that could enable everyday programmers to write performant parallel programs and 2) development of educational materials for teaching undergraduate students about parallel algorithms and programming.

To achieve these goals, the project develops a technique for organizing the memory as a hierarchy of heaps, which may be managed independently and in parallel, except when entanglement arises due to non-deterministic accesses to mutable data. To handle entanglement, the project develops techniques for detecting it during run-time, and handling it so that parallel execution can continue unimpeded.

The project then presents space, work, and run-time bounds that take the cost of memory management into account. Even though such bounds are critical for all languages, including procedural ones, they are under-studied. The project assesses the practicality of the techniques by providing an implementation, evaluating it, and integrating it into education.

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.