Functional Programming to the rescue? No side effects makes parallelism easy right? It is always safe to speculate on pure code Execute each sub-expression in its own thread? Alas, the 80s dream does not work Far too many parallel tasks, many of which are too small to be worth the overhead of forking them Difficult/impossible for compiler to guess which are worth forking Idea: Give the user control over which expressions might run in parallel
No side effects makes parallelism easy, right? - It is always safe to speculate on pure code. - Execute each sub-expression in its own thread? Alas, the 80s dream does not work. - Far too many parallel tasks, many of which are too small to be worth the overhead of forking them. - Difficult/impossible for compiler to guess which are worth forking. Idea: Give the user control over which expressions might run in parallel
The par combinator par::a→>b->b x par y Value(ie, thunk bound to x is sparked for speculative evaluation Runtime may instantiate a spark on a thread running in parallel with the parent thread Operationally, x par y y ypically, x Is used inside y: blurRows par(mix blurcols burrOws) All parallelism built up from the par combinator
Value (ie, thunk) bound to x is sparked for speculative evaluation. Runtime may instantiate a spark on a thread running in parallel with the parent thread. Operationally, x `par` y = y Typically, x is used inside y: All parallelism built up from the par combinator. par :: a -> b -> b x `par` y blurRows `par` (mix blurCols blurRows)
Concurrency Hierarch Very very Light Sparks Light Haskell Threads Heavy OS Threads pu cpu cpucpu
The meaning of par par does not guarantee a new haskell thread It hints that it would be good to evaluate the first argument in parallel The runtime decides whether to convert spark Depending on current workload This allows par to be very cheap Programmers can use it almost anywhere Safely over-approximate program parallelism
par does not guarantee a new Haskell thread. It hints that it would be good to evaluate the first argument in parallel. The runtime decides whether to convert spark - Depending on current workload. This allows par to be very cheap. - Programmers can use it almost anywhere. - Safely over-approximate program parallelism
Example: One processor x par (y x y is evaluated x is evaluated x is sparked x fizzles
x y is evaluated y x is evaluated x x is sparked x fizzles x `par` (y + x)