Write a Blog >>
ICFP 2016
Sun 18 - Sat 24 September 2016 Nara, Japan
Wed 21 Sep 2016 13:30 - 13:55 at Noh Theater - Session 10 Chair(s): John Reppy

An important feature of functional programs is that they are parallel by default. Implementing an efficient parallel functional language, however, is a major challenge, in part because the high rate of allocation and freeing associated with functional programs requires an efficient and scalable memory manager.

In this paper, we present a technique for parallel memory management for strict functional languages with nested parallelism. At the highest level of abstraction, the approach consists of a technique to organize memory as a hierarchy of heaps, and an algorithm for performing automatic memory reclamation by taking advantage of a disentanglement property of parallel functional programs. More specifically, the idea is to assign to each parallel task its own heap in memory and organize the heaps in a hierarchy/tree that mirrors the hierarchy of tasks.

We present a nested-parallel calculus that specifies hierarchical heaps and prove in this calculus a disentanglement property, which prohibits a task from accessing objects allocated by another task that might execute in parallel. Leveraging the disentanglement property, we present a garbage collection technique that can operate on any subtree in the memory hierarchy concurrently as other tasks (and/or other collections) proceed in parallel. We prove the safety of this collector by formalizing it in the context of our parallel calculus. In addition, we describe how the proposed techniques can be implemented on modern shared-memory machines and present a prototype implementation as an extension to MLton, a high-performance compiler for the Standard ML language. Finally, we evaluate the performance of this implementation on a number of parallel benchmarks.

Wed 21 Sep

Displayed time zone: Osaka, Sapporo, Tokyo change

13:30 - 14:45
Session 10Research Papers at Noh Theater
Chair(s): John Reppy University of Chicago
13:30
25m
Talk
Hierarchical Memory Management for Parallel Programs
Research Papers
Ram Raghunathan Carnegie Mellon University, USA, Stefan K. Muller Carnegie Mellon University, USA, Umut A. Acar Carnegie Mellon University, Guy Blelloch Carnegie Mellon University, USA
DOI
13:55
25m
Talk
Allocation Characterizes Polyvariance: A Unified Methodology for Polyvariant Control-Flow Analysis
Research Papers
Thomas Gilray University of Utah, USA, Michael D. Adams University of Utah, USA, Matthew Might University of Utah, USA
DOI
14:20
25m
Talk
A Fully Concurrent Garbage Collector for Functional Programs on Multicore Processors
Research Papers
Katsuhiro Ueno Tohoku University, Japan, Atsushi Ohori Tohoku University, Japan
DOI