Thread-level speculation systems for multiprocessors

In using multiprocessors to speed up applications, the ultimate goal is to automatically parallelize them using advanced compiler technology. Unfortunately, state-of-the-art parallelizing compilers have only proven useful for a fairly small domain of numeric applications with loops that make computations on arrays and where array elements are indexed with a linear function of the loop index variable.

In automatically parallelizing applications where data dependences are difficult or impossible to detect at compile-time, another approach is to assume that there are no data dependences and then speculatively parallelize them at run-time. By also detecting data dependence violations at run-time, we can roll-back the execution in case of a misspeculations.

The goal of this project is to develop such a speculative execution model on shared-memory multiprocessors. Unlike other approaches in the literature, our goal is to take a software-centric view on the problem by using as little hardware support as possible to implement this speculation system. Our approach is to invoke highly optimized code sequences to detect data dependence violations, to do dynamic variable renaming, and to provide data forwarding. Our hypothesis is that this approach will result in acceptable overhead and a low fraction of misspeculations. Besides using detailed architectural simulations, we will test this hypothesis by evaluating prototype systems on symmetric multiprocessors (e.g. Sun Enterprise servers).

This project will potentially offer a possibility to increase the range of applications that can be automatically parallelized for execution on multiprocessors.

• Dr. Per Stenström, Professor
• Fredrik Warg, Lic Eng

• Peter Rundberg, Lic Eng

• Ericsson Research, Alvsjo

• TSR
• NUTEK
• VR