A practical oracle for sequential code parallelization

With the relatively recent switch from single- to multi- core processors, parallelism now plays a much larger role in maximizing program performance. This switch calls for converting the existing serial implementations of programs into parallel implementations in order to ensure scalable performance on future generations of processors. While automated tools to perform this conversion have been developed, the resulting performance often significantly lags behind that of manually parallelized code. This gap in performance has led researchers to develop tools that ease the manual parallelization process. These tools have greatly simplified the later stages of parallelization, but they provide no assistance with one of the primary questions faced by programmers: "Which parts of this program should I spend time parallelizing?". In this dissertation we examine the design and implementation of Kremlin, a practical oracle for the parallelization of sequential programs. Kremlin predicts the outcomes of parallelization in order to guide the programmer towards regions of the program that will be most fruitful for parallelization. Kremlin accomplishes this task by extending a classic technique, critical path analysis, to make it practical for two often-overlooked phases of parallelization : parallelism discovery and planning. This oracle requires only unmodified serial source code, a representative set of inputs, and simple system parameters such as the number of cores to produce a parallelization plan that prioritizes regions by their potential parallel speedup. Our results highlight Kremlin's utility as a practical oracle : parallelization guided by Kremlin results in fewer program regions being parallelized (1.57x, on average) in order to achieve peak parallel performanc