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:

  1. Analysis of the MSSP paradigm itself
  2. Exploring techniques to characterize program behavior
  3. 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