Provably Efficient Coscheduling of Computation and Memory through Disentanglement

Because of its many desirable properties, such as its ability to control effects and thus potentially disastrous race conditions, functional programming offers a viable approach to programming modern multicore computers. This has led to the development of several parallel functional languages, typically based on dialects of ML and Haskell. However, these languages have traditionally underperformed compared to procedural languages such as C and Java. The primary reason for this underperformance has been the lack of scalable memory management techniques that can match the increased demand of memory in parallel execution. Building on a long line of work on parallel memory management, this thesis proposes provably efficient techniques for managing memory in parallel functional programs. The key idea behind our techniques is to coschedule the parallel computation with its data, enabling the memory manager to exploit the disentanglement hypothesis—the idea that parallel tasks of a program largely execute independently and avoid side-effecting data that may be accessed by others–for efficiency. We implement these techniques in the MPL compiler for parallel ML, and our experimental results show that the techniques can marry the safety benefits of functional programming with performance.