[Colloq] Thesis Proposal: Aaron Turon on Friday 2/17 at 2:00pm

[Nicole Bekerian]

The College of Computer and Information Science presents a PhD proposal presentation:

Speaker: Aaron Turon

Date: Friday February 17, 2012
Time: 2:00pm
Location: 366 West Village H

Title: Abstraction and composition for fine-grained concurrency

Abstract:

Parallel speedup is bounded by communication costs.  Adding parallel processors creates communication at a finer grain, which in turn increases communication costs (more cache misses, and more memory traffic).  Effective parallel programming must therefore, at some level, be supported by *fine-grained* concurrent algorithms.  The past two decades have produced a sizable collection of algorithms that use clever techniques to minimize the use of memory bandwidth and avoid unnecessary waiting.  They lie at the heart of industrial-strength libraries like java.util.concurrent and Intel's Threading Building Blocks.

In practice, such libraries are an enormous undertaking--and one that must be repeated for new platforms. They tend to be conservative, implementing only those data structures and primitives that are well understood and likely to fulfill common needs. It is not generally not possible to safely combine the facilities of the library to provide more complex primitives, nor to tailor the existing primitives to serve specific needs. Finally, while some simpler algorithms have been formally verified, it remains difficult to verify the more sophisticated algorithms used in real libraries.

In short, concurrency libraries are indispensable, but currently hard to design, verify, extend, or tailor.  My dissertation will show that scalable concurrency libraries can instead be built and verified using abstraction and composition.

With this approach, algorithms and their implementations no longer need to be constructed from "whole cloth," e.g. by using system-level primitives directly. Instead, they can be built incrementally, by composing abstract primitives. Common patterns can be baked into the primitives or captured in new abstractions built from them.  Library writers benefit, because they can express algorithms at a higher level, with more reuse, *without* sacrificing scalability. Library users benefit, because composition empowers them to extend and tailor the library without knowing the details of its underlying algorithms.

Just as composition provides an incremental way of developing algorithms, it should yield an incremental method of verification. And just as abstraction allows a library user to extend the library without knowledge of its internals, it should also allow library users to verify their code while treating the library abstractly. Data abstraction--hiding internal representation details from external clients--enables such abstract, compositional reasoning in the sequential world. As I will show, it can serve an even greater role in the concurrent world: concurrent data abstraction localizes reasoning about concurrent interference and allows the library and its clients to have differing views about the grain of atomicity.

Committee:

Mitchell Wand (advisor)
Amal Ahmed
Olin Shivers
Claudio Russo (external)
Doug Lea (external)


-- 




Best, 
Nicole 

______________________________________________________________ 

Nicole Bekerian 
Administrative Assistant 

Northeastern University 
College of Computer and Information Science 
360 Huntington Ave. 
202 West Village H 
Boston, MA 02115 

Phone: 617.373.2462 
Fax: 617.373.5121