Open access
Date
2010Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
Competitive parallel execution (CPE) is a simple yet attractive technique to improve the performance of sequential programs on multi-core and multi-processor systems. A sequential program is transformed into a CPE-enabled program by introducing multiple variants for parts of the program. The performance of different variants depends on runtime conditions, such as program input or the execution platform, and the execution time of a CPE-enabled program is the sum of the shortest variants. Variants compete at run-time under the control of a CPE-aware run-time system. The runtime system ensures that the behavior and outcome of a CPE-enabled program is not distinguishable from the one of its original sequential counterpart. We present and evaluate a run-time system that is implemented as a user-space library and that closely interacts with the operating system. The report discusses two strategies for the generation of variants and investigates the applicability of CPE for two usage scenarios: i) computation-driven CPE: a simple and straightforward parallelization of heuristic algorithms, and ii) compiler-driven CPE: generation of CPE-enabled programs as part of the compilation process using different optimization strategies. Using a state-of-the-art SAT solver as an illustrative example, we report for compiler-based CPE speedups of 4–6% for many data sets, with a maximum slowdown of 2%. Computation-driven CPE provides super-linear speedups for 5 out of 31 data sets (with a maximum speedup of 7.4) and at most a slow-down of 1% for two data sets. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006851092Publication status
publishedJournal / series
Technical ReportVolume
Publisher
ETH Zurich, Department of Computer ScienceSubject
SEQUENTIAL PROGRAMMING (PROGRAMMING METHODS); DISTRIBUTED ALGORITHMS + PARALLEL ALGORITHMS (PROGRAMMING METHODS); PARALLELVERARBEITUNG + NEBENLÄUFIGKEIT (BETRIEBSSYSTEME); SEQUENTIELLE PROGRAMMIERUNG (PROGRAMMIERMETHODEN); VERTEILTE ALGORITHMEN + PARALLELE ALGORITHMEN (PROGRAMMIERMETHODEN); PARALLEL PROCESSING + CONCURRENCY (OPERATING SYSTEMS)Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics