Overview

Memory accesses in loops are often stride-predictable. We exploit this fact by speculatively executing sequential loops in parallel at runtime. This can be done with no compile-time analysis and no hardware support, enabling us to parallelize code whose memory accesses are indeterminable until runtime on current multiprocessors.

We have two application domains:

  1. Automatic parallelization via compiler of loops that cannot be completely analyzed statically due to complex pointer use or to dependence on dynamically-defined data (program inputs).
  2. Dynamic parallelization of loops in native binaries using only information gleaned at runtime.
The second domain has not been fully explored yet. We have preliminary results in the first domain vindicating our methods: we obtain moderate speedups on loops not automatically parallelizable by any other compiler known to us.

Publications

Derek Bruening, Srikrishna Devabhaktuni, and Saman Amarasinghe. Softspec: Software-based Speculative Parallelism. 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-3), December 10, 2000, Monterey, California. (Gzipped Postscript | Pdf)

Derek Bruening, Srikrishna Devabhaktuni, and Saman Amarasinghe. Softspec: Software-based Speculative Parallelism. MIT/LCS Technical Memo, LCS-TM-606, April 2000. (Gzipped Postscript | Pdf)

Srikrishna Devabhaktuni. Softspec: Software-based Speculative Parallelism via Stride Prediction. Masters Thesis 1999. ( Postscript | Pdf)

People

Present:

Derek Bruening (iye@mit.edu)
Saman Amarasinghe (saman@lcs.mit.edu)

Past:

Srikrishna Devabhaktuni
 
Computer Architecture Group Laboratory for Computer Science MIT