  The constant increase in parallelism available on large-scale distributed
computers poses major scalability challenges to many scientific applications. A
common strategy to improve scalability is to express the algorithm in terms of
independent tasks that can be executed concurrently on a runtime system. In
this manuscript, we consider a generalization of this approach where task-level
speculation is allowed. In this context, a probability is attached to each task
which corresponds to the likelihood that the product of the task will be
consumed as part of the calculation. We consider the problem of optimal
resource allocation to each of the possible tasks so as too maximize the
expected overall computational throughput. The power of this approach is
demonstrated by analyzing its application to Parallel Trajectory Splicing, a
massively-parallel long-time-dynamics method for atomistic simulations.
