Video 3-9: §3.8 Parallel primitives, prefix sum

0:00 <Untitled Chapter 1>

0:03 okay in the next subsection i want to talk about some little algorithms that will be building blocks towards our bigger goal for um or parallel sorting and so we've seen we've seen the parallel models now let's see what we can do with those

0:23 and the first little building block i want to look at is called the prefix sums so it's a it's a very simple problem but it turns out to be quite versatile in using in other parallel programs the problem is as follows you're given an array of numbers just n numbers stored in an array and you're supposed to compute the prefix sums which is just the sum of the first i entries and we want to do this in place so we have the array a before and then we change the array and overwrite the elements with the prefix sums where at this position we sum up up to well all the all pre numbers up to this position including that position okay it's an abstract little problem you'll see in a few minutes why this is useful but for now is the abstract problem clear as as this so every cell just contains the sum of all the numbers up to this point and if there's zeros for example here you get repetitions also this will never go down some simple observations all right let's wake you up again suppose you wanted to solve this uh innocent little problem sequentially

1:37 Clicker Question

1:52 so we don't care about parallel for now but guess what there might be a follow-up question okay seems to go quick few more seconds three two one locked a wide range of of different answers

2:56 and the majority is right though or the largest vote was right so sequentially we can easily do this um in in linear time and i'll show you how uh if you can do one of the the faster ones i'd love to learn

3:16 Prefix sums - Sequential

3:22 um so the sequential solution could be as follows it's it's maybe just it's so small that's easiest explaining code uh you just iterate through the array and you compute the next prefix sum by taking the previous prefix sum and add one new element so you start computing on the left left element is its own prefix sum so you're done go one step to the next to the right take that element and add the last prefix sum that makes the new prefix sum and as you keep going you notice if you fill the array from left to right with the prefix sums all you really have to do each and each step is add one more element easy

4:01 that's a nice little code if you want to do it sequentially that's fine the problem is you can't really parallelize this one and the reason is that there are data dependencies between the different steps each step depends on the computation that has been done in just the step before so you can't really pull this one forward you have to wait till the previous step has done its work is that is that problem clear the data dependency trickles all the way through and that prevents us from from speeding this code up by parallel processing so we need a different approach and luckily there is one

4:43 and let's simplify the problem a little bit just to see clear instead of really doing all the prefix sums suppose we're just interested in the last entry the sum of the entire array this is definitely solved by the prefix sum problem because we can just take the last entry but this is a little cleaner to draw

5:05 so if you think about this for a few minutes you want to compute the sum of n numbers and each step can only take two numbers and add them there's no way you can get away with less than n minus one additions in a sense what you're building is a binary tree you start at the leaves with the original numbers and then every node can take two things two subtrees and add them and no matter how you do this you will always need the same number n minus one nodes if you want to prove this there's a nice little proof where you say every node has two uh slots for children and one new slot is added so whenever you add a new node you take one slot away and that's it so you need n minus one slots away steps before you add one but uh we're not forced to use this shape of a binary tree here we can use a different one for example the one below or the balanced one and in terms of data dependencies we want to do this because here the data dependency basically meant following a path this last element was what we wanted the total sum and it depended on this which in turn depended on this dependent on

6:18 double double-blip so we have this long chain of dependencies just in the data how we how we compute and in this tree it's better because the height of this tree is much smaller in the small example not as dramatic but of course your experts now complete binary tree log n height or log n rounded up whereas the other one has linear height so that's a huge difference if n is big so the parallel time here is just the height of the tree it's a little tricky to write down in array index syntax what this tree looks like in code but in essence that's what we want to do to compute the sum faster so if you're just interesting interested in computing the sum of an array what you want to do is simulate this complete binary tree and you can figure out how to do this within the season in uh bit magic taking uh the numbers the indices as binary numbers for the prefix sum problem we have to work a tiny little harder because we also want all the prefix sums all the other partial sums so what we'll do is a generalization of what you've seen for this tree so this is maybe the first like um detailed algorithm so everyone wake up

7:21 Parallel prefix sums New Compute all prefix sumns with balanced trees in parallel Remember partial results for reuse

7:40 we do this in steps here's the input array in the first round every processing element takes its own value and adds the one that is one to the left except for the first point where there's no one to the left so if you if you trace this up here 5 and 7 is 12 and so on and so forth okay now note that in the first step already by definition this guy was the correct prefix sum so this is already settled right from the start after this first step also the second element now contains the correct prefix sum because it only needed to sum up these two elements okay so we seem to make progress now the question is how do we continue any guesses you don't have printouts of the slides and cheat right you wouldn't or on the laptop

8:40 well it's computer science so it always has to do something with powers of two right so in the next round every processing element adds its previous value which is some partial sum and it goes two steps to the left and this way

8:59 the first four elements are already correct and that's on this small scale example cy if you look at if you look at the eight that one was supposed to sum up the four values in the original array which is this part and the eight summed up this and this entry and they each were the sum of these two and so after the two rounds this position indeed contains the sum of the first four and now you can guess the pattern we keep doubling the distance we go back so if you go to another round we now jump back four positions and so after that a prefix of eight elements counting is hard knows its correct prefix sum that's still not the entire array so we have to do one more step in which case we now go back eight steps okay

10:05 and i highlighted here at the end again uh for one of these elements where its values come from and you see two things first of all if you follow the paths you reach every element in this in its prefix like uh excluding the the last one exactly once there's exactly one path to this element and second that looks a lot like a complete binary tree doesn't it and i mean it is we're just simulating this this idea with computing just the sum but we're doing it not once we're doing it for every position and we interleave the computation so that it's faster in terms of the the parallel time we use the same time we would have used for just computing the sum we're computing all prefix sums along the way

10:55 by nicely interleaving those okay now i've explained this on an example we also want to be able to write pseudocode down for such parallel algorithms and that's something we haven't touched on yet and here's the code for this algorithm that i just described and you see it's one one code and that's around all the processing elements but there's um

11:06 Parallel prefix sums - Code

11:24 well we we don't need the processing element index here explicitly what we assume is that in a way every processing element is sitting at one position in an array but this is not explicit in the code the outer loop is through the rounds and we need log n of these rounds that's the height of the binary tree step is how much do we have to jump to the left um and then here's this loop is just saying exclude some part of the array that's already dealt with that's why we started at step and not at one and the important part of course here is in red this is a loop now that we run in parallel

12:11 so the the idea here is you take the loop body and assign this as a little job to different processing elements and they run the loop bodies step by step line by line if you want in lock step so for each of these values you first do this step compute the sum of your value and the one sewn so many positions back and in the second step you write that value into the array you might be tempted to take these two statements and make them into one because that's what they seem to do right

12:51 because x eventually is written to a of i but this wouldn't work at least unless we define what exactly the execution order is it's important that all the processing elements read the old state of the array first and do the computation based on that and then as the second step they write the new values back to the array otherwise you would get some weird mixture and this is where you see pram algorithms make this easy because there's implicit synchronization if you program this without any synchronization on a threat based language then it would create chaos you get rights that precede other other reads and stuff

13:37 i hope the code is is clear enough up to this point and it follows the example so that's uh that's your first um your first pram code now uh we want to also briefly analyze how good this algorithm is and we have to do two things work and time we ignore the space that's constant in a sense um for time we can just treat this wherever it says do in parallel we ignore that there is even a loop we just count the longest execution so uh i don't know let's do green for span

14:23 so we run the outer loop this is not parallel that's sequential so we run this login times uh but then the rest inside here this is just one step and these two are also just one step

14:45 so all of this has constant span it happens in constant time if you parallelize that's why the span is just logarithmic and let's use this for work so what can we say about the work well for that we basically ignore the in parallel statement and treat it as a sequential algorithm and see how long that would take if we do that we see that this part is indeed constant and this of course too constant time but we repeat this loop roughly n times i mean it's is n minus step but you've seen probably quadratic loops like this before

15:36 so it's at most any iterations of the inner loop and we have the outer loop same as before logarithmic steps so we have log n iterations where each iteration takes linear time so that's n log n that's what we have here on the slides as well

15:59 now this is not work efficient because remember the sequential algorithm took just linear time and now we need n log n time so that's not the ultimate prefix sum algorithm yet

16:20 and in this case we can see it as a trade-off we improve the parallel time but at the expense of more work which might or might not be better in this case we reduced the parallel time from linear to logarithmic so it's probably a good deal even though the work is not optimal so sometimes you have this trade-off that inherently you cannot parallelize things unless you pay extra in work but not for this simple problem here we can actually get linear work if we just pay twice the time so the same theta class but a constant factor difference that algorithm is a little ugly to write down so instead i'll show you a very simple one that uses a much more general technique that will come up in other contexts that achieves the same but uses three times as much span but by and large these constant factors are are not so clear how much they materialize so i'll ignore that part

17:23 Work-efficient parallel prefix sums standard trick to improve work compute small blocks sequentially

17:27 and the way to improve the work is to break things into little blocks at some stage and do these sequentially that's the abstract idea and this breaking small sub problems into blocks that you treat differently that will come up in in different disguises

17:47 so what we'll do here is we use blocks of login elements and then we conceptually break the array into blocks of that size so the first login the next login elements and so on and for each of these blocks we assign one processing element to compute the local prefix sums so these are just inside the block you sum up the well some of the prefixes

18:17 then we use the algorithm we've just developed which is has good span but it's not work efficient but we only use it on a smaller input namely only on the rightmost entries of each block

18:35 that gives us the prefix sums of some positions in the array and in particular the last one is almost the sum of the entire array so we're almost there but we have to fill some of these intermediate steps only have the local prefix sum and so what we have to do is to add the the block offset in a way i think it's worth maybe sketching a brief example on this

19:24 so say we have three blocks and each block has four elements so we have position zero and then four and then eight at the beginning of a block uh and to make things nicely work out let's say n is divisible by the block length so then um we do this first step which is the the block local prefix sums

20:07 okay let me say let me fill in the array with numbers and to make it easier let's say and this is not really readable i'll write the one like this i want an array that contains all ones because then the prefix sums are very simple it's just one two three etc and for illustrating the example that's enough you could substitute other numbers and then the addition is different but the rest is the same i think it's convenient to look at it with just once the first step was inside the blocks compute local prefix sums

20:47 and what this means in the example is just this becomes one two three four that's what i mean by local right these guys they don't know that there's much more coming in front then for the second step

21:11 for the third step second computational step we only use the last element of each block and in a way we we put that into a new array say i want to align it in the picture but really this is this is just one fat array okay with really huge cells i mean and how big is this array uh the length of this one is the original length divided by the block length because we take one element out of each block

21:50 and then this step is computing the prefix sums of this green array remember that's what it says here you take all those and you compute their prefix sums but using the work inefficient algorithm so we'll have to see in the analysis how good that is for the example though it's simple it's just 4 8 12.

22:21 was to add this prefix to add the the offset here to the original array so i'll take a copy of this one and then this last step adds and eight to all of these all right and i made this look like you copied the array you can actually do it in place but uh

23:06 so for the second block we add four to each and then it comes out like this as it's supposed to be and then here as well sorry eight plus one is not eight

23:21 okay i hope the example makes it a little more clear what's happening the idea behind all this is we have a good algorithm it's just not work efficient so we try to avoid calling it on the entire input we just reduce the input by some factor first and we call it on exactly the input of size n divided b and b was log n okay so it's it's a log n factor smaller and that will be just enough so that overall this is um this is work efficient um let me try to speed this up a little bit so the the second and fourth step uh let's first analyze the time ignoring work right

24:09 in this second step we compute sequentially not using parallelism inside on a block of size b so this takes takes b time because we use the sequential algorithm for computing the prefix sums within each block and same in this one that's even easier we just add a number a fixed number to each element in the block that is another time order b

24:46 interesting part for time is uh the the third part even though that's a little confusing maybe the span of this of this step is whatever the span of the prefix sum algorithm is

25:24 and we've seen that this is log n prime the new n that we had before and because i can just upper bound this by n log n prime is

25:37 at most n is actually strictly less but we don't bother so the span of this part is also at most login and so we see all steps take logarithmic parallel time it's the same as before up to a constant factor

26:01 so let's also analyze the work and here we have to pay a little more attention uh what's the work in this case well we spend that's the number of blocks and we spend order b time in each block so that's linear and the same down here that's the number of blocks we spend b time in each block total work in that step is linear and the crucial step for the middle part is

26:38 the work for the prefix sum was was n log n but we use a different n so it's n prime log n prime and if you insert n divided log n the log just cancels and there's a minus log log term well you'll see the same one same computation in the tutorials again

27:03 that happens to be order n as well okay so we have linear work which is the best possible because the sequential one also takes linear time and well to fill end numbers here you have to spend linear time there's no way you can improve on this and we keep the login time you can also argue that log n is the best parallel time so this is this is an optimal algorithm up to constant factors okay and this is a nice general technique that you first have an algorithm that's not completely there yet it's not work efficient but you can bootstrap yourself to a better algorithm by using this one as a black box in on some smaller input this will resurface a little later

27:52 Compacting subsequences

27:53 good deep breath there's one tiny thing i want to add to this before we close that subsection um why do we care about prefix sums at all like other than being a nice toy example there's one concrete thing that we will use in parallel sorting and that's the notion of compacting an array suppose you have an array of numbers like here that's the array a and that contains anything and we have a different array b which is a bit vector and it tells us which of the numbers we would like to keep and which ones we would like to delete now we don't want to physically delete one number after each other that wouldn't be fast sequentially or parallel because you have to copy things over but what we can do is create a copy of only the elements that have a one in a new array but we'd like to do this in parallel so we can do it sequentially easily you just walk through the array once that's fine but we want to do this in parallel okay

29:00 and there's an easy way to reduce this to the prefix sum problem where you compute prefix sums of this bit vector b and then magically the prefix sums of this bit vector turn into the precision that you have to write an element into

29:18 that gives you the offset in s that you want so formally spelled out as code you compute the prefix sums on a copy of b so that you have b still around and then you can have a parallel loop where you're only doing anything if you're assigned to a position in a that is one so if if the original bit vector is a one then you're doing something otherwise you just do nothing and what you do is you write your element into the appropriate position in s and which position should that be well it's the number of other elements before you that have a one and that is the prefix sum in c okay so that's the the real use for prefix sums in sorting at least we want to be able to do this step go from this array where you have some positions marked to another array where you just copied out only the marked marked elements

30:30 what is the time for doing this operation that we just discussed oh what a mean question it asks for time and work um should i show you the algorithm

31:13 so when the question asks for achievable means using the best algorithm we know right of course you can always do it in a dumber way and spend more time on

31:38 uh how was it doing with the previous questions we had 51 anyone still thinking and or discussing all right five four three two one many different suggestions uh but some definite preferences for some of the options and

32:39 the best thing we can achieve is is this one so logarithmic span and linear work and the reason is well it's it's dominated by the prefix sums and so it was a test whether you remembered what the time for prefix sums was and you can look it up the slides before you can if you think about this first algorithm with these many binary trees overleaf where we went through rounds the work inefficient prefix sum algorithm that one would give you uh this option so it's in theory the other one's better um to be honest in practice sometimes this blocking technique has a little overhead so it might actually be worth trying for small inputs if the other is faster

33:27 but yeah in terms of asymptotic performance this is the best we can do