Parallelizing sequential programs with statistical accuracy tests

We present QuickStep, a novel system for parallelizing sequential programs. QuickStep deploys a set of parallelization transforma-tions that together induce a search space of candidate parallel pro-grams. Given a sequential program, representative inputs, and an accuracy requirement, QuickStep uses performance measurements, profiling information, and statistical accuracy tests on the outputs of candidate parallel programs to guide its search for a parallelization that maximizes performance while preserving acceptable accuracy. When the search completes, QuickStep produces an interactive re-port that summarizes the applied parallelization transformations, performance, and accuracy results for the automatically generated candidate parallel programs. In our envisioned usage scenarios, the developer examines this report to evaluate the acceptability of the final parallelization and to obtain insight into how the original se