| Research |
| [ CSI ] [ ETH ] |
[ Lab Manager ]
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |
|
Application-level Multi-variant Speculation with Competitive Parallel Execution |
| Oliver Trachsel, Application-level Multi-variant Speculation with Competitive Parallel Execution, ETH Zurich (Diss. ETH No. 19287), November 2010. [DISS-19287.pdf] |
| In the past few years, computer systems have rapidly shifted from single-core to multi-core architectures. Today, most computers sold in the server, desktop, and even notebook markets are equipped with multiple CPUs. This trend toward systems with an increasing core count is likely to continue---if not accelerate---in the future. In contrast to this increasing parallelism on the hardware side, many programs executed on these systems are still sequential in nature or have limited inherent parallelism. These programs can thus not directly exploit the parallel features of the hardware they are running on. This dissertation investigates multi-variant speculation, a technique that leverages the parallel processing power of modern systems to simultaneously explore different possible execution paths of a program. Different execution paths, or variants, can employ different algorithms, implementations, or other configuration parameters, and come with their respective properties in terms of performance or output characteristics. Multi-variant speculation is targeted at situations where the optimal execution path cannot be determined without actually trying out different possibilities. We present competitive parallel execution (CPE) as one approach to such multi-variant speculation. In the CPE model, multiple variants of specific parts of a program are executed in parallel. The variant that delivers the best performance or the best result according to an application-specific quality metric is then determined and selected online, i.e., upon the actual speculative execution of the variants. Using the CPE model, programs can improve their performance and the quality of computed results. The CPE model guarantees that variants execute in full isolation from each other. No side-effects are observed between variants, and no effects are made visible to the remaining system until a variant is selected. Conceptually, this model corresponds to a coarse grain transactional model with full isolation. These isolation guarantees make augmenting a program with multi-variant speculation particularly easy: Reasoning about a CPE-enabled program is in many cases no more complex than reasoning about a sequential program. The dissertation shows how the CPE model can be implemented as a pure software platform by leveraging features of modern architectures and operating systems. The evaluation demonstrates how CPE-based multi-variant speculation can be applied to existing real-world programs. We study a CPE-enabled version of an SAT solver that is created by modifying only a few lines of code in the original sequential implementation. The SAT solver is a representative example for the wider classes of heuristics-based and randomized algorithms. The resulting CPE-enabled version of the SAT solver provides speedups for many of the studied data input sets; in some cases the observed speedups are super-linear. A second application example shows how minor modifications to a modern video encoder lead to an implementation that performs multi-variant encoding of individual video frames to simultaneously explore different encoding configurations. The video encoding example is also used to study the scalability of the CPE software platform. Finally, the dissertation investigates an approach where a speculative multi-variant program is created at compile-time by applying different optimization strategies to different variants of frequently executed parts of a program. |
| [ Publications ] [ Research Opportunities ] [ Partners & Supporters ] [ Earlier Work ] |