andoperations was recently discussed at length on my student, Lindsey Kuper’s, blog.
This is a follow-up to that post, with the purpose of laying out a taxonomy of conjunction operations that might occur in a parallel language. (The same discussion applies equally to disjunction.) Below I classify these operations into five levels, from basic to full featured. A good context to imagine as we go through this is a computationally intensive search problem with lots of nested parallel conjunctions and disjunctions that expose opportunities for parallelism.
Before we get started, some ground rules. We need the operation to take some kind of deferred computations or thunks. Further, we assume these can be turned into futures for exposing parallelism. In our case, we use Haskell and the
Parmonad so this means that we expect something like this:
result <- span=""> asyncAnd comp1 comp2 ->
comp2are monadic computations that, once executed, return a
Boolvalue. But the distinctions below could just as well apply to a plain, non-monadic
andoperation in a lazy, pure language — for example, Haskell’s
- Strict: Evaluate both
comp2in parallel, and then return the logical and of the resulting booleans.
andis parallel, but is also less work-efficient than the sequential left-to-right short-circuiting
&&operation found in most programming languages. It always evaluates both computations fully. Thus, our next upgrade is short-circuiting.
Level TwoHere it helps to generalize a bit and consider an
andthat takes a list of an arbitrary number of input computations:
- Short-circuiting: for a list of input computations, evaluate them using a machine-specific degree of parallelism, but also stop launching new computations whenever a
Falseis encountered in an already-completed computation.
(&&). That is, some input computations have the ability to short-circuit (deschedule) others, but the relationship is not fair; it’s not all-to-all.
You can build an N-way
andmeeting this limited criteria using (1) a level-one parallel
andtogether with (2) a short-circuiting sequential
and. The two operators could be combined by a heuristic strategy for determining how many parallel tasks are appropriate, and then "bottoming out" to the sequential version. Still, as long as the sequential
andis used, inputs are handled asymmetrically; and as long as a level-one parallel
andis used we will run unnecessary computations that can’t be descheduled or canceled. Indeed, this is a real tension: work-efficiency vs. parallelism.
- Short-circuiting, symmetric: all input computations are potentially evaluated in parallel, and any one of them returning
Falsequickly can potentially cause the result of the entire
andoperation to become available immediately.
Falsethat remaining computations will be cancelled in bounded time. Thus our fourth level concerns cancellation.
- Symmetric with cancellation: When an early answer is given, all other threads/tasks are told to stop computing because their answers are no longer needed. There exists a bound on how much computation lingering child-computations of the
andmay do after this point in time.
ands are pretty rare in practical parallel languages and libraries, simply because [transitive] task cancellation is not a common feature of modern parallel runtime systems. I would be happy to be wrong about this! So please share any links to standard library documentation that mention level-four parallel
ands out there in the wild.
Level FiveOur final stop is a feature that is not strictly a property of the conjunction operator itself, but rather a complementary feature we find useful in some of our applications. It concerns the ability of canceled computations to do useful work, by storing partial results that are computed before cancellation occurs.
In an unrestricted parallel language, canceled computations may have arbitrary side effects, which, in general, race with the cancellation message itself. In a deterministic language such side effects cannot be allowed; rather, it is usually safe to cancel only "pure" computations. There is one exception, however, a memoized pure function provides a "side effect free" way of storing partial work.
- Cancellation + memoization: Canceled threads never provide a final result, but they can contribute to other computations by adding to their memo-tables.
Our recent draft paper on "taming the parallel effect zoo", discusses the combination of cancellation and memoization further.
Is there a level six? Is there anything else we might ask of our parallel logical operators?
Final thoughts: Parallel conjunction/disjunction in GHCGHC with "sparks" (futures) can do level-two
ands, for example by sparking the arguments to
(&&). But short-circuiting must follow a predetermined order. Further, cancellation is not possible with sparks, because sparked computations cannot be removed from the spark pool.
If one could use internal GHC functions to determine whether an object is a THUNK or CONSTR at runtime, it would then be possible to do more flexible short-circuiting, for example, sparking some elements of a
[Bool]while executing others on the current thread, and inbetween executions, polling for completion of the already-sparked futures. Yet this road seems unappealing for a number of reasons.
Alternatively, rather than using the spark mechanism, it is certainly possible to use
MVars to implement parallel-and in Haskell, as Conal Elliot does in this post, using an
forkIOis vastly higher overhead than sparks, with our own
Parmonad’s futures falling somewhere inbetween. Moreover, our desire to include transitive cancellation and memoization features motivates us to build these operators on a custom
Parmonad rather than with
IOor sparks directly.