Software Behavior-oriented Parallelization
Chen Ding, Xipeng Shen, Kirk Kelsey, Chris Tice, Ruke Huang, Chengliang Zhang
ABSTRACT
Many sequential applications are difficult to parallelize because of
unpredictable control flow, indirect data access, and
input-dependent parallelism. These difficulties led us to build a
software system for behavior oriented parallelization (BOP), which
allows a program to be parallelized based on partial information
about program behavior, for example, a user reading just part of the
source code, or a profiling tool examining merely one or few
executions.
The basis of BOP is programmable software speculation, where a user
or an analysis tool marks possibly parallel regions in the code, and
the run-time system executes these regions speculatively. It is
imperative to protect the entire address space during speculation.
The main goal of the paper is to demonstrate that the general
protection can be made cost effective by three novel techniques:
programmable speculation, critical-path minimization, and
value-based correctness checking. On a recently acquired
multi-core, multi-processor PC, the BOP system reduced the
end-to-end execution time by integer factors for a Lisp interpreter,
a data compressor, a language parser, and a scientific library, with
no change to the underlying hardware or operating system.
Download the paper in
pdf format.
Copyright notice