Beyond “Nested Parallelism” Futures are a way to pipeline computations while still having “deterministic” parallel programs (i.e. ones that don’t depend on the schedule). Available in Java concurrency library. Futures 1Futures future e : generate a “future” cell and a parallel task to evaluate e. Return the cell immediately. When e is done, it places its value in the “future” cell. ? e : This operation (called “touch”) gets the value out of the cell. If the value is not ready, it waits until it is and then returns the value. Futures 2Futures 3 Consumer Producer fun produce(0) = nil | produce(n) = f(n):: future produce(n-1); fun consume(nil,state) = state | consume(h::t,state) = consume(?t,g(h,state); fun map(nil) = nil | map(h::t) = h(t)::future map(?t); The producer and consumer can work in parallel in a pipelined fashion.Futures 4 produce consume Time produce consume map P1 P2 P1 P2 P3Futures 5 Consumer Producer fun ints(0) = 0 | ints(n) = n :: future ints(n-1) fun sum(nil,accum) = accum | sum(h::t,accum) = sum(?t,h+accum) sum(ints(1000)) When there are no race conditions futures have a sequential semantics (they always return the same thing as if they were ignored)Futures 6 Quicksort with Futures fun filter f nil = nil | filter f h::t = if f(h) then h::(future (filter f ?t)) else filter f ?t; fun qsort(nil,rest) = rest | qsort(h::t,rest) = let val L1 = filter (fn b => b < h) ?t val L2 = filter (fn b => b >= h) ?t in qsort(L1,h::future qsort(L2,rest))) end; fun quicksort(L) = qsort(L,nil);Futures 7 Qsort Complexity partition append Depth = O(n) (less than, …) Sequential Partition Parallel calls Work = O(n log n)Futures 8 Quicksort with Futures Depth = O(n) Work = O(n log n) Still not a very good parallel algorithmFutures 9 Merging Merge(A,B) = let Node(AL, m, AR) = A (BL ,BR) = split(B, m) in Node(Merge(AL,BL), m, Merge(AR,BR)) m AL AR BL BR A B m Merge(AL ,BL) Merge(AR ,BR) Depth = O(log2 n) Work = O(n) Merge in parallelFutures 10 Merging with Futures Merge(A,B) = let Node(AL, m, AR) = A (BL ,BR) = futureSplit(B, m) in Node(Merge(AL,BL), m, Merge(AR,BR)) m AL AR BL BR A B m Merge(AL ,BL) Merge(AR ,BR) Depth = O(log n) Work = O(n)