Washington University in St. Louis

December 11, 2017
11:00am - 12:00pm
Donald Bren Hall 6011

A program is said to have a determinacy race if logically parallel parts of a program access the same memory location and one of the accesses is a write. These races are generally bugs in the program since they lead to non-deterministic program behavior --- different schedules of the program can lead to different results. Most prior work on detecting these races focuses on a subclass of programs with fork-join parallelism.

In this talk, I will present a race-detection algorithm, 2D-Order, for detecting races in a more general class of programs, namely programs whose dependence structure can be represented as planar dags embedded in 2-dimensional grids. Such dependence structures arise from programs that use pipelined parallelism or dynamic programming recurrences. Given a computation with work W and span S, 2D-Order executes the computation while also detecting races in O(W/P + S) time on P processors, which is asymptotically optimal.

We also implemented P-Racer, a race-detection tool based on 2D-Order for Cilk-P, which is a language for expressing pipeline parallelism. Empirical results demonstrate that P-Racer incurs reasonable overhead and exhibits scalability similar to the baseline (executions without race detection) when running on multiple cores.

I-Ting Angelina Lee is an assistant professor in the Computer Science and Engineering department in Washington University in St. Louis. Prior to that, she worked with the Supertech research group in Massachusetts Institute of Technology lead by Professor Charles Leiserson for her graduate study and subsequently as a postdoctoral associate.

Dr. Lee's research focuses on advancing software technologies for parallel computing. She is interested in many aspects of parallel computing, including designing programming models and linguistic constructs to simplify parallel programming, developing runtime and operating system support to execute multithreaded programs efficiently, and building software tools to aid debugging and performance engineering of multithreaded code.