Compiler and Runtime Techniques for Automatic Parallelization of Sequential Applications.

Abstract

Multicore designs have emerged as the mainstream design paradigm for the microprocessor industry. Unfortunately, providing multiple cores does not directly translate into performance for most applications. An attractive approach for exploiting multiple cores is to rely on tools, both compilers and runtime optimizers, to automatically extract threads from sequential applications. This dissertation tackles many challenges faced in automatic parallelization of sequential applications, including general-purpose applications written in C/C++ and client-side web applications written in JavaScript, with the goal of achieving speedup on commodity multicore systems. First, a complete parallelizing compiler system for C/C++ is introduced. This system successfully identifies parallelization opportunities in programs and transforms the code to a parallel version. A matching runtime system, STMlite, is proposed to monitor the parallelized program behavior and fix any misspeculations that might happen. We show that this system can generate and execute parallel programs that are upto 2.2x faster than their sequential counterparts, when executed on an 8-core commodity system.

The second piece of work focuses on a similar problem in a very different application domain, JavaScript programs running on the client’s web browser. This dissertation is the first research work that proposes dynamic and automatic parallelization of JavaScript applications. The nature of the JavaScript language and its target execution environments impose a completely different set of challenges that we intend to solve. We first propose the ParaScript parallelizing engine, which identifies and speculatively parallelizes potentially parallel code segments while the code is running in the browser. A low-cost and highly customized speculation approach verifies the execution of the parallelized client-side code and rolls back in case of any misspeculation. Dynamic parallelization using ParaScript yields an average of 2.18x speedup over sequential JavaScript code on an 8-core commodity system. In addition, we introduce ParaGuard, a technique which executes the runtime checks required by trace-based JavaScript compilers in parallel with the main execution. ParaGuard is able to improve performance by 15% by using an additional core in multi-core systems.