Compiling Sequential Programs for Speculative Parallelism

Chih-Po Wen and Katherine A. Yelick

We present a runtime system and a parallelizing compiler 
for exploiting speculative parallelism in sequential
programs. In speculative executions, the computation consists
of tasks which may start before their data or control
dependencies are resolved; dependency violation is detected and
corrected at runtime. Our runtime system provides a shared
memory abstraction and ensures that shared accesses appear to
execute in the proper order.  Our compiler transforms
sequential programs into parallel tasks and manages control
dependencies. It also optimizes the parallel program using data
flow analysis to reduce the cost of speculative execution.  We
demonstrate our approach through the parallelization of an
example application, and report on its performance on a 
distributed memory multiprocessor.