Video 5-4: §5.4 Parallel sorting

0:00 Intro

0:03 In the next subsection, we finally put this all together for parallel sorting algorithms that use all these these primitives that we've built up and go much beyond what we've seen initially for parallel string matching where we could get away with just these very simple tricks of parallelizing. Uh this time we'll have to try a little harder, but the algorithms that come out are uh much more interesting.

0:30 We'll look at the two key algorithms we discussed in unit three, merge sort and quick sort. So, let's let's look at merge sort and and think about how can we do what merge sort does in parallel, doing it on on our PRAM? One thing that's easy, merge sort, remember divide and conquer and all that, it had these recursive calls. You first sort the first half and then the second half, and then you merge the result when these recursive calls come back. Because the two recursive calls work on uh disjoint part of the input, you can just keep them running in parallel. And we will express that pretty much like that. Uh that's that's the easy bit.

1:16 The bulk of the work in merge sort, of course, is in merging. And if you think about it, just the very last merge, the merge that you do at the very end after the two first recursive calls came back, already takes linear time. It has to go over the entire input once. If you parallelize everything before that perfectly, but then this last bit is sequential, you're still at linear uh parallel time. And so, that's hardly better than the n log n time we started with. In general for for PRAM algorithms, your goal should rather be something like logarithmic to a power, log to the fifth power if you want to go crazy, or something like that. That's a good algorithm. Maybe square root n if you can't get down to log or poly log. Uh but um linear is not so great if you started from n log n. So, if we have to if we want to go beyond that, if we want to go faster than or have more parallelism than than that, we have to somehow tackle the merge part as well. We have to do that in in parallel.

2:22 And the method I've shown you seems completely un- unhelpful for that. And the the solution will be to come solve the same problem, but look at it from a single element's perspective, and then try to do all of that in parallel.

2:42 That's more versatile than uh than just this application. You can often do that. And it's often helpful also for other kinds of programming. So, I think this is um a good way to to practice thinking of this way. And it often leads to more scalable algorithms in in a more general sense than just PRAM. Uh for our merging procedure, we can we can say for every element, it's either in the left or in the right run initially, and we have to find its position in the final merged sorted run.

3:16 And it turns out that this position can be computed um relatively easily as the sum of two things. First of all, it's the position in the sorted output. That's the same as its rank. If you've used that terminology before, it's the number of elements that are smaller. That coincides with the position in an in a sorted array. And there's two types of elements, those that come from the left run and those that come from the right run. And uh we can just count how many are smaller in the left, how many are smaller in the right, add that up. That's your rank in the sorted output.

3:51 So, we can do that easily for one of the runs, namely the one that contains X. That run, as the name says, is sorted. So, the position of X there already is its rank within that run. And for the other run, we can use another algorithm to find the rank, and that's binary search. All the way back, unit two, we've covered it all. Uh binary search is just a way of finding in a sorted list, how many elements are smaller than some other element. Right? You start in the middle, are you bigger or smaller, and so on. You you wiggle your way through, and so you find the position where you would have to insert this element if it's not already there, so that the list remains sorted. And that's again the rank of this element. And uh if we have both of these information pieces collected, we can just add the two positions up and move the element there in a second round.

4:48 Okay? That's pretty much it. Uh this is what this looks in code. It's a little intimidating by the size of it, but all the individual parts you have either seen or they're what it was on the last slide. The overall recursive scaffolding for merge sort is as we had it before in the sequential algorithm. You first recurse in the two halves. Uh and note here I I I use the different construct that we haven't seen before.

4:54 Parallel Mergesort - Code

5:25 I didn't want to cross it out. I'm just writing do these two things in parallel, which means in uh more low-level PRAM code, you would have to assign somehow to uh processing you would have to distribute this to different processing elements. For sorting, I think it's it's usually sufficient to think of each position in the array having their its own little processor attached to it. And so doing this in parallel would just mean the left side is handled by its processors and the right side by that side's processors and they can work independently.

6:05 Then we invoke the parallel merge that we'll discuss in a second. And what's left is to copy back. Our merge method, also the sequential one from unit three, was merging from the runs into an output buffer. That's why we always pass the second array buff buffer around. So after merging is done, we have to copy back from the buffer to the array that we actually want the sorted list to be in. And we can do that in parallel as well, easy. Every processor takes care of one position.

6:40 That was the easy part, right? That's almost as we had it before with two times in parallel sprinkled in. The interesting bit is the merging. And I remember from the last slide we have to do two things. For each element we have to find its position and then we have to get it there. The first phase, finding the position, is uh for is split up in the elements that come from the left run and the elements that split that come up from the right run. But the two phases are intermingled. Uh it was it was shorter to write it in that way so you don't need an extra um an extra array for storing the target addresses. So this first one is for the elements in the left run. So you do a binary search with your element and again we do this in parallel so every processor does this for for its element does a binary search in the right run.

7:45 That returns the number of elements that are smaller in that run. And we add the rank in the left run. So, R at the end of this is the position where the element should go in the sorted output.

7:59 And so, as a second step, we just write it to that position in the buffer. That was for the for the elements that come from the left run, and the one for the right run is the same. It's just symmetric. You do a binary search in the left run, and you add the rank in the right run. But, the moving to the buffer part is the same. Okay?

8:26 I wanted to show the the detailed code for this, because I think it's it's fairly elegant using these constructions in parallel. It doesn't take a lot of code to write all these things out. Uh and there's no no really nasty bits uh needed in this. Okay?

8:55 Let's have a quick look at how how it well this does. Uh maybe we should do this in the code. So, again, what did I use for colors in the past? Maybe you need to stay consistent.

9:21 Parallel Mergesort-Code

9:21 So, if we go to merge, then uh the binary search is done sequentially, right? I'm not trying to parallelize the binary search, and I don't think it's easily possible.

9:34 I'm not aware of a of a speed up for that part. Because binary search, it very much needs to know what the comparison outcome was to decide where to go next. That's a data dependency. It's It's not easy to overcome that. So, that part will take linear time logarithmic time.

10:00 Logarithmic in the in the size of the uh run that we're working in. Uh but I'm just rounding that up to n generously because it's never longer than that.

10:11 Uh the rest is all linear is all constant time. And we're doing all this in parallel. And same here. So, we have two times log n for the merge as parallel time.

10:30 Uh then merge sort itself is a little more tricky because it is uh this recursive pro- recursive procedure that calls itself. Uh but you can do a a simple argument about the the recursion tree. So, we start with the entire list. And we cut it in two halves. Okay, almost like two halves. And you recursively cut and so on until you're eventually at individual elements all the way down. And you can argue the height of this tree is is roughly logarithmic.

11:11 Uh and on each level on each level we need to add up these uh log n cost from merge. Uh but we have to do those. Um Yes, this is a at most log n. Some of the merges are cheaper than that, but uh half of them needs a constant times log n, so uh, it's a it's correct that most merges need need theta log n. And so, the total time is on each level we have to wait log n time, and we have log n levels, so it's log squared time parallel time in total.

11:57 Now, for work, if we go back, it's it's easy in this case because we don't use any any building blocks. We just have to multiply this what happens inside the loops with how many times we do the loops. So, this merging procedure has So, because of the binary searches, this is not work efficient for merge. We know the normal merge ran in linear time, but now work has gone up from n to n log n. But, what we what we were winning from it is that the parallel time goes down to log n. Again, if you sum this up over all the levels, you can basically just multiply by by log n by the height, and you get this this bound of n log squared n work. Okay?

12:24 Parallel mergesort - Analysis

13:03 So, is that good or bad? It's much faster in terms of parallel time than any of the sequential algorithms or the simple version where you only recursively uh, sort things in parallel, but then the merge is sequential. Because that still had linear time, and now we're exponentially faster in the parallel time. So, if you have many processors, it's definitely better. Uh, the The went up a little bit, a log factor, uh which you may or may not feel. Uh that depends a bit on the number of processors.

13:35 Now, there is a way to make the merge procedure that I've shown you uh work efficient, but it's it's quite tricky and involved. Uh so, uh this is this is again just for your curiosity. Uh the key idea is something like a block being trick again. You don't do the full binary search for every element, but only for some of the elements. And you know, for the other elements, their rank must be sandwiched between whatever the next elements are where you did the full binary search. Now, that alone is not enough because you could still have a huge range for some of the elements to search, so it's is a little more tricky than that. But that's the uh the idea. You could try to not do the binary search for all elements. Uh but the uh the beauty of this simple code is definitely lost in that process. So, if you want a a work-efficient parallel sorting algorithm, um with merge sort, it's it's not so easy to get there.

14:46 Fortunately, we have another sorting algorithm. Let's also try our luck with quicksort. Um first of all, the overall structure is the same. It's a recursive algorithm, and the two recursive calls are on completely independent bits of the data, so we can do those in parallel. That's the the easy part. And again, uh if we only do that, it's not much use. We still have the first partitioning round that spends linear time sequentially. Unless we parallelize that, no good speed-up is possible. And our code that we've had in unit three for the the fast sequential partitioning method uh is not going to cut it here because it very much depends on the previous comparisons, how the pointers move and all that. So, again we have to switch perspective to a a per element point of view. And so, here it's um it's a little trickier than in merging, I think, uh but overall a bit more elegant maybe.

15:55 You you split again the the partitioning process into several phases. Uh recon- uh a reconnaissance phase where you collect information and then uh a second or a last phase where you act up act on that information.

16:11 And what is the information in this part in this case for partitioning? We just need to know for each element if it's smaller or bigger than the pivot. So, it's a single single comparison, no binary searches or something like that. Uh but then from that single comparison, you don't already know where you have to go in the final array because that depends on all the elements before you. But if you think about that, that's exactly what prefix sums can do. If you're in the group of small elements, you need to know how many small elements are before you to the left in the array. And that's precisely what prefix sums can can do for you in in decent parallel time. Not constant time, but we've seen logarithmic time.

16:58 Parallel Quicksort - Code

16:58 Okay, let's let's try to also put that in code. The recursive scaffolding is as before is even closer to the original code for quick sort. The only change here is this in parallel.

17:14 The partitioning method is a little more different. Uh we pass in again Uh, so you remember for quick sort it's it's important to choose a decent pivot element. And uh, so all that we've discussed previously about how a pivot can be chosen well or how to improve on this, that's encapsulated in this choose pivot method and the same same tricks can be played as I've shown in in unit three. Uh, so I'll don't discuss that again. Uh, so we have this position of the pivot that we passed down. And so as a first step we swap that out of the way.

17:55 Now for all the other elements, that's the first phase here, where we collect information. And this time we don't get around with without storing some information in between. So we have this array S, uh, which contains, I think it's S for smaller and L for larger. These two arrays store is an element smaller than the pivot or not. And so okay, I'm using this this Iverson bracket or this square brackets around a condition supposed to mean one if the condition is true and zero if the condition is false. It's just a shorthand. Um, so we we do the comparison and set small accordingly and large is then just the opposite of that. We can do that in parallel for each element independently because it only depends on the pivot element and this element.

18:56 Then we have these two arrays and then we compute the parallel prefix sum of those two. Because precisely again, if I'm in the small cohort, and I'm the the fifth element from the left that is small, I have to go to position five at the very end. In the large cohorts, it's similar, but I have to add the offset of how many elements are in the small group to that. So, first of all, we just compute the parallel prefix sums.

19:27 Uh then we um also compute how many elements are small in total. That's J. That will be the position of the pivot. And then we can again work in parallel for the second phase, for moving element where it moving the data where it belongs. And uh here we we do the comparison with the pivot a second time, because that's the most convenient way to know is my element, is that a small one or a large one? I've forgotten if I haven't saved it. So, the uh the cheapest way is to just look um do the comparison again. So, if if I I'm I speaking is processing element I, if I'm responsible for element AI, I check again if I'm small, then I look up in position S of I where I'm supposed to go. And if I'm large, I'm looking up in L of of I, but I have to add this offset J. There's some off-by-ones, like uh you have to subtract one here because we start arrays at zero and all all that again.

20:35 Uh I hope that the the code is correct with respect to all those details. So, again, that's the that's the moving phase. And that can all nicely be done in parallel.

20:53 Okay? Is the code somewhat clear? Let's have a brief look at how good this is again. Uh so, for the time, if you look at all of those loops, they're all in parallel, so we only have to look inside one of those, and that's constant time. It's just a single comparison and a few memory assignments. And same thing here, that's also constant time. Just a few comparisons and a few read and writes. There's of course the parallel prefix sum, which is not for free in terms of parallel time. That costs us log n parallel time.

21:36 So, the overall partitioning procedure, if you look the rest, that's constant time. That's constant time. It's all constant time except for the prefix sums. So, the overall time for the partitioning phase is log n again.

21:48 Parallel Quicksort - Analysis

21:54 Uh then if we we do a similar trick for the analysis as for merge sort, if we need log n time on on each level of the partitioning step, then uh we can multiply that with the depth of the recursion tree. Now, the recursion tree in quick sort is not quite as rigid and and clearly balanced as the one in merge sort. It's only in expectation, so uh but I don't want to go into this in more detail. I will just use the expected depth and say uh the caveat here is that this is expected case only. So, you you don't get easily this worst-case bound from merge sort. For that, you would have to pick a really good pivot, which gets us into the trouble of how to find a good pivot, and so uh I don't think that's easy in parallel. Uh but the expectation bound is fine. So, we get the same result as for merge sort, log squared parallel time.

22:53 The difference is in the work, because if we look back in terms of work, all those loops, they're just doing roughly n times some constant operations. So, that's linear time. Uh linear work, sorry. Same here.

23:20 We also have the parallel prefix sum. And now it depends which method for that you use, but we know there's a way to do it work efficiently with with linear work. So, we might as well use our good algorithm instead of one of the poorer ones. And so, the overall work is uh is linear in this case. And remember that was not so easy for merge sort. The merging step was also log n parallel time, but n log n work in the version that I've shown you.

23:56 And that means quick sort in total, if you again multiply uh with the expected depth of the recursion tree, you get n log n work. And we know that that's the best in the sequential world as well for comparison-based sorting. So, we're work efficient.

24:11 That was not so easy to do with merge sort, but but quick sort gets it here, at least in in expectation. Now, you could ask, is this the best you can possibly go for? Uh for all the natural methods, we seem to arrive at this parallel time log squared n. Is there something magic about log squared of n or log n squared, I should say. So, this this is the the typical notation. Uh I don't know if this causes confusion, but what's meant is log of n and then the square, right? Uh it's not something like log of log of n, sometimes also written with a superscript.

24:58 Parallel sorting-State of the art

24:59 log n to the power tube. Is there something magic about log squared? There's nothing magic about log squared. If you're willing to go to more sophisticated methods, you can actually get down to log n parallel time. Uh it's it's some intricate variant of merge sort.

25:18 But what you have to do for that is basically give up the nice separation of now I'm doing this merge step. When I'm done with that merge step, I'll do the next merge step higher up in the recursion tree. You have to break that all open and uh kind of start parts of the next merge while you're still finishing off parts of the previous merge. By interleaving things that way, you can uh improve the overall parallel time. Uh it's a pretty cool theoretical results. I'm not sure if this is uh realistic to ever be implemented and and be competitive. Um but it's it's in theory possible to cut it down to logarithmic time parallel time. Um and uh potentially faster on these on these other variants of the um of the PRAM where you can do concurrent rights.

26:20 That's one one one side of the things I want I just wanted to mention this result without giving you any details. That's beyond of the beyond the scope. Uh the other part in in practice, if you want to implement algorithms, we have to deal with the fact that these things are not PRAMs with these nice synchronized processors where synchronization is basically free. So the practical challenge is to do what we've done, but not break things down into tiny little work packages. And so it's often um more convenient to structure code a little differently. If you want to see some really neat and fairly recently designed examples, the Java library has a few that that are really nice and and well well readable. And nothing too crazy in the code there. Uh but they're they're in a in a way close to our parallel merge sort, just different way to slice up work packages.

27:26 I think that's that's just another way of saying uh if you were to implement a complicated algorithm that has log n parallel time instead of log squared for the simpler methods, to see that difference, you need a lot of a lot of processing elements. Otherwise, the work will dominate. Remember Brent's theorem to convert from work and span to actual time if you have a fixed number of processors. And because here work is still n log n, you need you need a fair number of processors before that difference between log squared n and and log n makes makes its way through to the final result.