Master/slave speculative parallelization and approximate code

This dissertation describes Master/Slave Speculative Parallelization (MSSP), a novel execution paradigm to improve the execution rate of sequential programs by parallelizing them speculatively for execution on a multiprocessor. In MSSP, one processor—the master—executes an approximate copy of the program to compute values the program's execution is expected to compute. The master's results are then checked by the slave processors by comparing them to the results computed by the original program. This validation is parallelized by cutting the program's execution into tasks. Each slave uses its predicted inputs (as computed by the master) to validate the input predictions of the next task, inductively validating the whole execution.; Approximate code, because it has no correctness requirements—in essence it is a software value predictor—can be optimized more effectively than traditionally generated code. It is free to sacrifice correctness in the uncommon case in order to maximize performance in the common case. In addition to introducing the notion of approximate code, this dissertation describes a prototype implementation of a program distiller that uses profile information to automatically generate approximate code. The distiller first applies unsafe transformations to remove uncommon case behaviors that are preventing optimization; second, it applies traditional safe optimizations to exploit the newly created opportunities.; The mechanisms necessary for a MSSP execution and an example implementation based on a chip multiprocessor are also described. These mechanisms buffer the master's predictions and make them available to the slaves, capture the input and output values for each slave task, and verify and commit the slave tasks to give the appearance of a sequential execution. A hardware implementation of these mechanisms require only a modest amount of resources (likely less than 5% area) beyond a next-generation chip multiprocessor.; This dissertation includes a simulation-based evaluation of the example MSSP implementation. Performance results show that MSSP achieves speedups up to 1.75 (harmonic mean 1.25) for the SPEC2000 integer benchmarks. Performance is currently limited by the effectiveness of code approximation, which can likely be significantly improved.