Disentanglement: Provably Efficient Parallel Functional Programming

Speaker: Sam Westrick , Carnegie Mellon University

Date: Wednesday, March 10, 2021

Time: 3:00 PM to 4:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required, if you haven't registered for this series before)

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, lindalynch@csail.mit.edu

Relevant URL:

Speaker URL: http://www.cs.cmu.edu/~swestric/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu

Reminder Subject: TALK: Disentanglement: Provably Efficient Parallel Functional Programming

Abstract:
Researchers have argued for decades that functional programming can greatly simplify writing parallel programs, for example by controlling side-effects and avoiding race-conditions. However, parallel functional programs have historically performed poorly in comparison to their imperative counterparts. The primary reason is that functional programs allocate memory at a high rate, which only grows with parallelism, causing traditional memory management techniques to buckle under the increased demand for memory.

In this talk, I identify a memory property called disentanglement and show that it emerges naturally in race-free parallel programs. To exploit disentanglement for improved efficiency, I describe how to integrate memory management with thread scheduling, ultimately enabling each processor to allocate memory and perform GC independently and in parallel. This approach yields a provably efficient GC policy: for any race-free program with R* sequential live memory, execution on P processors with GC requires O(P R*) memory in total, and only O(P R*) additional work. We implemented these techniques in the MPL compiler, and our experimental results show good performance and scalability. With respect to a sequential baseline, MPL uses only 1-5x additional memory while obtaining 12-51x speedup on 70 cores. In a small sorting competition, MPL is 50% faster than Go and nearly 2x faster than Java while using comparable space.

Bio:
Sam Westrick is a PhD student at Carnegie Mellon University, advised by Umut Acar. His research focuses on developing provably efficient and practical implementation techniques for parallel programming languages. He is the lead developer of the MPL compiler for Parallel ML, which is currently being used at CMU to help teach parallel programming to 500+ students every year.

IMPORTANT NOTE FOR ATTENDEES: If you have already registered for the Fast Code Seminars on Zoom since July 27, 2020, please use the Zoom link that you have received. This link will stay the same for subsequent Fast Code seminars this semester. Zoom does not recognize a second registration, and will not send out the link a second time. If you have any problems with registration, please contact lindalynch@csail.mit.edu by 1:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

See other events that are part of the Fast Code 2020 - 2021.

Created by Julian J. Shun at Wednesday, March 03, 2021 at 8:30 PM.