  In fork-join parallelism, a sequential program is split into a directed
acyclic graph of tasks linked by directed dependency edges, and the tasks are
executed, possibly in parallel, in an order consistent with their dependencies.
A popular and effective way to extend fork-join parallelism is to allow threads
to create futures. A thread creates a future to hold the results of a
computation, which may or may not be executed in parallel. That result is
returned when some thread touches that future, blocking if necessary until the
result is ready.
  Recent research has shown that while futures can, of course, enhance
parallelism in a structured way, they can have a deleterious effect on cache
locality. In the worst case, futures can incur $\Omega(P T_\infty + t
T_\infty)$ deviations, which implies $\Omega(C P T_\infty + C t T_\infty)$
additional cache misses, where $C$ is the number of cache lines, $P$ is the
number of processors, $t$ is the number of touches, and $T_\infty$ is the
\emph{computation span}. Since cache locality has a large impact on software
performance on modern multicores, this result is troubling.
  In this paper, however, we show that if futures are used in a simple,
disciplined way, then the situation is much better: if each future is touched
only once, either by the thread that created it, or by a thread to which the
future has been passed from the thread that created it, then parallel
executions with work stealing can incur at most $O(C P T^2_\infty)$ additional
cache misses, a substantial improvement. This structured use of futures is
characteristic of many (but not all) parallel applications.
