Video 3-10: §3.9 Parallel sorting

0:00 Intro

0:03 All right, uh a last little subsection on the sorting topic brings all this parallel pre-text back to sorting algorithms. Which we haven't talked about in a while, uh and basically not at all today.

0:19 Of course, we would like to take the primitives we've just built and the PRAM model to also sort an array efficiently in parallel. And it's natural to start from the simple algorithms that we looked at at the beginning of this unit, namely quicksort and merge sort. They're both divide and conquer algorithms, so they have these recursive calls. And if you think about it, say quicksort, um we pick a pivot, we partition, then we have two parts, and we recursively sort this part and recursively sort this part. We actually have no data dependency on the two recursive calls. They can be done entirely independently. So, one easy thing is recursively do the two steps and do that in parallel. And that's one thing that we will do. Uh but that is somewhat limited in um how far we can get this.

0:29 Parallel quicksort Let's try to parallelize quicksort

1:23 If we only did that, we're still stuck with the first partitioning step giving us uh linear time. Unless we parallelize that, we have to do it in one processing element, and we have to spend linear time for partitioning. So, we're stuck with linear time parallel time. Uh the work can be fine, but this is like we went from n log n down to log and from n log n down to n. It's not that great. With the other problems, we went from n to log from n down to log n. That's that's a much bigger step. So, uh we can think about parallelizing the partitioning step. That's the remaining problem, okay? Instead of sorting, now it's partitioning.

2:10 Uh and we can do this for for quicksort style partitioning relatively easily on a PRAM. The idea is just do away with the good sequential methods. Uh we spent a lot of time talking about this in an detailed example, but for this, uh flush your brain and forget about it. Instead, think about partitioning more abstractly. What is it? We have to find out where each element goes, so we compare with a pivot, and then we have to physically move it to the left or right. But we can decouple these two parts. It was completely intertwined in the partitioning algorithm that we've seen, the sequential efficient one. Uh but if you if you're working on a parallel machine, you want to decouple things. So, what we do is first do a round of comparisons, and we can do this in parallel because it doesn't depend on each other. Whether this element is smaller or bigger than the pivot doesn't depend on whether this element is smaller or bigger than the pivot.

3:05 And we store the results in in a convenient form. Um and then what's left is compacting the subproblem we've just solved. If you store in bit vector a one for all the elements that are smaller than the pivot, if you take those out and compact them, that's your left subarray that you want to recurse on. Okay? And that's how this um this fits into the puzzle. Uh and I spelled out the code in in some more detail here. Um I want to point out this construction in pseudo code. I just wrote in parallel and then uh a set notation. There's other notations. Sometimes people write this with uh So, one of the the textbooks that I cited uses this.

3:34 Parallel quicksort - Code

4:02 Two pipe symbols uh means execute this in parallel. That's just saying we do the two recursive calls in parallel. For the partitioning itself, uh maybe it's worth studying this code in a bit more time than I want to give it now.

4:19 Uh but you can recognize here we do in parallel the comparison step. We compare each element, so every processing element is responsible for one element in the array. We compare that to the pivot element. And these these uh square brackets are supposed to mean if the condition inside is true, then it's a one, otherwise it's zero. It's something that programming languages often do just out of the box, but uh in mathematical notation, that's a convention to write it. And so, S stands for smaller. That has a one for all the elements that are smaller, which means on the other hand, if the element is is not smaller, it's bigger. So, we write 1 - S.

5:01 Then we compute parallel prefix sums of those two. That's in a sense for for compacting. Um and then we want to uh create two new arrays where well, we we reuse A to put all the small elements into the left part and the large elements in the right part where we have this this offset J, where J is the number of small elements in total.

5:33 Um yeah, here yeah. That's what the code does. Um I would suggest study it in a bit more with a bit more time, and uh use use Campuswire if something's unclear. The notation needs a bit getting used to.

5:57 Parallel quicksort - Analysis Time

6:01 Okay, I want to briefly see how how well this works now. Um in the interest of time, let me just tell you the end result, and we don't look at all the details. Uh the time for partitioning is is constant except for the prefix sums. All the other steps we do, once you take the parallel loops out, what they do is just compare some things and store it in an array. That's all just constant time. The only thing that takes parallel time is the prefix sum, and we've seen that that's logarithmic.

6:34 Uh then uh that's for one partitioning step. But we also have to have the recursion somehow taken into account. And remember, we have to finish the partitioning step before we can recurse. So, there is a data dependency between those. The depth in the recursion of quicksort can be bad. We know the worst case is quadratic and all this uh sad story, but the expected depth, the typical depth uh is logarithmic. So, uh in terms of span, the data dependency is along the recursion tree, and so it's it's log n high, and each step is up to logarithmic, so that gives you a log squared uh span. Okay? That's a substantial improvement over n log n and also over n. Something log to a small power, that's reasonable running time for parallel algorithm. The work, um if you use the simple prefix sum, goes up to n log n, uh which you may want to use uh for some simple algorithms like this.

7:40 Uh but of course, we can bring it down using the work-efficient one, the one with the blocks. So, we would have n log n for one partitioning step and then n log squared n in total, or n log n actually, if you use the um efficient the work-efficient prefix sum. Okay?

8:11 Very briefly on an and a last detail, the same idea for merge sort. We can easily parallelize the two recursive calls as we did before. They're independent. We have to wait till they both come back for merging, but that's that's fine. So, the the challenge is how can we merge two sorted lists in parallel?

8:32 Uh and this is again um the question is how can we find faces that we can separate out? Now, in in merging, it's a little more tricky. It's it's not as simple as partitioning, uh but again, you can separate into in this in a a constant stage where you try to learn information where you can do this independently, and then a stage where you actually write things in their the appropriate place.

9:00 But this first stage is a little more uh expensive. The key idea is if I have an element in my in one of the two sorted runs, and I want to know where does it go into the merged result? I need to know its rank in the output. How many elements are smaller than this guy in the merged result? And this rank is the sum of two ranks. It's the sum of the ranks in the two runs.

9:31 That's what what this equation is saying. Um and for one of the two runs, we know the rank because it's a sorted list, so the rank is just the position in that array. For the other list, though, we don't know it. So, we have, say, an element in the first run, and we need to know where in the second run does it belong if we were to insert it there. So, how many elements in the second run are smaller than X? We don't know that yet, but well, we can use binary search to find out.

10:04 Uh so, we do a binary search for each element in the other run, and then we know the rank in the output. And then the second step is just put the element where it belongs at the right position. Uh that's that's in a nutshell, that's the idea.

10:21 Parallel mergesort - Analysis

10:23 And I want to leave it at this abstract level. Uh you can spell this out in code similar to quick sort, but I think the the key idea is more important. Um you separate the the stage where you collect information from the stage where you move data, and that allows you to get get some parallelization.

10:43 If you pull this if you put this into practice, um the binary search, I don't think can easily be parallelized. So, for every element, you do one binary search. So, that gives you log n parallel time for this part, for the merging step. Whereas the second part, writing it to the output in the appropriate position, that's constant time. So, in terms of parallel time, we get log n for each merging step, and the depth of the recursion tree again is log n, so we arrive at the same log squared span for sorting. You see a pattern. Uh for work, here it seems we cannot easily do away with this um n log n work. For one merging step, we do these n binary searches, so that's n times log n. Uh and it's not not as easy to get away with that to do away with that. Uh but we have total work of n log squared instead of n log n, that's still decent.

11:42 Uh and something along these lines is indeed used in in the libraries. I think that's um briefly mentioned at the end. Uh reducing the work in merge is possible, but uh I'll leave out these details, and I've never asked about those in the exam. And these are just vague ideas. Um it needs it needs more details to flush out.

12:11 Parallel sorting - State of the art

12:14 So, let me just um finish with a few remarks. One is an implementation of merge sort similar to what I've shown you is essentially in the Java library and in the C look library for C, for parallel C. So, these are algorithms that work well in practice, uh even though they're in the PRAM world, in the theoretical world, not the last word. There's slightly There's improvements on those. Uh but these improvements come at a complicated more complicated algorithm. So, it it seems that for reasonably sized inputs, they're not worthwhile doing. Uh whereas the algorithms that I explained to you, they're a big step uh of improving the sequential ones.

12:59 Um I do want to point out though on in theory, if you work on the on this CRCW RAM CRCW PRAM model, this the P somehow got lost. Uh then there are better methods. You can be work efficient and have logarithmic span. The algorithms are quite interesting and complicated, and probably not much practical, but it's a a theoretical achievement. And uh a ver- a version of merge sort gets you there, but it's quite complicated. So, we won't talk about it, but I think you should know that this is not the end of the story.

13:38 Um uh remember all we talked about here was span and work. You have to see how this translates into time if you have a fixed number of processors. And so, the difference between log squared span and logs log n span might not be so easy to see. You need quite a few processors. All right, we talked about the practical challenges already. Um I think that's that's enough for now. That's the end of the sorting unit, and we leave the realm of parallel programming for a moment again.