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 understand the effects of different
scheduling policies on the use of space. We offer a series of examples to
demonstrate that scheduling 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, this
semantics provides a specification for how implementations should behave.  Our
costs are parameterized so that they can be used to model many different
scheduling policies. We consider several such policies for task-parallel
implementations and analyze their behavior.  Our semantics can also be used to
study the effects of compiler transformations. We recast a compilation technique
for nested data parallelism in light of our framework. We show that this
transformation induces a particular schedule and then give an example where this
schedule requires asymptotically more space than an alternative.