 |
|
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:
|
|
|
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) |
|
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)
|
|
|
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) |