Access Annotation for Safe Speculative Parallelization: Semantics and Support

The safety of speculative parallelization depends on monitoring all program access to shared data. Automatic solutions use either program instrumentation, which can be costly, or hardware-based triggering, which incurs false sharing. In addition, not all access requires monitoring. It is worth considering a manual approach in which programmers insert access annotations to reduce the cost and increase the precision of program monitoring. This report first presents an execution model and its interface for access annotation. The semantics of an annotated program is defined by the output of a (sequential) canonical execution. The report then describes a quadratic-time checker that can verify the safety of annotations, that is, whether a speculative execution always produces the canonical output. The report demonstrates the usability of the annotation interface by safely parallelizing a number of code fragments that have uncertain parallelism