|
| Research on Master/Slave Speculative Parallelization supported by NSF CSA-0311340 and a gift from Intel
|
Master/Slave Speculative Parallelization (MSSP, overview) is an execution
paradigm that relegates correctness and performance concerns to
separate and distinct sub-systems, what we call the correct
path and the fast path. In this way, it simultaneously
facilitates system verification (much complexity is removed from the
correctness sub-system) and aggressive pursuit of performance (the
performance sub-system is unhindered by correctness concerns).
Our current research into MSSP has focused on three topics:
- Analysis of the MSSP paradigm itself
- Exploring techniques to characterize program behavior
- Development of a dynamic distiller
|
Analysis of MSSP Fundamentals
|
We've taken a critical eye to the MSSP paradigm, in order to: 1) prove
that it does in fact work, and 2) characterize the degree to which it
delivers on the goal of decoupling performance and correctness. To
this end, we've formalized MSSP in order to rigorously reason about
its properties. The important results of this work are: 1) that MSSP
can be shown to be equivalent to sequential execution while
effectively modelling the fast path as a random number generator, and
2) an implementation-independent specification of MSSP, from which we
can reason about what properties must hold to ensure correct operation.
To complement the formal work that demonstrated that MSSP is
insensitive to the fast-path's correctness, we performed some
simulation work to explore MSSP's sensitivity to the performance of
the correct path. If insensitive, the correct-path components can
eschew some of the performance-motivated complexity that makes
difficult the verification of existing systems. Our results show that
MSSP's sensitivity to the performance of the correct path can be more
than an order of magnitude lower than conventional systems with
respect to both compiler and microarchitecture optimization.
Formal
Verification of MSSP, Pierre Salverda and Craig Zilles, (UIUC
technical report)
Formally Defining and Verifying Master/Slave Speculative
Parallelization, Pierre Salverda, Grigore Rosu and Craig Zilles (FM`05)
Architecturally Decoupling Performance and Correctness, Pierre
Salverda and Craig Zilles (in submission)
|
|
Program Behavior Characterization
|
Because the fast-path binary has no correctness constraints, we have
significant freedom in its construction. In practice, it merely needs
to compute a subset of the program's values correctly most of the
time. Thus, the fast-path binary need only compute the
non-predictable fraction of the execution, yielding significant
optimization potential, if we can accurately characterize the
program's behavior.
For this reason, we are exploring techniques to characterize program
behavior. We are particulary interested in low-overhead techniques
that can be employed in a dynamic optimizer. A key idea that we are
exploring is the concept of profile-guided profiling, where a
cheap-to-collect type of information is used to guide the collection
of a more expensive-to-collect form of profile information. Our paper
on Targeted Path Profiling applies this concept to a software-only
implementation of acyclic path profiling to achieve a 50% reduction of
overhead.
Targeted Path Profiling: Lower
Overhead Path Profiling for Dynamic Optimization Systems,
Rahul Joshi, Michael Bond and Craig Zilles (CGO-2)
|
|
Design of a Dynamic Distiller
|
MSSP provides a framework for heavily leveraging profile information
to achieve significant optimization potential. This framework,
however, is predicated on the profile information being correct almost
all of the time. Thus, it appears important to be able to adapt the
fast-path binary at run time.
To this end, we are developing a system, called the dynamic distiller,
that dynamically constructs and adapts the fast-path binary at
run-time. While the proposed design shares many characteristics of
previous staged run-time optimizers, the lack of correctness
constraints on the distiller's product signficantly influences its
design. In addition, we are exploring how to partition the system between
hardware and software in order to achieve a low-overhead, but flexible
system.
Reactive Techniques for Controlling Software Speculation Craig Zilles and Naveen Neelakantam (CGO 2005)
An Assembler for the MSSP Distiller Eric Zimmerman, B.S. Thesis, May 2004
Program Orienteering Naveen Neelakantam, M.S. Thesis, April 2004
|
|