DATE: Monday, November 22, 2010
TIME: 10:30 am - 11:30 am
PLACE: Gates 9115
SPEAKER:
Junfeng Yang, Columbia University
TITLE: Making Threads Deterministic by Memoizing Schedules
ABSTRACT:
Nondeterminism complicates the understanding, testing, and debugging of multithreaded programs. A deterministic multithreading (DMT) system addresses this problem by forcing a multithreaded program to always use the same thread schedule for the same input. However, existing DMT systems are unstable: they may force a program to (ad)venture into vastly different schedules even for slightly different inputs, defeating many benefits of determinism. Moreover, few existing DMT systems work with server programs whose inputs arrive continuously and nondeterministically.
In this talk, I'll present TERN, the first (to the best of our knowledge) stable DMT system. The key novelty in TERN is the idea of schedule memoization that memoizes past working schedules and reuses them on future inputs, making program behaviors stable across different inputs. A second novelty in TERN is the idea of windowing that extends schedule memoization to server programs by splitting continuous request streams into windows of requests. Our TERN implementation runs on Linux. It operates as user-space schedulers, requiring no changes to the OS and only a few lines of changes to the application programs. We evaluated TERN on a diverse set of 14 programs (e.g., Apache and MySQL) with real and synthetic workloads. Our results show that TERN is easy to use, makes programs more deterministic and stable, and has reasonable overhead.
BIO:
Junfeng Yang is an assistant professor in Computer Science department at Columbia University. Before that, he was a Post-doc researcher at Microsoft Research Silicon Valley. Junfeng Yang received his Ph.D. in Computer Science from Stanford University in 2008, his MS in Computer Science from Stanford in 2002, and his BS in Computer Science from Tsinghua University, Beijing, China in 2000. He is a recipient of the Best Paper Award of OSDI 2004.
Visitor Host: Garth Gibson
Visitor Coordinator: Jiri Simsa (jsimsa@cs.cmu.edu)
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/