Video 3-8: §3.7 Parallel sorting

0:00 Intro

0:02 in this last subsection on sorting we will look at how to parallelize the sorting algorithms that we've previously studied quicksort and merge sort we start with quick sort because that's slightly easier there's two parts to quick sort as you will remember there's the partitioning step and there's the recursive calls in the left and right sub arrays now um the recursive calls are immediately data independent because they work on disjoint parts of the array so you can just call those in parallel um and we we will write you can effectively write this in pseudocode as as you want but uh um well i'll i'll show you one way at the at the very end how we can do this so that's that's the easy part whereas the partitioning algorithm seems tough to parallelize

0:10 Quicksort

1:07 i want to make one for the comment here if you were to only parallelize the recursive calls it seems like this should massively help because instead of recursing on two things you just recurse down on one side effectively for in terms of time but the problem is that then the parallel time is entirely dominated by the first partitioning step and that takes linear time

1:52 so the best we can hope for is to reduce time to linear and while that's that's better than n log n it's not exactly great uh because it leaves a lot of potential for parallelization on the table and indeed parallelizing it and only getting a logarithmic speedup is not usually scalable to really big inputs so we definitely have to parallelize the partitioning step itself as well and that seems more challenging but we can again view the problem slightly differently and then we get to something that can be parallelized in this case we can do it in three rounds we can first do all the comparisons with the pivot element and we can store the results then we can compute prefix sums of this bit vector with the previous you see how parallel prefix sums occur here over and over again and as the last step we compute uh we can we compact the subsequences of small and large elements again with the primitive we've just seen so in total um that is what gives you um what gives you a parallel partitioning method um let's uh do a a quick example here maybe again okay i want to make it really small so that doesn't eat up too much time

2:23 Parallel sorting

3:34 and let's say 5 is our pivot so what we would do is we store a bit vector smaller and then 3 is smaller than 5 7 is not smaller than 5 1 is smaller than 5 2 is smaller than 5 6 is not 8 is not and well it might be helpful to do the same thing for the larger elements which here is effectively just negating everything

4:04 and now we have a compaction problem like we've seen it before with s if we compact this array we just select the smaller ones so just selecting those where there's a 1 in s gets us to this and we probably want to start at the front because we want to put the pivot in between

4:34 and the other ones have a 1 so we want to put them after the pivot and put the pivot in between that is partitioning in a way that is friendly for parallelization and uh in in the full glory of the code this looks like this uh i know this looks a bit intimidating but i just wanted to spell out all the steps there's not much complicated happening here

5:07 we have a recursive procedure parallel quick sort which looks exactly the same as the previous one the exception is only that here we say in parallel you call yourself recursively that's the only difference other than that it's choosing a pivot and calling the the partitioning function but the partitioning function is also parallelized now and uh what it does is well it swaps the pivot to the to the last position here that turns out to be more convenient then in parallel we do the comparisons so you compare your element against the pivot and i use this notation [Music]

5:47 if you have a predicate something something that can be true or false i write this square bracket and that's just to mean one or zero if the if the predicate is true

6:07 and zero if it's false so that's just a shorthand for that and so s is smaller l is larger that's just the inverse then we do the parallel prefix sums for those two parts calling those in parallel is fine but does it only saves the constant factory i could have left it out as well um and now we use here that um this is essentially the number of small elements that's the starting index for the big elements and then we have another loop in parallel where we read the old value at position i and write that value to either um the

6:56 so and so many position in the small array or in the big array depending on whether i is smaller than the pivot or not we could have replaced this check with s i but we have overwritten as i in the prefix sum so it's most convenient to just do the comparison again usually the comparison is is fairly fast compared to the overhead that comes from the parallelization

7:28 yeah that's uh that's it that code exactly this what i did on this example so um i don't want to comment on this much further if you if you read it in more detail you will see that

7:45 HyperQuicksort

7:51 um there was a question on this uh that i want to show let's stop the poll um i'm not sure what hyper quicksort is it might be a parallel model uh using hypercube um networks so that's more of a it's more a distributed model where you send messages around maybe you have to send me more details about this

8:21 any other questions about the parallel quicksort if so then then put them in and we can discuss them and i would want to briefly discuss the analysis uh before we move on to merge sort

8:39 by going through the code you see that essentially all steps in the partitioning procedure are just constant time in parallel the only thing that's not constant is the prefix sum computation so that gives you a logarithmic time and that's the that's the time for partitioning but we don't just do one partitioning step we have to recurse now we do the recursion in parallel but we still have to execute one recursive step after the other finish the partitioning at the top recurs on on one side because there's data dependencies you have to finish partitioning at the top first before you can recurse so we get an additional factor from the depth of the recursion tree and remember we talked about this uh they're like binary search trees so the expected height of sets of this tree or even with high probability um the height of this tree is logarithmic which gives us a log squared time in expectation

9:43 and for the work the partitioning call is everything is very simple except for prefix sums we know how to do this so you can reduce the amount of work also for the prefix sums to linear and so uh we could essentially slash off the the power of the the two here if we want to use the the blocking version so uh we can achieve n log n time the comment is below here so i'll just leave it as it is with the simple prefix sums you get n log squared and work in expectation uh with the work efficient prefix sum you get expected work efficient sorting and log n is best possible because we're still in the comparison model you remember the lower bounds

10:41 it doesn't look like there's other questions on quick sort for now so let me briefly move on to merge sort we can parallelize merge sort in a similar way the recursive calls exactly the same argument they're data independent so you can parallelize them very easily what's not so clear is the merging step because again the sequential algorithm used used to get the the smallest from the runs one at a time and it seems this can't be parallelized without again formulating the problem a little differently what we have to do is treat all the elements independently in a way and indeed this is possible also for merging using the following idea the correct position for some element in one of the one of the two runs so the input to the merging procedure if you remember

10:45 Mergesort

11:50 and let's suppose we have some element x here now the output looks like this a one sorted long run and at some point we have our x so the question is where does where does this x belong

12:11 can we somehow find out where x should go um without going through all the data dependent steps of the standard merging and yeah and the answer is yes because it's a sorted list so the position of x is its rank the number of elements that are smaller than x and the number of elements smaller than x is the sum of two things it's all those guys here and well all those guys that are before a certain bar where x would be if it was in the list but it's not really there so we don't know how many these are

12:53 but for one of the runs we can just take the position of x so that's easy that's the first comment here and for the other rank for the other run we can use binary search to find the insertion position we just pretend we wanted to insert x into the other run use binary search to find the position but then don't insert it we don't really want that we just want to know where it would have belonged and that gives us the rank in the other run and then adding those two things up gives you the position in the output array again i'm assuming here that as for for standard merge sorry we have a buffer space where we write elements to that makes it a little easier we have we have to buffer the outcomes of these binary searches

13:43 um if you do this um i want i have to speed up and get to some some other topics i could keep on talking about sorting but i want to keep this part um bring this part to an end now uh so no no detail code for for merge sorts but what you can do is you get in in parallel time you get login from all the binary searches but you do them all in parallel so for each element you do a binary search in the other run everything else is is just constant time in in parallel time uh and the the depth of the recursion tree in merge sort again is logarithmic and this time it's even worse case because we always cut things exactly in half so we get the same total time as for quicksort except that again here it's worst case not only expected the work is slightly worse we need to do n binary searches and each binary search needs login steps to find the position in the other run and that gives us an n log n work per merging step so if you multiply that again with the depth of the recursion tree you get to n log squared n it doesn't seem to be easy to improve this with any very

15:03 simple tricks but it is possible to get down to linear work for merge and the trick is to not do the binary searches for all elements but only for some of them which gives you a range for all the others and then you can use a simpler methods a simpler method within that block but it's it's a little more complicated because you cannot easily control the size of the blocks so no details for that essentially just the claim here that linear work again is possible for merge sort so you can also turn parallel merge sort into a work efficient sorting algorithm and again you get the parallel time log squared which is um is is a really good speed up in in practice

16:02 i want to finish this unit with a last comment on the theory state of the art for parallel sorting uh it turns out if you look if you try to get below this log squared n you have to use more sophisticated algorithms but it is possible to do it with just log n parallel time on on our

16:26 concurrent read exclusive write ram model so that's the standard model that comes closest to what we can realize in practice these algorithms tend to have overhead in that they use very small units of work and that's not what practical implementations uh like i didn't talk a lot about how the pram compares to practical models of concurrency most programming languages give you threats that you can start so it's some programming languages allow you to do loops in parallel but with restrictions

17:12 and most programming languages allow you to spawn a new thread and interact with it in various ways so there's usually some overhead attached to starting off parallel computations and then synchronizing them back so that you collect all the results so what you really want is not too small units of work which is also the reason why implementations like the ones in the java library tend to use methods that are very similar to the parallel quick sorted merge sort that i've shown you because there you can reduce the the granularity of parallelization of parallelism

17:54 uh but still it's it's interesting that you can get rid of this log squared factor uh at least in in theory and that needs interesting methods but that's beyond the scope of this class

18:08 and uh yeah that's that finally concludes the unit on sorting i hope you enjoyed this part we've done a deep dive on parallel methods and the prefix sums and we've seen that this is the core step to solve sorting in parallel with very good parallel time and essentially optimal work and that's the basis for parallel sorting