Now happens-before later: Static Schedule Analysis of Fine-grained Parallelism with Explicit Happens-before Relationships

摘要

Current compilers are still largely ignorant of the scheduling of parallel tasks at runtime. Without this information, however, they have difficulties optimizing and verifying concurrent programs. In this paper, we present a programming model where the program contains explicit scheduling constraints in the form of happens-before relationships between scheduled tasks. This model allows for flexible and fine-grained ad hoc parallelism while still enabling us to statically extract an abstraction of the runtime schedule. The result of this schedule analysis can answer the question as to whether two tasks execute in sequence, exclusively, or in parallel with each other.