[Colloquium] Bergstrom/Dissertation Defense/Apr 19, 2013

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Lars Bergstrom

Date:  Friday, April 19, 2013

Time:  10:00 AM

Place:  Ryerson 277

Title: Parallel Functional Programming with Mutable State

Abstract:
Immutability greatly simplifies the implementation of parallel
languages. In the absence of mutable state the language implementation
is free to perform parallel operations with fewer locks and fewer
restrictions on scheduling and data replication. In the Manticore
project, we have achieved nearly perfect speedups across both Intel
and AMD manycore machines on a variety of benchmarks using this
approach.

There are parallel stateful algorithms, however, that exhibit
significantly better performance than the corresponding parallel
algorithm without mutable state. For example, in many search problems,
the same problem configuration can be reached through multiple
execution paths. Parallel stateful algorithms share the results of
evaluating the same configuration across threads, but parallel
mutation-free algorithms are required to either duplicate work or
thread their state through a sequential store. Additionally, in
algorithms where each parallel task mutates an independent portion of
the data, non-conflicting mutations can be performed in parallel. The
parallel state-free algorithm will have to merge each of those changes
individually, which is a sequential operation at each step.

In this dissertation, we extend Manticore with two techniques that
address these problems while preserving its current scalability.
Memoization, also known as function caching, is a technique that
stores previously returned values from functions, making them
available to parallel threads of executions that call that same
function with those same values. We have taken this deterministic
technique and combined it with a high-performance implementation of a
dynamically sized, parallel hash table to provide scalable
performance. We have also added mutable state along with three
execution models - two of which are deterministic - that allow the
user to share arbitrary results across parallel threads under several
execution models, all of which preserve the ability to reason locally
about the behavior of code.

For both of these techniques, we present a detailed description of
their implementations, examine a set of relevant benchmarks, and
categorize the guarantees provided on their determinacy.

Lars's advisor is Prof. John Reppy

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#larsberg

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=