Video 7-4: §7.3 Parallel primitives, prefix sum, compaction

0:00 Introduction to prefix sums

0:04 in the next subsection we'll look at some little primitive building blocks for pel algorithms that uh turn out useful in in a variety of applications and we will use them for parallel sorting but they are more General than that indeed and uh

0:21 so by themselves the problems that we'll see on the next few slides might look a bit uh uninteresting or esoteric but uh bear with me for a bit uh we'll come back to them and they naturally fit into the problems that we will identify for parallelizing sorting

0:46 methods the first of these problems is called the prefix sum problem and so uh it's a very simple problem uh you're given a list of numbers or an array of numbers and you're supposed to uh find all the prefix sums well that's uh just using the name again summing up the first I elements for every I and it's okay if we do this in place so you could think of it as we start with this array and we want to end up with that array where the idea is that every entry here contains now the sum of the entries up to this point including that point so um the last entry will always contain the sum of the entire array the first entry will always just be the first entry from before if we have zeros in the array before then we'll have a a run of the same entry right so that's some some simple observations about this about this problem again forget about for the moment why this is an interesting problem just uh assume we want to solve it what can we do to solve it before we start with parallel algorithms let's see what is the Baseline that we compete against what's the best sequential

2:00 Sequential baseline analysis

2:23 method and I'm not asking about a complicated algorithm essentially the the simple straightforward solution uh gives you the running time I'm after let's wait for at least 60 maybe vs are trickling

3:35 oh wow it jumped okay there you go uh we had votes for various options you can actually do this pretty fast um so uh you can do it in linear time which means that's the time to just read the entire array okay how how do you do this uh here's the code is is a very short code the main trick is just um if you if you want to find the sum up to including the I element if you already have the sum up to including the one before then there's only one more element that you need to add in so sequentially you can do it like this um you you iterate over I and then you just do one summation in each step you start with the just the first two elements and you add one more into the sum of the first two that gives you the sum of the first three and so on and so forth so we we can do it with n minus one additions and linear time overall of course the problem is that that's maximally data dependent I always need for the next for the next uh step in the computation I need the result of what I've just done that's the antithesis of parallelization so that

4:57 won't work uh but we can still take this algorithm as inspiration and um it's in it's insightful and uh just gives the easier to draw pictures if we focus on a sub problem namely summing up the array now that sounds like we're reaching problems that are so simple there's what can you really do interesting with just summing and numbers now if you look at this from the perspective of what what additions are done if you need to sum n numbers up and all you can do is add two numbers at a time you will always need n minus one additions No Way Around It each step takes one number away uh but of course you can choose which numbers you add up and in what order and uh this happens to be a binary tree because it's a binary iteration a binary operation and you have two things that you add up so the sequential algorithm corresponds to this kind of tree we start with the the first two and then we add in the third and so on uh yeah forgive me that I didn't start with zero I offending myself here with uh not being consistent uh but yeah imagine there's there's a zero that's a one so uh that that aside uh that

5:01 Parallel tree approach

6:22 tree is useful for this algorithm but it has this maximal height right we've seen the same kind of tree as the worst case for binary search trees of course I can do better if I want to minimize the height I can use a more balanced tree and now instead of 1 2 3 4 five six seven steps that all have to wait for the previous one I just have three height three uh so can we somehow uh use that also for the prefix some problem it also seems if you want to compute the sum of n numbers in that way there's no way to get below the height of such a tree at least unless you can do something else then adding two numbers at a time that's the best you can do well but for for the simple problem of just summing things up uh you can also write this as a proper algorithm that operates on the tree level by level up so it first executes all those additions then those then those so the parallel time the span of that algorithm will be the height of the

7:12 Implementing parallel prefix

7:37 tree and you can do the exact same thing for the prefix sum Problem by just doing all the trees in parallel that sounds wilder than it is um but it actually has a nice nice regular structure so what we'll do is we do the the lowest level of the trees and if you look at what the lowest levels do they just add up consecutive elements so the first step adds up consecutive elements so every element now contains the sum of itself and its left Neighbor In The Next Step you do roughly the same but you jump by two so this guy for example now contains the sum of these two and each of these remember was the sum of of the two neighbors here so it turns out that this now contains the sum of these last four elements and the same thing is true for all of the others with a few boundary uh conditions at the beginning but every element now contains the sum of the ele four elements before it and guess what we just keep going like this by doubling how far we jump back so uh here we jump back four positions and then we have summed up eight elements and if we do if we do this here we need one more round and and

8:59 now each of these elements in the in the last round after the last round essentially contains a full binary tree of everything to the left of it and here's the one example highlighted but it's true for all of those that's what I meant by doing all the binary trees in parallel we're not doing them in parallel in the Primitive way we're not recomputing results that they share we only recompute the results once that's what's meant by this by doing this in these rounds level by level you automatically avoid any redundant computation okay I think in the um at the level of these pictures the algorithm is is fairly straightforward to understand and it's quite clear why it works because every element exactly shows you what it has summed up uh in code it's a little it's a little more annoying because you have to do the computations of the indices but it's the very same idea so you can do this um I guess that's maybe um it doesn't give this nice animation or this nice picture but to do this step I only need the previous round step so I can each time overwrite the array that I'm using I don't need to keep the old results around the old rounds can be overwritten uh that's uh that's that

10:27 remark and and uh here comes for the first time a property of the model of the pram model that is uh somewhere between a bit idealistic or convenient or an idiosyn chrity of the of the of the theory call it what you want um that's a part that's not so realistic so if you wanted to implement this you would have to do that explicitly um but because we're we're working on the pram everything Works in loog Step so when I do one round of writing to to the array and then the next round reads elements I can rely on all the rights going through before any of the reads start everything's nicely ordered I do one step after the other that's the part um where on on

10:29 PRAM model and complexity

11:22 current architectures you would have to um explicitly synchronize the different threats if you if you program with threats in a programming language they run at different speeds at different times the operating system is even free to schedule them like pause any one of them for an indefinite amount of time and then wake it up again so there you would have to explicitly say now we'll wait for everyone to write their their round results and then

12:06 and what we see increasingly is that this kind of abstraction or the synchronization is done in software as part of the programming framework that you're using and so it's it's getting less and less of a problem uh but the hardware essentially uh doesn't support it in exactly that way anyways here's the code um it's the same as before it's just doing this with proper in index arithmetic nothing complicated going on other than that the overall number of rounds is well the depth of such a binary tree so it shouldn't surprise you that there's a logarithm involved and it turns out to be just log base two round it up is enough then you compute the step size that doubles in each step um and here is what we actually do in parallel so the rounds are sequential I have to do one round after the other uh but in each round across the array I can work in parallel and what I do in parallel is just a single addition and then I write it back so note that I've split this operation into two time steps here and that's um uh depends a bit how how your pseudo code is defined but this makes it explicit that we first read the old results compute the new results and then

13:25 in the second step we write the result back to the array that's my way of making this a bit more explicit you could you could U maybe you're tempted to write this in one line but you have to keep in mind that it's actually several steps on any hardware that we that I know of okay otherwise simple code um and this would run reasonably fast so how fast

13:51 Evaluating work efficiency

13:57 exactly in in one round all these additions here it's constant time because I'm just doing a bunch of additions and reads and writes and I do all of this in parallels so uh in terms of span this entire Loop is constant time constant

14:18 span and uh constant times the number of rounds gives you the overall span we have logarithmic number of rounds so that's a log and span overall uh that turns out to be best possible in a in depending on the model but uh uh if you have to sum up n numbers and all you can do is these binary additions that's the tree argument again even if just your task is to compute the sum of the numbers you can't really be better than that unless your model allows allows weird operations but let's look at the work as well the analysis here is is essentially the same you have constant for each inner loop iteration but for work analysis for work is essentially ignoring all in Parallels for these Loops at least that's exactly what happens instead of doing them in parallel we have to sum them up so this was order one work but order n uh sorry order one span but order one order n work for each of these uh rounds and uh we have logarithmic be many rounds so the overall work is order n Logan huh remember we said we can do prefix sums sequentially in linear time so our algorithm is not work efficient it is still a good algorithm because it's low overhead it's just a

15:47 logarithmic Factor worse in work so it might even for a relatively decent number reasonable number of processors give you a speed up but at least theoretically we can uh we can ask whether we can do better so it's is overall good we get a speed up um but the question is can we do even better so there's uh again a more tricky algorithm that I'm not going to show where you can do with a twice the span doubling the span you can get linear work uh I instead want to show you something that has two benefits I mean it's it's a tiny bit slower it's three times instead of two times but we we ignore constants in in much of this module anyways uh the good thing is it's a bit simpler and it's more versatile but because again it uses uh a blocking trick that is more versatile than this concrete problem it can be applied in other scenarios as well so let's have a look at that um

16:56 Work-efficient blocking

17:08 the idea is to use what we already know um which is an algorithm that has good span but slightly too much work so we want to make use of that algorithm but apply it to slightly smaller instances and do that in parallel that's always the idea of this blocking try to break things down into slightly smaller sub problems so that you can use the slightly slower algorithm but do that in parallel so that it overall doesn't hurt now if you just do that and keep repeating the same work you're not saving the work so you have to do a slightly bit uh slightly smarter thing than that and that's the problem specific part so [Music] um maybe let me do the example first

18:01 and so I'll I'll have to draw that but um uh let's do a simple example where our array is just all ones now I'll have to draw this a bit a bit nice so it doesn't get too messy it's not my

18:20 strength so suppose we have an array of length 12 and we'll break it into blocks of size uh four that number is is basically given in the algorithm so um in our example we have

18:41 12 and now we're using blocks of size log n so we Bunch login elements together and here that works out to four oh that's B so I'm I'm breaking the array why do I use just ones well if I'm if I'm Computing the prefix sum what's the prefix sum of an array that is one in every position it's just the first n integers so it's uh it's nice to check that the example worked out correctly that's uh that's why uh but other than that it's it's General if it works for these numbers it basically works for any other numbers in the same way okay so we broke the problem into blocks um then for each of the blocks in parallel we compute the local prefix sums just in the tiny block and for that we use the algorithm we already know so let's uh let's do that first on the example so I take this as small independent arrays all filled with ones if I compute the prefix sums that's just 1 2 3 four in all of

20:03 now maybe it's it's good to already note how much time this takes and we'll have to analyze work and span separately so we use our um so we use uh sorry we use the fast sequential algorithm for this not the parallel one at this point we use the fast sequential algorithm but do it in parallel for all the

20:28 blocks and the sequential algorithm had linear time so each of these takes order B time uh and of course that's the total span as well for the entire round because it's run in parallel but we do n ided btimes that in

20:53 work because we have to uh sum for work we have to sum up over all the blocks all right so far so good now we use the work inefficient algorithm that we've had before but not on the entire input only on the rightmost elements from each block so I look at this at this uh subarray and um I'll I'll draw it in the example just as a as a really fat array with only three entries but you should think of this only containing that last entry of uh of the small arrays and I compute the prefix sum of that so four four and four becomes 4 8 and

21:50 12 so previously was four four four and now it's uh it's summed up to that so how much how much time does that take I'm using the the parallel but uh work inefficient algorithm for

22:08 it the size of this array is n / B because that's the number of blocks that I have and remember the work inefficient algorithm had log and span but and login work not the linear time linear

22:33 work so we have log n Prime span and N Prime log n Prime work now if you insert what we know about b b is log n so I could have maybe simplified this here earlier if we have n divided B * B that's of course just

23:13 n if I have log of n Prime if I insert what I know about n Prime n divided log n that's log n minus log log n so that's a lower order term the asmic cost here is the same as log n

23:34 span not spam and the interesting thing happens here if I insert n divided log n here what I get is that the log just cancels n ided log n Times log and here again I have technically log divided log n but this this divided log n just becomes a minus log log n that's lower the term that is that is dominated by the rest or you can upper bound it by the rest and what's left is a log n down here and a log n up here that we can cancel so that turns out to be just order

24:17 n and that's where the magic happened we took a work inefficient algorithm but we applied it to a slightly smaller problem so that the overall work that it does is small enough that's what the parameter Choice come comes from the way I presented this is basically I showed you the final result and said haha this fell from the sky and that's how how you do it but uh the way you should approach is if you do it to a new problem is you work backwards you have an algorithm that doesn't quite get the work right so you can compute how much you have to thin out the problem so that the work is is what you want and here it's a log factor that you have to lose okay we're still not done with the overall problem we've just computed these these intermediate

25:08 steps so what you do in the last part um is you uh add to each block the prefix sum of the rightmost elements and that gives you you can do this again uh you do it in parallel for each block but you can do it sequentially within a block so you take this number and add it to the orange

25:41 number so here you take that number and you add the orange numbers in the first block you don't don't really do these and then you get get the final prefix sum from before so why is this correct these are the prefix sums within the block all that's missing to the overall prefix sums is the sum of all the elements before it and that's that's that green entry because it was the sum of this block and the sum of this block and the prefix sum of that these layers of prefix sums on top of each

26:25 other so how much time do we need for that um we again this sequentially and we need order B for each block the the length of the block we just do B additions so the span is order B and the work is by the same calculation as here is linear so if we sum this all up what do we have for span we have order B which is order log n remember and and we have login and we have login so the span is

27:10 login and what do we have for work sum that up to so we have order n we have order n we have order n so linear linear work uh that's that's spelled out here in a bit nicer as well but I thought it's nicer just to do it on the example so overall we found now uh an algorithm that has the same span as what we had before up to constant factors but we reduced the work to order n and that's the best sequential algorithm because we have to read the array so we found a work efficient algorithm now as well and funnily it uses both of the previously best algorithms but combines them in a smart way so that it's better than either of those in isolation right the algorithm both uses the fast sequential algorithm and the previously fast but not work efficient parallel algorithm but by combining them with blocks of the right size you get the get the oval Improvement when whenever I uh whenever I present this I feel it's kind of it's kind of surprising how this works you can take two things that are not optimal and you combine them and the result is better than either of

27:44 Refining algorithmic performance

28:28 them but uh yeah the the clever choice of this of the size of the block is is what makes this happen there's one one more uh such parallel primitive that we look at but that will be much shorter because it's essentially the prefix sums in Disguise but it's it's one more step um towards what we'll need for sorting so uh the problem here is called compacting and an array and it has two inputs has one array of of objects and it has a bit Vector that tells you which of the elements you want to keep all the ones with a one and you're supposed to create an output that consists of just the elements that have a one on top but compacted in an array at consecutive

28:54 Compacting and final analysis

29:26 positions now luckily you don't have to work very hard you can reuse prefix sums and the the clever way of assigning things in in on the pram to solve this with very little code uh the the way this works is you first call prefix sum on the bit Vector so here I'm I'm making a copy of the bit Vector first because we need it later and remember prefix sums overwrite their input but essentially we compute the prefix sums of the bit vectors now what does that do it means for example the seven here has an entry above it that's a one and if I sum up everything that's up to this point that's three and that's exactly the position in the output array where it should go so once I've computed the prefix sums I can use these entries above the elements to know where they should be written to and so I can do the second part in parallel for each element in a I either do nothing namely if there's a zero above that element uh or I take it and write it to the output to the position that's given by this C by the prefix sum of all the bit vectors and that's how I can do compacting so I'm spending constant

30:51 effort in each of these inner iterations because these are all done in parallel it's constant span and linear work that gets too small I guess I try to make it B

31:20 bigger and what we have to add is the cost for the prefix sum work that's the final test if you uh kept everything in in your mind kept everything in

32:04 um I guess I'll show you the code the key piece of information is on the slide before okay there we go it's a good spread right H but the majority is

33:37 right so to finish off my analysis um I almost gave it away already what we've just seen about the parallel prefix sum here it is we can do it in log and span and uh linear work

34:01 now the span is of this overall thing is dominated by the prefix sum the rest that comes afterward is essentially nothing just a constant span um and the work is is linear in both parts so it remains uh Big O of

34:19 n so that's the right answer at least if we use the the fancy uh sub prefix sum algorithm