Skip to content Skip to navigation
Pre-Defense
5/9/2019 01:00 pm
CoRE B 305

Performance and Correctness Debugging Techniques for Task Parallel Programs

Adarsh Yoga, Computer Science Department

Defense Committee: Prof. Santosh Nagarakatte (Chair), Prof. Ulrich Kremer, Prof. Sudarsun Kannan, and Dr. Madanlal Musuvathi (Microsoft Research)

Abstract

Debugging parallel programs for performance and correctness is notoriously challenging. First, performance and correctness issues can occur in any of the numerous interleavings for an input, making it necessary for every interleaving to be tested to confirm the absence of any issue. Second, issues may not manifest during small scale testing, but may occur when a program is executed at scale. Finally, secondary effects of parallel execution on hardware, can influence the performance of a program, and skew the execution to mask correctness issues. Hence, there is a need for tools that can expose issues that may occur in any execution of a program, not just in the observed execution.

In this dissertation, we propose techniques to identify performance and correctness issues independent of an execution for a class of parallel programs, called task parallel programs. We present TaskProf, a profiler that can highlight scalability bottlenecks, runtime overheads and secondary effects in task parallel programs. TaskProf identifies performance issues by constructing a performance model of the program and computing the logical parallelism expressed in the program for a given input. Using the performance model and parallelism, TaskProf automatically identifies code regions that must be optimized to improve the parallelism of the program. The key insight is a novel what-if analysis technique, that can check if hypothetically optimizing a region of code will improve the parallelism of the program. Further, we propose a differential analysis technique that compares the performance models from two executions - a parallel execution, and an oracle execution and pinpoints code regions with work inflation as regions experiencing secondary effects. Finally, this dissertation proposes PTRacer, a tool to detect concurrency correctness issues like races, and atomicity violations in task parallel programs. For a class of task parallel programs, PTRacer can detect correctness issues that can occur in any interleaving of the program for a given input.