Up Next
Go up to Introducing Parallelism
Go forward to Data-Oriented Parallelism

Simple Divide-and-Conquer Functions

Let us consider the parallel behaviour of pfib, a very simple divide-and-conquer program.

pfib :: Int -> Int
pfib n 
  | n <= 1    = 1
  | otherwise = n1 `par` n2 `seq` n1+n2+1
      n1 = pfib (n-1) 
      n2 = pfib (n-2)
If n is greater than 1, then pfib (n-1) is sparked, and the thread continues to evaluate pfib (n-2). The figure below shows a process diagram of the execution of pfib 15. Each node in the diagram is a function application, and each arc carries the data value, in this case an integer, used to communicate between the invocations. Brackets can safely be omitted because seq has a higher precedence than par.

Parallel quicksort is a more realistic example, and we might write the following as a first attempt to introduce parallelism.

quicksortN :: (Ord a) => [a] -> [a]        
quicksortN []     = []
quicksortN [x]    = [x]
quicksortN (x:xs) = losort `par` 
                    hisort `par` 
                    losort ++ (x:hisort)
                      losort = quicksortN [y|y <- xs, y < x] 
                      hisort = quicksortN [y|y <- xs, y >= x]

The intention is that two threads are created to sort the lower and higher halves of the list in parallel with combining the results. Unfortunately quicksortN has almost no parallelism because threads in GpH terminate when the sparked expression is in WHNF. In consequence, all of the threads that are sparked to construct losort and hisort do very little useful work, terminating after creating the first cons cell. To make the threads perform useful work a "forcing" function, such as forceList below, can be used. The resulting program has the desired parallel behaviour, and a process network similar to pfib, except that complete lists are communicated rather than integers.

forceList :: [a] -> ()
forceList [] = ()
forceList (x:xs) = x `seq` forceList xs

quicksortF []      = []
quicksortF [x]     = [x]
quicksortF (x:xs)  = (forceList losort) `par`
                     (forceList hisort) `par`
                     losort ++ (x:hisort)
                       losort = quicksortF [y|y <- xs, y < x] 
                       hisort = quicksortF [y|y <- xs, y >= x]

Process Diagram
pfib Divide-and-conquer Process Diagram

{trinder,hwloidl,simonpj}@dcs.gla.ac.uk, kh@dcs.st-and.ac.uk

Up Next