Video 7-5: §7.4 Parallel sorting

0:02 in the last subsection on Parallel algorithms we'll look at the Sorting problem again as an example where immediate traes the parallelize it don't work it's not an embarrassingly parallel problem uh but with the preparation from these Primitives from the previous section we can get something uh that is that is useful in practice and is indeed used for example in the Java library but let's start from from first principles uh we've seen two key sorting algorithms right quick sword and merge sword so um there's other sorting algorithms out there but these are the efficient ones so that's that's the two candidates that we could try to parallelize um merge sword is a little easier so we start with that one now first of all it's a recursive algorithm it's a divide and conquer method so whenever you do some recursive calls these are independent you can do them in parallel uh that will introduce a new piece of uh of pseudo code notation where I'll just write in parallel and then two recursive calls again depends on on the actual programming language how to do this um but that's a that's something that is even better supported than these parallel Loops uh but that doesn't get us so far so uh if we if we only parallelize

1:23 the left and right recursive calls we still as at the very last step we have to merge the first half and the second half of the array into the final output uh and that that takes linear time we've seen the merging method in detail back then in unit 3 um unless we somehow parallelized the merging as well the best we could hope for is go from time n login standard merge sord sequential to Big O of n maybe but we're stuck with that if we don't parallelize the merging step

2:01 so in particular the method that we've that we've seen there uh just just to remind you how did we merge to sorted runs we started with a pointer at the minimum and then we compared those two the smaller one goes to the output and then that pointer moves one forward and if that one's smaller now that goes to the output moves one forward that doesn't seem to work well in parallel because again it's like for the summing up all the uh for the for the sequential prefix sum every Next Step seems to depend on the result of the previous step so I can't do that in uh independently so we have to find something else where we do treat elements entirely independently uh and um we can do that by conceptually splitting merging into two steps um what merging does conceptually is is two things it finds for each element where where it should go in the merged output and the second stage is it rearranges the elements so that they end up there in our sequential algorithm we do the two things inter Le we always put one element at its final position and then move on and we only ever find out where an element goes just before we put it there but we don't have to do it that

3:21 way uh we can split these two things um so if if we if we look at that in more detail let say we pick some element um X in in the sorted output then um okay from this this picture that I was always drawing at the Sorting unit X could be somewhere here and now the question is where does it go in the sorted output where does it go well it goes um at the position of its rank namely um the number of elements that are smaller is its position plus minus one how many elements are smaller than than x in this run well that's exactly the position in that run because it's a sorted list uh in here we don't know we have to search where X goes but there's some position where X would fall if it was inserted into that run how do we find that position well we can do a binary search so the uh the overall position of X in in the sorted output is the sum of the number of elements that are smaller than x in the left and in the right run and uh one we get for free because it's the position where that element is located and for the other we need one binary search in the other run starting

4:51 in the middle and then you've seen it in more detail in in unit two so with the binary search we can find where a needs to go but then we just do this in parallel for all the elements save where they should go and then put them there in the second

5:21 step and um in code that looks like this so let's uh let's go through this in in a little detail uh first of all the simple part is is the parallel recursive calls so that almost looks like standard merge sword um with with Smo two small twists first of all like in standard merge sword we find the Middle Point that's where we split we're not doing Peak sword right uh then we can do in parallel the two recursive calls and um remember we have to pass a buffer around and the convention was uh that we um that uh we use the buffer but the sorted result at the end is back in the array that it that the unsorted elements were in then we call parallel merge well we'll we'll come to that in a second which leaves um everything in the buffer so we have to copy it back afterwards and this last part this we can do in parallel by a simple loop I just take every Loop iteration takes one element from one array copies it into the other one uh that we can do in parallel now for the merging itself uh we first determine the rank of each element and for that we do the elements in the left run and the

6:43 elements in the right run separately first we do the ones that are in in the left run so we know how many elements are smaller in their run and we add the result of a binary search so here the I'm assuming ass uming that this this binary search returns exactly the the number of elements um for searching this element in this array now the binary search we do sequentially there's no fancy fancy thing happening parallel

7:24 wise and then we do the same thing again just the mirror image we go through all the elements in the right run we add their rank in the right run which is just the position and we do the binary search in the in the left

7:40 run and once you know the uh so here I could have split this up into a second round um but once we have the the loop here as well we can already write them to the buffer array at this point so how how fast is this because we don't do the binary search in parallel it'll have login span and and work exactly and N is the length of the of the array so if we have um parallel merge on something of length and half and N half then uh we'll

8:35 we have constant time for the rights and uh we do the rest in parallel so the overall span of the merge is log in now if we analyze the work we have to do this binary search for each of the elements eventually so it'll be n login work

9:10 so we're not work efficient right parallel U merge needs n log n work but we could do the standard merge in linear work uh but at this point we'll we'll leave it with that um so we get login span for the binary search but um uh uh the overall work for one merge is and login now what happens with the recursions is um that we start with the entire array then we recurse on the two halves and we keep going like

9:51 this uh until we have individual elements we've discussed the recursion for for merge sord in more detail back then the the depth of this tree is the is this log n that's how many times we have to cut things in half and on each of these levels we do things in parallel because the recursive calls are in parallel but I have to spend uh at most log n on each step but actually on the first half rounds down I have to spend Theta log n so overall I spend login Times login uh span over across all the levels up to constant factors um it doesn't help that I get smaller inputs they don't get small or fast enough so the total span for for this parallel merge sword is log squared but that's still that's still a substantial speed up from sequential where we had at least n log n as the running time so even if you have a reasonable number of processors this is going to speed up sorting a good bit now we're not work efficient in the merge which means we also won't be work efficient overall by essentially the same argument you also get this extra log Factor you get n log squared n as work for the overall algorithm but again

11:14 as as before um a log factor is is not that bad uh you can still get a good speed up with the reasonable number of processors um unlike back then uh leave it with that but it is possible to get merg down to work efficient again uh there's different solutions um a relatively clean one is not completely unsimilar dissimilar to our blocking method but I still decided not to give you the details here because it it gets a bit gets a bit messy so I'll leave it with a statement that it's possible and um the details are for example in this uh in the lecture notes um from another lecture that are linked on the website if you're if you're

12:12 curious now um what I didn't comment on uh both both measures are not optimal um the work you can get down to n login by making the merge work efficient the span is also not perfect because it's also log squared and you can't get it down to log in but that algorithm is even more crazy so um we're not discussing it but I guess it should be as a as a comment

13:02 here so the combination is possible on on the appropriate Ram Pam model but the algorithm is is substantially more complicated this part doable just a bit too much for us so I didn't want to do it uh this is very tricky okay let's take a a quick look at quick story before I let you go um we can do the same as before we can do the recursive calls parallel easy same as before if we don't parallelize the partition step we won't really get down below log below linear time um even in parallel so that's that's not going to help us that much but we can parallelize the partitioning round as well and we can do this by uh again splitting a a Recon phase and the data movement phase uh and doing things in parallel there now remember quicksort partition you have this pivot element and for each element you have to find whether it's smaller or larger and you have to put it to the left or the right that's the two different parts doing all the comparisons with the pivot in parallel is easy you can just remember the outcome and then you're done moving things to the appropriate place is a little more tricky because the position where an element goes depends on how

14:22 many other elements are smaller than the pivot uh but that's where our friend the prefix sums come again into play so um we can do this as follows I'll I'll just go over the parallel partition the code for the overall algorithm is is exactly as for standard quicksort apart from this in parallel here so uh we get our um our pivot element that's that's this one and we swap it to the last position then we determine for every element in the array uh whether it's smaller so this notation here means this this square brackets means if the condition is true it's the value one otherwise it's zero it's just a short way to write that so in in s of I we we store a one if that element is smaller than the pivot in L ofi we store the opposite just to have the have that convenient and this we can do in parallel it's independent each each just compared with the pivot element

15:33 um then in parallel we can do the parallel prefix sums of both S and L S and L are again uh just a binary ve binary arrays so the prefix sums essentially just count how many ones are before a certain

15:53 position um and then again in parallel we write the elements where they should go so um we do the comparison with the pivot again and then we either use S or we use l to write the element to a certain position in the output and here again um we make use of the fact that in this pram model the things are synchronized because everything runs in lock step uh so we can we can just write it to the same array that things come from we first read all the elements and then we overwrite the array and the the Pam synchronized is that for us so that's that's the details here first first uh find where elements go and then move them there in the Second Step same as for merge for for the merging step that's that's the key that we had to split to parallelize

16:50 things uh because we use the parallel prefix sum we inherit the logarithmic span um what we can get this time though is linear work work so we get an overall algorithm with n log n work without any tricks that I didn't show you so it's work efficient overall at least in expectation uh and uh the same span is for merge sord we have logarithmic span for each partitioning step and in expectation we have log many levels in the recursion tree and so that multiplies again to log squ

17:34 let me just uh finish with um what I already mentioned you can um you can get this this more sophisticated method that's work efficient and login uh span on the crew Pam at least uh but that algorithm is not very practical if you want to put this in practice you have to work on reasonable chunks of uh the sub problem otherwise the synchronization is is too much overhead

18:00 uh and uh you can you can see some examples of that in the Java Library uh you can there's ray. sort which is standard sorting method but they also have ray. parallel sort and they're essentially using the merge sort I've shown you with a few extra tricks to avoid two small uh blocks of of things uh but this basically based on that