A Semantic Framework for Scheduling Parallel Programs

Declarative parallel programs offer deterministic results, allowing the language implementation to schedule parallel tasks in any order. However, program performance hinges crucially on the way that these tasks are scheduled. In this work, we use formal language semantics to express different scheduling policies. These semantics enable us to compare different policies and to understand their effects on the use of space. We offer several example programs to demonstrate that scheduling policy can have a dramatic, and even asymptotic, effect on space usage. To predict performance, programmers require a means to understand the effects of scheduling. We define a cost semantics that allows programmers to reason about how space is used by parallel declarative programs. At the same time, these costs provide a specification for how implementations should behave.