Provably Good Algorithms for Multicore Computing

by Jeremy Fineman

Massachusetts Institute of Technology

Date

Tuesday, March 10, 2009

Time

3:00 p.m. — 4:00 p.m.

Place

Persimmon Room, IMU (Note special day, place)

Abstract:  With most hardware manufacturers shifting to multicore computers, which have multiple independent cores (or processors) on a single integrated circuit, the need for efficient parallel programs becomes more apparent.  Developing efficient parallel programs involves overcoming difficulties in synchronization (such as locking), scheduling, and locality. This talk focuses on provably good algorithms in all three areas, including provably good algorithms for race detection, conflict-detection in transactional memory, and so- called "cache-oblivious B-trees."  A multithreaded parallel program that is intended to be deterministic may exhibit nondeterminism due to bugs called "races."  These bugs arise due to improper synchronization and are notoriously difficult to detect.  A race detector is a tool that helps locate these race bugs in the program.  A key component of some race detectors is an algorithm for "series-parallel maintenance." This talk describes a novel series-parallel (SP) maintenance algorithm that both has provably good performance and runs in parallel.  In general, it is not well understood how to analyze programs that use locks.  Interestingly, our SP-maintenance algorithm uses locks, yet it still attains provably good performance.  The analysis uses a new approach for amortizing the cost of locking accesses to a shared data structure against the critical path of the underlying program.  These same techniques are relevant to a novel conflict-detection algorithm for a transactional-memory system.  Finally, addressing locality, this talk discusses some results on "cache-oblivious B-trees," including adding concurrency to existing structures and enabling faster updates. A cache-oblivious B-tree supports the same operations as a B-tree, but it uses no system- specific parameters.  Cache-oblivious algorithms in general are desirable for several reasons.  First, the lack of tuning parameters makes the code more portable. Second, an algorithm that is provably optimal for a two-level memory hierarchy are also optimal for all levels of a multilevel hierarchy. Third, in a multiprogrammed multicore environment, the effective tuning parameters depend on the load on a system, and hence are not generally known.

Biography:  Jeremy T. Fineman is a Ph.D. candidate at MIT.  He works in the Supercomputing Technologies and Theory groups under Charles E. Leiserson.  He is also currently serving on the program committee for the Symposium on Parallelism in Algorithms and Architectures (SPAA).

Colloquium Provided By:

the School of Informatics