Video 5-3: §5.3 Parallel primitives, prefix sum, compaction

0:00 Introduction to primitives

0:02 in the next subsection I want to show you some Primitives that will be part of of bigger parallel algorithms in particular uh for for parallel sorting but which also show um that you have you have to learn some new building blocks for for these kinds of parallel algorithms

0:27 we'll we'll see that uh most problems are not embarrassingly paralleled but they contain some parts that are almost embarrassingly parallel so many many problems have this this double nature there's there's parts that are easy to parallelize but then there's other bits where they seem to build on previous results all the time and so you need you need tricks to get these these steps uh done efficiently and still make use of the parallelizable part I know that's that's so big that it's um close to useless maybe it'll make sense after you've seen the examples uh there it turns out that luckily in a way there are some building blocks that are useful many many times and we'll we'll study some of those the first of these building blocks is called the the prefix sum problem and it's formulated in an abstract way so that it is useful and applicable to different scenarios it may look a little unmotivated at this point but bear with me you'll you'll see on Monday what it's good for the input is an array of numbers as so many times in in this module the goal is to modify this array so you're allowed to this in place um to modify the array so that afterwards it contains the prefix sums which

1:12 The prefix sum problem

1:53 means at position I you're supposed to have the sum of the first of the elements up to and including position I which are I plus one numbers I guess so here's an example here's the input here's the output note that so we always have um the first two entries are the same if there's zeros that we means that means some things stay constant in the other array and an entry up to here so it just sums up all the numbers up there and uh that matches it sums up to 15. I guess the definition of the problem is is easy enough now again bear with me for the for why this is a useful problem

2:45 without telling you much let's have a see let's have a vote on what you think is possible for this and now first just sequential right so you um I'll maybe show the problem again you're supposed to do this just sequentially standard algorithm coded in Python whatever you want how fast can you do it

3:50 in a way there's no wrong answer to this question or maybe there are some wrong answers if it's impossible but if you if you vote something if you vote the the highest number and Cubed is never wrong right because you can't do it in that as an upper bound but maybe that's not the most interesting algorithm then

4:26 34. do we get some more 35 I should have split this up and uh now first show you the code and then have you vote again in the interest of time let's not do this though um the the answers are very mixed if you went for the say two went for the safe option of n cubed uh I guarantee you it's doable in N Cube time a big O of n cubes the safe bet anyways um yeah if you can do it in login time please find me for the thesis later uh sequential time right um oh sorry I'm I'm not supposed to uh to Mock You much for this um so linear time is what we can do uh sequentially I think this is this is inevitable because you need to read the array to produce the result if you think about just the last last entry how are you supposed to do the sum of the entire array right the last entry is the sum of all the numbers how are you supposed to get that sum without inspecting every position in the array I think this is not possible in the worst case

6:02 um how can you do it in linear time though uh here's the code is very nice and slick and simple oh you don't see it I forgot to switch back

6:17 there we go so I was I was waving around on this Slide the last entry in the array is the sum of all numbers and you need linear time to find that and here's the code for the dramatic effect it's just two lines really uh the the trick is you compute the sums from left to right and then you all you use that the next term is always the previous sum plus one more element that's how you can compute all those sums even though if you wanted to do those we'll come to that if you do it in parallel if you wanted to jump right in the middle and compute one of the sums taken out in isolation you always need linear time in distance to the beginning but if you do it sequentially you can build on the previous result that's great um it's it's actually very very cheap you do the number of additions that would be needed for just Computing the last entry in the array the total sum but along the way you get for free all the other partial sums it's just convenient that you can leave them in the array now the big problem for parallelizing this of course is that's maximal data dependency every operation every iteration of this Loop uses what was

7:28 Parallelizing prefix sums

7:39 just computed in the iteration before so that's not gonna work for parallel not if you want to get the parallel time down and to um to focus our mind let's reduce the problem even further for a moment to just Computing the sum of the array right so this algorithm uh does this in one particular order and that's depicted in this tree you have n inputs and numbers that you want to sum up and what we have is a binary addition operation that can take two numbers and compute its sum so you inevitably have to do n minus one additions because uh it's a binary tree there's no way to get by with fewer internal nodes but what you can do is look at a different binary tree that's the binary tree that belongs to this code you always computed the the previous sum and then add one more element to it you don't have to do this tree you can do a balance tree instead and now if you compute this bottom up you notice that a lot of things the way the tree is already drawn shows this a lot of things can be done in parallel without data dependencies I can add these two and I can add these two they don't interfere each other

9:08 so I can do level by level bottom up this is the first time step that's the second time step and then there's one last time step and you see it gets less and less busy so here four PES were busy here just two and then just one but we reduced the height of the tree here the height was uh was it seven and here's just it's just uh three okay

9:44 cool so we want to do that um and the only bit that's left is to do this not just for the sum of all numbers but all the prefix sums as well it turns out that you can do this with a simple um a simple trick you you basically simulate this algorithm for all the prefixes all at the same time and you can reuse some of the partial examples so I'll show you how this works on an example and then we'll have some code after that here's your input in round one you take adjacent Pairs and add them up

10:28 so this this new cell is filled with these two and there are some and you do this for all uh the entries note that the sums are overlapping and all that will will come to it I want to point out that this at this after this first round already uh the first entry is final well it was ready right from the beginning and the second entry is final it contains its prefix sum but all the others aren't in the next round we'll do something similar but this time we take the element that's above us and two steps back and maybe you can just by pattern matching guess what how this might continue you double the distance you jump jump back in each step so here we went back one cell minus one I guess

11:22 here we went back two cells four cells hard to draw and and eight cells uh uh whatever um the gray errors arrows are right and whatever I'm drawing may or may not be if you pick out any specific element you can see the binary tree that we've had for just the sum embedded in this there's uh

11:59 Maybe thicker so we have these two and then the trick is that the final sum consists of two sub trees Each of which consists of further two sub trees and what we'll have to see is that eventually everything's covered uh sorry I'm just blindly continuing here not what I wanted this one and this one

12:40 now I will color in all the top rows one day apart from the last one let's make that a bit more economically okay I'm totally messing up the picture uh but maybe you can see the binary tree a little nicer now and I forgot one

12:59 no no sorry Ah that's the only one uh that shouldn't be in there yeah that's subtle it's not a complete binary tree that's why I picked the second to last there's one one dangling Leaf left here what you can see just visually is that all the elements are in there and it's it's the same binary tree that we've seen before all right but doing it this way you get all the binary trees at the same time

13:25 Analysis of parallel efficiency

13:28 writing this in code is not too hard it's just a little messy because you have to keep track of the indices uh but that's what it's like what it looks like

13:42 we'll do the rounds these are round one and so on that's the height of the tree uh the rounds go from one up to log n rounded up step is how much do I jump back for my single Edition that's powers of two as hopefully you've noticed that pattern here as a computer scientist and so that's that's the the step size and then the parallel part is just this inner loop in each in each round we do for each of the positions in the array so in round two for each of the positions that are not final that's why this starts not at zero you compute first the new sum the pre the value that's above you and the one a little further to the left you compute that sum and then you store it now I might have written these two lines in one line right it's it's doing the same thing now I split it up in this case to point out a subtlety here which uh the pram model is essentially fine doing it that way but you have to be careful if you implement this on our on real problem software or programming languages with with parallel support we have to make sure that all these reads in that line from all the

15:05 processing elements are done before any of the processing elements start writing back their results because otherwise you would read the new value and they uh they would get out of sync you have to make sure that all the reads in round I are done before all the rights in round I and then you can continue with the next round is it clear why

15:33 otherwise you um you might end up having some numbers some more than once because one processing element ran ahead and already did a bunch of additions now you grab this and pretend it's the old value but then you add things several times so that's one of the things that are easy to write as a pram algorithm but need explicit synchronization if you do this in in most implementations synchronization is implicit for us which makes the code clean um but I wanted to point this out here

16:14 okay we still have to analyze how fast that is remember we had sequential time linear that's the goal for um for the work now I know the answers are here but let's um let's go slowly over this and I have two colors because we want both work and time

16:38 so let's first be in time mode so the green one we run the overall the the outer loop is not parallelized so we have to do this sequentially so we have uh login times this this inner loop now um

17:08 but then we have a for Loop that's parallelized so for the time we can ignore this we just look at how long each body takes and that's again constant time

17:23 it's just two operations each or a bunch of reads an addition and a right so what does that mean for the overall loop it's log n times constant so we have log n overall

17:38 that's the time okay it will turn out that this is basically best possible for this problem at least um or for the sum of the parallel models if we look at work

17:58 the only difference so this is the same this is the same the difference is that this Loop now is done all the different pre-ease we sum that up so we have to sum up this and I'll be generous and say this is order n some iterations later are cheaper but um uh let's let's just do do a generous upper bound which turns out to be um a sharp Theta bound

18:30 so you have linear in each iteration an overall n log n okay you could write this here more specifically by subtracting the step and then write it as a sum and you'll come to the same overall Theta conclusion

18:49 so we have n log n work but the sequential algorithm that we've seen before was linear so it's not quite work efficient yet it's a it's a bit worse but hey it's not not that bad either right it's uh it's a lock Factor overhead so um unless you have really few processing elements maybe that algorithm is still still a substantial Improvement because the sequential time is really fast it goes from linear to log

19:25 uh the the best possible here comes in a way from just looking at the sun if you look at the simpler problem of just summing Up N numbers as long as all you can do is take two numbers and add them up you have to spend a login logger you have to spend a linear number of additions and you can you can work out that it's not possible to interleave them better the binary tree has to have login height

20:02 in a way this is not atypical we often have a certain trade-off we can get a bit more parallelism but then uh blow up the work we've seen that as an extreme case for our first string matching algorithms now sometimes though you can actually get the Best of Both Worlds by just thinking a little harder uh in this case you can you there's two ways how you can make our parallels prefix sums work efficient and keep the parallel time you can do it with doubling the parallel time which is a little more in involved so I'm I'm not doing that I'll show you something that effectively triples the uh triples the the parallel time but brings the work down so in in Theta world where we ignore the constant factors we keep the time but bring the work down to linear

20:59 Work-efficient parallelization

21:02 let's see how that works and that's again before we dive into the details I know it's a wall of text uh it should have split that up uh the the key thing is that this is a template that works more generally if you have an algorithm that's good in terms of parallel time but not work efficient try to find a way to break the problem into blocks where you can use an efficient sequential algorithm on small pieces and then on the aggregate results use your work inefficient parallel algorithm if you can reduce the size of the problem enough so that this work inefficiency doesn't carry through and the blocks are small enough for the sequential algorithm to still be fast you can improve overall uh again [Music] um as always I'm not sure if it's useful to First give the general template and then the example or the other way around you usually understand things the other way around but I think warning you up front about what's to come is helpful you'll be my judge uh here's how we do it in this case we choose a block size of roughly log n so this this will just be um sub segments of the array of login elements

22:25 we break the uh conceptually break the element into blocks no uh no sawing needed and then in parallel we compute the prefix sums on just the little pieces foreign use the sequential algorithm and then we'll use the sums of these in the work inefficient parallel prefix sum and let me show you um an example for that

22:59 at least um like not not a fully worked one but a conceptual one I think that makes makes it a bit clearer so we start with um 12 elements in our array and suppose the block size is four which it is if you take the log of 12. I didn't just make that up good so we'll have three blocks right if they're four elements each

23:44 I'm just trying to draw the array with cells we don't really care about the numbers in there that's why I said it's not a concrete work example we're just summing numbers up you can you can sum numbers uh we don't need to do that in detail so this is index 0 then 4 and then eight

24:06 right so let's look at the different steps the first one is this local computation where we keep local to the blocks so we have conceptually broken the array into three pieces containing the same numbers and

24:29 you know what let's make it a concrete example but a boring trivial one let's just say it's filled with ones it's easy to keep track of the sum then

24:47 but it's a little little less opaque the local prefix sums they just compute the prefix sums in this in this block using the sequential algorithm so I will fill this all with one two three four

25:15 the last element of each block namely these guys the rightmost element and compute the prefix sums for those using the new algorithm the one with the fancy binary trees embedded so we take this one this one and this one and uh well I guess pretend there's a huge array with

25:40 just the the force in there and compute the prefix sums of these so that will give us that's before and then after you get this okay that used up much of the slides space we'll see

26:04 and then we come back to the blocks and and add the the global prefix before that block to all the values within the block so what that's supposed to mean is we copy our orange part

26:34 okay I went too far with this one let's um make this a bit smaller this step says to all elements in here add the four to all elements in this block add the eight

26:54 I can do this in parallel over the blocks so what I'll get is these stay the same then these get to 5 6 7 8 and these get to 9 10 11 and 12. that's the 12.

27:13 okay which is the correct prefix sum obvious to check in this case because we started with all ones if you sum up as many ones as you have then it should be the just the numbers 1 through 12. that was the last step so that correctly computes the prefix sums at least it worked in this example now let's let's see uh what the time and span for this and work for this is [Music] um

27:54 time here and work there then I can keep using my colors for the different phases how much time do I need inside each block with a sequential algorithm well how long is a block it's B long so for the orange part I need Theta B time which is log n

28:20 then I have the blue part which uses the fast sequential sorry the fast parallel prefix some algorithm that we've just discussed and its time was log n but I'm using it on N Prime which is not n but n divided the block size

28:47 rounded up so in terms of theta it's n divided B and that again is undivided login um should I do the computation if you take uh sorry this is a log n Prime I didn't write this that's the size of the input but the time for the blue part is log n Prime if you insert this definition of n Prime into n into log n Prime then you get log n minus log log n that's the same as Theta login

29:44 and finally the green part that's a bunch of additions again each processing element deals with one block so it's only linear in the size of the block again so the overall time if you sum this up is something like three times the previous time

30:07 and well I don't have to copy this so this is um summarized here again I think the explanation is is better explained step by step so the time is in terms of theta is still the same log n as we had it before let's look at the work because the work was where we weren't happy previously so work for the orange part we're using the efficient sequential algorithm and it's a effectively the same as the Span in this time every little piece just executes on its block so that's log n in terms of the work uh sorry that's per block

30:55 and we have n over B blocks so that's linear work overall for the orange part the local sums well the blue part we're using the work inefficient algorithm from before so the work there was n Prime Times log n Prime

31:24 if we insert what our n Prime is we see that this nicely cancels so it's n divided log n Times log n Prime which we've already seen is log n minus this small term so that cancels and becomes also Theta of n so we've reduced the work by making the problem a little smaller we reduced it by a log Factor that was enough to bring the work to linear and then the green part is as before we use n over B blocks and each block costs us B so that's linear again so the overall work is is linear for all steps and that's work efficient because we know that's the best sequential algorithm okay

32:21 so that's probably the most involved algorithm we'll discuss in this in this section uh it's more involved because it builds on other things right it uses previous algorithms as a black box the nice thing about this though is you get an overall much faster algorithm without thinking too hard you're just putting pieces together in a clever way and that's much of the beauty in algorithms and data structures almost all the time you do just this you take pieces and put them together in a in a more clever slightly more creative way and that that gives you a better result at the end the the magic or the the skill is to know good pieces to put together and to see how they fit which is sometimes incredibly hard uh even with it with a lot of practice you sometimes don't see it as someone else does uh but practice does help a bit

33:25 Compacting subsequences

33:30 I have one last ingredient for this uh for this building block section and that's that's this problem which again uh sounds maybe a bit esoteric at first but this will literally be used in the Sorting part then

33:47 suppose we have an array of numbers we always have arrays of numbers but we have a second array that tells us some of the elements are not interesting I'm only interested in the elements that have a one and the ones with a zero I'd like to not have there so I'd like to copy out only the elements that have a one above them we call that compacting a subsequence from an array so you have a subsequence is a selection of the indices so it's not a contiguous part but could be spread out as you want but subsequence means we want to keep the order as they appear in the original array now again doing this sequentially is very easy right you go left to right you keep a pointer to the next cell that's free if you see zeros you skip it if you see a one you copy it out and move one cell further easy peasy sequentially how do you do this in parallel it's not so clear at first because it seems that say this four where this goes in the output seems to depend on what happened before in the sequential algorithm but if you think about it for a moment uh this is really just reusing what we've just done

35:04 you can use prefix sums on this bit Vector B to figure out where the elements should go precisely for this four say if we check where it comes from the position in the array is essentially the number of ones in B to the left of that point so we would like to sum up the number of ones here if we sum that up as five and four is The Fifth Element so apart from the plus minus one because we start indices with zero that's the answer

35:44 so you can you can put this into code by this little algorithm you have this B given as an array we copy that out because we need B and we need to mess with it so we copy it into C and compute the parallel prefix sums there we're using one of the lovely algorithms you've just learned and then we can do the following in parallel if our processing element has one of those positions assigned that has a one then it gets active otherwise it sleeps and what does it do it copies its element a of J into wherever C of J says it should go minus one for you know the off by one we start indices at zero okay

36:32 so the trick here is this we know how to do properly in parallel and we can use that to pre-compute where the elements should go and then we do the actual data movement in the second step in the second phase that way we have decoupled the the computation like the the previous the sequential algorithm would go through this step by step and have this data dependency the place where the element goes depends on the past we have decoupled this by first Computing with where everyone goes and then moving them there in just one step across parallel across all the processing elements

37:21 so let's see if you digested that part how fast can we do this compacting it's also interesting that it doesn't depend on how many elements you copy out it's kind of um Irrelevant for the time and work in this case

38:39 probably have to cut cut it here and reveal the answers here though maybe it didn't have a chance to vote but most of you got this right so maybe this is a easy enough the answer is is login time and and linear work and the reason for that is look at this algorithm and analyze it it basically does the prefix sum and not much else around it what comes afterwards in terms of time is a constant step and linear work because we spread it across all the PES but both is dominated by the computation of the parallel prefix sums