[Colloquium] Auhagen/MS Presentation/Apr 13, 2012

[Margaret Jaffey]

This is an announcement of Sven Auhagen's MS Presentation.

------------------------------------------------------------------------------
Date:  Friday, April 13, 2012

Time:  11:30 AM

Place:  Ryerson 277

M.S. Candidate:  Sven Auhagen

M.S. Paper Title: Hybrid Chunking

Abstract:
Manticore is a compiler for the parallel programming language Parallel
ML (PML), which is based on Standard ML. PML supports parallelism
using an implicitly-threaded model where the programmer annotates
parts of the program that should be run in parallel. For example, in a
recursive divide-and-conquer algorithm, the programmer could use a
parallel tuple annotation to specify that recursive calls should be
done in parallel. The Manticore compiler replaces the parallel tuples
with futures that encapsulate the potential parallel work. At runtime,
work stealing is used to balance the parallel workload.

For many programs, this approach has the problem that it introduces
too much fine-grained parallelism, which means that the overhead of
managing the futures comes to dominate the execution time. The
solution to this problem is to increase the granularity of work, but
not so much that there is not sufficient parallelism to keep the
processors busy. In this paper, we introduce an automatic mechanism
for chunking together fine-grain parallel computations into their
sequential equivalents. Our approach, which is called hybrid chunking,
uses a combination of compile-time analysis and runtime
instrumentation and decision making to identify when a recursive
parallel computation should be run as a recursive sequential
computation.

We present a cost model that we use in the static analysis to obtain
cost of expressions and size information of data structures. We also
describe how this information is used at runtime to switch the
execution of a program from parallel to sequential when we determine
it will run faster sequentially. We show that we can obtain good
speedups on recursive divide-and-conquer programs, with our hybrid
chunking approach.

Sven's advisor is Prof. John Reppy

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#sauhagen

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=