[Colloquium] TTI-C Talk: Daniel Spoonhower, CMU

[Julia MacGlashan]

REMINDER

When:             Wednesday, March 11th @ 11:00am (lunch will be provided
after talk)

Where:            6045 S Kenwood Ave, TTI-C Conference Room #526 (5th Floor)

Who:               Daniel Spoonhower (Carnegie Mellon University)

Title:                Scheduling Deterministic Parallel Programs


Deterministic parallelism enables programmers to write programs without
concern for how parallel tasks are interleaved.  While this simplifies
reasoning about the correctness of parallel programs, the performance of
these programs still depends on many aspects of the language implementation,
including the scheduling policy.  For example, the choice of scheduling
policy can asymptotically increase the amount of memory required to run an
application.

In this talk, I will give some background on scheduling and present a
methodology for understanding the performance of parallel programs.  At the
core of this work is a cost semantics that enables programmers to reason
formally about different scheduling policies and how they affect
performance.

This cost semantics is the basis for a suite of prototype profiling tools.
These tools enable programmers to simulate and visualize program execution
under different scheduling policies.  My cost semantics also provides a
specification for an implementation of the language.  I have extended MLton,
a compiler for Standard ML, with support for parallelism and implemented
several different scheduling policies.  Using my cost semantics and
profiler, I found a memory leak caused by a bug in one of the existing
optimizations in MLton.

I will also talk about how this implementation has inspired some theoretical
work on parallel scheduling.  Though work stealing has been successfully
applied to nested parallelism, I will present new bounds on the overhead of
work stealing implementations of parallel futures, a more expressive form of
parallelism.  These bounds apply to all prior work stealing schedulers but
suggest the possibility of more efficient alternatives.

Contact:          Umut Acar, TTI-C	umut at tti-c.org 		702-5072





-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090310/36257685/attachment.htm