The Taub Faculty of Computer Science Events and Talks

Advisor: Prof. Mooly Sagiv
Software applications are becoming increasingly harder to parallelize. Modern software systems written in imperative languages like Java and C# typically manipulate complex heap data structures, consist of multiple layers of abstraction, and have input- and deployment-specific behaviors that affect their available parallelism. This creates a significant challenge for parallelizing compilers, whose target transformations are normally conditioned on the assumption that the instructions designated for parallel execution access disjoint memory regions. Establishing this precondition over real-world applications is hard: Often there are dependencies between the candidate code blocks at the concrete level, at least over some of the inputs, and even if disjointness holds universally, it is hard for an automated verifier to formulate a proof to this effect. These limitations of static dependence analysis in dealing with the complexity of modern programs, as well as their dynamic behavior, have shifted attention to runtime optimistic parallelization techniques, and most notably, software transactional memory (STM). The challenge with this approach is that STM typically incurs high overhead -- due mainly to runtime tracking of memory accesses and conservative conflict detection -- which often obviates the performance gain from parallelization. In this thesis, we overcome the limitations of these general parallelization techniques by specializing the parallelization system per the specific application and workload at hand. Specialization addresses fluctuating parallelism, as evidenced in many applications, and enables optimizing the runtime system with respect to prevalent program behaviors and common input profiles. Specifically, we develop methods for specializing concurrency control by analyzing dynamic data dependencies, obtained during offline profiling over representative executions of the subject program. We demonstrate that our methods enable effective specialization over realistic programs and popular parallelization techniques, e.g. by dramatically reducing STM overhead thanks to specialized conflict detection.