Techniques for Module-Level Speculative Parallelization on Shared-Memory Multiprocessors
Project no: 0005-04
Per Stenström and Lennart Pettersson
Chalmers University of Technology, Department of Computer Engineering
Application, curriculum vitae, support letter from Ericsson Utvecklings AB.
Comments by evaluators.
Support: 1 PhD student for 1 year decided 00-06-16.

Industry contact

Lennart Pettersson
System Processors Department
Ericsson Utvecklings AB, Box 1505, SE-125 25 Älvsjö, Sweden
Project: Techniques for Module-Level Speculative Parallelization on Shared-Memory Multiprocessors


Multiprocessors have hit the mainstream and cover the whole spectrum of computational needs from small-scale symmetric multiprocessors to scalable distributed shared-memory systems with a few hundred processors. This has made it possible to boost the performance of a number of impor-tant applications from the numeric and database domain. Extending the scope of applications that can take advantage of the performance of multiprocessors is however hindered by the fundamental limitation of static (off-line) parallelization methods to only uncovering data dependencies that do not depend on input data.

We consider in this research the prospects of exploiting module- (function-, procedure-, or method-) level data dependence speculation to simplify the process of extracting inherent coarse-grain parallelism out of sequential codes. Given that codes have been developed using good pro-gramming practice, our hypothesis is that there is plenty of parallelism to uncover in such codes and a majority of the data dependences will be resolved by the speculation system.

The key question is how to uncover this parallelism and to identify concepts for a speculation system that reduce the number of mis-speculations and yet impose as little overhead on the execu-tion of the threads in parallel. We approach this problem by (1) performing a limit study on avail-able parallelism in commercially used codes in telecommunication systems as well as in benchmark suites such as SPECJava. (2) We then investigate methods for how to extract the parallelism in these codes. In particular, we study the upper-bound on speedup that can be achieved by control-flow and value speculation applied to codes with module-level parallelism.

The expected results of our research is a method that can be integrated in existing software infrastructures for extraction of parallelism in important codes. These results can be transferred to our industrial collaborator and can be used to increase the capacity of telecommunication servers. It will generate important scientific results that contribute to the knowledge about the opportunities and limitations of exploiting module-level parallelism using speculative execution.




  1. Warg, F. Module-Level Speculative Execution Techniques on Chip Multiprocessors, Licenciate Thesis, Dept. of Computer Engineering. Chalmers University of Technology. 2003.

  Strategic Research