Video 3-7: §3.6 Parallel primitives, prefix sum

0:00 Prefix sum

0:03 in this subsection i want to introduce you to a few primitive algorithmic problems that are very simple to solve in the sequential in the sequential model but for the parallel execution to make it efficient and get a good speed up from parallelism uh we have to invest a little more effort and uh try a little harder to speed these things up they will appear a little artificial at first but we will use them right after to parallelize our efficient sorting algorithms quicksort and merge sort and then they will become absolutely vital for achieving the the parallelism there so let's get started with this

0:51 the first of these primitives is the prefix sum and here we are given an array of n numbers and i should say the problem is also called cumulative sums or running totals depending on on whom you ask we're given an array of numbers and the goal is to to change that array so that we have the uh prefix sums it's fine if we do this in place so we can overwrite the input array and in fact um the algorithms that i'll show you will do this uh but in principle you could also write it to us to an output array a sec a separate array and you want the cell in the output at position i to contain the sum of the elements up to and including position i okay so it's a very simple problem if you look at this example here's an array with a bunch of zeros so that the sumps don't get too big you see that um you just keep adding these things up and if there's zeros up here nothing changes but then we add the five so we get eight add the seven 15 and then it stays the same until here when we add the two again and of course the rightmost entry in the output will

2:12 be just the sum of all the elements in the input so far so good as always if you have any questions put them in the q a or on the campus wire lecture back channel i'll try to monitor both while i'm speaking and will pick up any of your questions when when we get to suitable point

2:41 so if you feel um you understand this let's see um first of all how this would look like in sequential so uh we have this problem of computing prefix sums we can do this uh with a sequential algorithm uh just take this array and you're allowed to do this in place right this is um this makes life a lot easier uh so um you can just overwrite the input what is the sequential time you can achieve for this for computing all these these sums of all the prefixes

3:18 give you a little bit of time to think about it um it's not i'm not asking for a very very fancy algorithm for this but try to do it as efficient as possible

3:47 we had 33 votes for the opening question on the programming languages so i suppose we might be a few people short today and almost all have voted now so let's show the results we have a clear peak for linear time but also for linear rhythmic and login and um a few on the others now people are changing their mind maybe uh so yeah um the correct answer is is linear time and um i'll i'll show you briefly how to do this if you do this sequentially you actually just need one single little loop like this so uh you iterate with i from one to n minus one and then you always take uh just the sum of the previous two now this this looks a little magic but if you think about it um you you add the the next bigger prefix sum comes from just adding uh the next number in so if you already have the the prefix sum computed in a i minus one so that's the if this already is the sum of the numbers up to i minus one you just need one additional number to get the next prefix sum that's why it's so simple um and uh in sequential time this is also the best uh you can do so this is

4:27 Sequential

5:24 um this is the way to go now for parallelization there's a problem here and that's data dependencies the previous step computed a i minus one and now i need it again for the next step i need it right again now i can't even wait a little bit to uh there's this i always need the previous step to compute the next step so every step depends on the previous one and that's that's the depth of all parallel computation if you have these kinds of dependencies so we have to do this differently if we want to parallelize it in a meaningful way

6:11 to get started with this let's look at a very simple problem even simpler than prefix sums just the sum you're given an array of numbers and you want to compute the sum of all the numbers in the array how would we do this it's clear that we can solve this with prefix sums just because

6:33 the last entry in the prefix summary will be exactly the sum but this is this is simpler because we don't have to compute all the previous entries now um the sequential algorithm essentially does a tree like this so we start by adding the first two numbers then we add in the next and the the next and so on i guess this should start with zeros uh so uh this is a bit inconsistent to the index indexing on the left but uh never mind uh so you you always add in the next number and at the end you have computed the entire sum uh it's also clear if if we do binary additions if if we compute the sum of n numbers and the only operation we can do is compute the sum of two numbers which is what our ram model tells us you can always add two registers into a third or well you remember how this when how this was done in the ram machine so if you can only add two numbers you need n minus one additions to form the sum of of these n numbers and the reason is that you essentially form a binary tree you start with end leaves that's all your elements and you want to merge them

7:56 together to a single thing so you need n minus one internal nodes for this uh what you can do though is instead of uh using this tree which is um a degenerate one you can make it balanced as a binary tree and then we have reduced the data dependencies a lot right these two elements can be computed in parallel to these two so all these sums on one level these can all be computed

8:36 and again on the next level they can all be computed in parallel because we don't have these data dependencies anymore between nodes on the same level we do have data dependencies between parent and child but that's another story all right and then the height of the tree is what we can expect as parallel time

9:01 Parallel

9:06 so let's um let's see how we can do this in an actual parallel algorithm we're given this input that's the initial array of numbers now we would like to do this lowest level of the tree first and this lowest level of the tree really just adds up two adjacent numbers um we we can do this here as well probably have to move myself away we always just add the two adjacent numbers but the trick is now um we want to do this for all prefix sums again not just for sum uh so uh we do this for all uh the pairs including the overlaps so maybe i should have said here at this point we've solved the problem of computing the sum of n numbers in parallel just the sum not prefix sum that's that's just it you take this tree you compute uh these two these two these two uh you compute the tree bottom up level by level then after log n steps you have computed the value at the root and that's the final output and there's no way to improve upon this because you have to do the n minus 1 binary additions and as long as it's binary the height has to be log n so that's that's the best

10:32 you can do and it's also work efficient because you still do just n minus one additions in total so um coming back to the prefix sum problem we now want to do all the prefix sums with these balance tree balanced trees and it turns out there's a simple pattern that allows you to do this where you just interleave all the trees and that's the lowest level here just says always add to the current cell the one that is one step back and you do this in parallel for all the positions in your array

11:19 in the next round you do the same thing but instead of going from one to the previous position you jump back two positions so you do minus two here it was minus one and um that that corresponds to the next level of the tree and you keep doing this until you have

11:43 reach the right level the the log n level and if you now uh look at this um particular element you can trace back the binary tree that you computed there was an internal node here and here and then you added those two up and the result is the 29 that you put in here now how can we make sure that 29 is actually the sum of all the numbers up to this position so we should cover that range and have summed it up so there's a little oddity because it's not a perfect power of two but apart from that we always have these two go into this one and these two go into this one right so uh you can you can follow this through except the the three here is a little exceptional in that it's added in here a level later because the powers of two didn't work out perfectly so you get this and that's uh in that sense um you get exactly the same tree as we had on the previous slide for a single sum but we could do this in parallel for all the positions and you automatically get the right type of binary tree for all positions by just doing this

13:08 going one step back going two steps back going four steps back going eight steps back always doubling your step size all right um let's see how this looks in actual code and because this is our first parallel algorithm i want to go over the way we write this in pseudocode in a little more detail

13:15 Pseudocode

13:33 again it's important that we do this in place uh we just overwrite the given array that makes um life easier and so this is all on the pram so remember that that means we have synchronous time steps

13:57 so in pseudocode we essentially use things like running a for loop in parallel which means we assign the ith iteration of the loop all right note that this is only ever possible if there are no data dependencies between iterations

14:43 the sequential code for prefix sum and maybe uh jump back a couple of slides if we were just taking this code and add in parallel here it would be a complete disaster because uh we would compute um these sums based on the original array so we would really only get this first step

15:09 the sequential algorithm relied on data dependencies that one iteration is finished and then the second is started for parallel loops like this one we assume there are no such dependencies

15:26 so what is each of these what is this algorithm doing uh we have a number of rounds and that's log n that's the the height of our tree the step size that's how much we jump back we double that all the time so that's the same as saying we use a power of two and now this is actually writing the step in the array and i split this up into two steps so we always take make in a i we add the thing that is step positions back i could have just written a i is this but to make this very clear we first do in parallel on all processing elements the reading step we read the old value of the array as it was before this round then we compute internally this axis in our register in the in the pram we compute the sum and then we all synchronously write it back so that uh we always get the old values when we read and everyone gets the same old values and then in the next step we write them back that's what's behind this assumption uh which is essentially just saying we're working on the pram okay so this is a a very concise and nice way of writing parallel algorithms just having loops that run in parallel

16:54 but it's also a little subtle because you have to be very careful that you're not creating hidden data dependencies where you essentially rely that some execution is finished before another is started that would be a disaster if you actually run it so it would be it would compute a wrong result

17:19 how good is this um algorithm that we've came up that we've come up with let's first look at the the running time the parallel running time and uh probably we just do this here on the code so maybe let me use blue for blue is not good that's my color for correcting mistakes let's take green for the time

17:46 so both of these steps they take constant time because they're for each processor it's just reading two numbers adding them and writing a number back to memory easy to do constant time for loop is also constant time now this is weird because usually a for loop is time n times whatever the body takes uh as a bound but here we do this in parallel so the parallel time is just the time of the longest of these iterations and because they all take constant time the entire for loop takes constant time this is another constant contribution just computing this power which you can do with binary shifts so this is um this is easy to do so it's uh the only thing that's left is the outer for loop and that one actually takes um log n time and the reason is that we don't have uh in parallel here we have to do this one after the other we first have to compute the the first round and then based on its results we can use we can go back to the next round so that's why we have logarithmic time and remember our the parallel the prefix sum problem also solves the sum problem and for the sum problem we convinced ourselves that uh log n is a lower bound because

19:20 we have to somehow compute the sum of n numbers using binary additions and that's only possible with a data dependency of log n now let's also briefly look at the work that is the total amount of operations that we do and here the only thing that really changes is this this part

19:59 in work we don't have this in parallel so we can pretend that this is not here for analyzing the work and then um of course uh if if each iteration of this inner if the if each iteration of this loop here takes linear time now then we do this log n times in total so this becomes n log n

20:29 uh right so um that is not work efficient it's not too bad it's a logarithmic overheads over the sequential algorithm but it's not work efficient okay but it's still a good algorithm because it achieves very good speed up and the work is only slightly sub-optimal

20:51 and it's a very simple algorithm which is also a good thing to have this is for for more complicated problems this is a typical trade-off you face if you get more parallelism then sometimes you have to work harder for this in exactly this technical sense that work goes up for this simple problem though we can actually get rid of the overheading work we can do uh linear work and double the time the parallel time that algorithm is a bit more complicated so i'm not going to show it because there's an alternative which is very simple conceptually very simple it's also a building block a technique that often works for improving the work in parallel algorithm and that's breaking things in blocks i'll show the details in a second we also achieve linear work so we will get a work efficient parallel prefix sum algorithm and the time will be three times the best that we can hope for so instead of these login rounds we have a three times login rounds but that's still um ignoring constant factors it's still best possible and a factor of three is is not usually a big deal

22:20 how does this work efficient parallel prefix sum algorithm work so it turns out that essentially a simple and standard trick uh helps here but it's um it's a bit uh puzzling if you see it for the first time so again i don't want to rush it too much the trick is to start with blocks off roughly the size that you want your parallel time for the entire algorithm to be at the end what do you want your time to be we want the time to be logarithmic so let's start with a logarithmic size of blocks so we break our array conceptually we don't really break anything we don't touch it it's just uh conceptually we divide the array into blocks of uh login indices those are these um so i i write this round parenthesis for meaning up to b minus one so it's like like you use uh the interval notation for half open intervals in in math i use this to mean a zero up to b minus one and then the next one starts at b okay and then uh for each of these we just compute sequentially the prefix sums within these blocks um maybe i'll i'll do an example with you while we're doing this let's just do a small example so that we don't

23:36 Example

23:58 spend too much time on it but let's suppose we have a simple array it's all just once 12 times the number 1 0 4 8 and i indicated the block size here this is not to scale uh the array should be longer i realized that log of 12 is not really four but it's not too far from it actually we round up so it is okay uh b is four

24:36 n is twelve now the first step is um sequentially i don't know we let's take orange for each of these we compute the local prefix sums and well these are simple

24:58 but we do this we do this in parallel and independently of each other so we take three processors pe zero computes this part this is pe one's job and this is pe2 so in parallel they compute but using the sequential algorithm inside to compute the prefix sums for just these parts okay that's the first step

25:27 the second step is we use the work inefficient algorithm that we've already that i've just shown you and use this as a black box but now we use it not for the entire input because that would be too much work we only use it on a reduced input and in that case we use only the right most elements of each block all right so let's uh let's do this maybe um to make the connection this was done in orange i don't know let's take green for this one so the next step is we take the right most of these elements

26:10 and uh in a sense we um create a new array that just contains these four elements um [Music] well okay let's uh let's just draw it with very large boxes so that it's uh is a bit it's maybe not beautiful but should be clear what's meant it's a small array much smaller than the original one it has size n over b

26:51 is this green well it's hardly visible right maybe all right um nope this color is fine we use the idea use work inefficient to well make it into the prefix sums which is uh this

27:33 so i'm i'm overwriting this but uh i'll uh i put it here so that you can see it and we'll we'll analyze it in a second then hopefully it becomes obvious why this makes sense the last step is uh for each of the blocks again um in a sequential step uh we add the previous um the the sum of the well the the green part from the previous block to what we just computed uh this this wasn't a good explanation uh so the third step is we copy this

28:16 and put it here okay let's make a bit room uh well roughly like this okay and um probably need this a bit higher you know what i'll make the entire thing a little smaller than

28:59 okay now what's the last step the last step is simply adding um this one to all of these this one to all of these so the last step in p o p e zero doesn't actually do anything here we get to four plus one and so on

29:25 and then you get this um again so it's the same processing elements each is taking care of its little block of size b and they just um add this to all the elements all right so here you add eight to all the elements that's that's all there is to it okay why is why is that a good algorithm um

29:55 let's see uh let's let's analyze the time and the work so this takes order b time because the processing elements all do the same thing in parallel and each of them is just using the sequential algorithm we need which needs linear time on a block of size b that's efficient that's good time b is what we want at the end and that's why remember why i said we choose the block size to be the time we want at the end that's that's why this is fine here okay the algorithm the work inefficient algorithm had um log n time

30:42 but here we apply it to a smaller n but this is at most log n so that's also good uh remember b is chosen as log n so again here this is also login

31:02 and for the uh for the last step we have the same argument it's order b because we just add a number to every position that's even simpler than computing the prefixes so the total time

31:16 is log n that's good we didn't screw it up but we already knew how to get parallel time login so uh the really important part is getting the work right and so let's look at the work how much work do we have in this first step we have n divided b blocks and we do order order b work per block

32:00 how about the green part this is the interesting thing one this is the interesting one now the algorithm had n prime log n prime work because it was work inefficient remember it used this n log n but if you insert what n prime is it is n divided log n times log off the same thing n divided log n

32:34 and this log just splits uh you can write this as log n minus log log n and the minus log log n we can drop for an upper bound and then the log n and the log n here cancels so that's the same thing as order n and that is what we wanted we now got the work down to linear time by using the work inefficient algorithm but only on a smaller input all right just to state that again here down there here the work again is linear time by the same argument we have n over b blocks of size b and each of these causes uh just order order b work so we in total get linear work

33:25 Compacting subsequence

33:25 all right that's it that's uh an essentially optimal parallel algorithm for the prefix sum problem good one little application of this is to study this problem which is called compacting subsequences this is uh what we will use in the sorting methods so um pay attention to this one we're given one array with numbers and we're given another array with well essentially bits 0 or 1. and what we want is to only select the positions from this large array where we have a 1 but we want to compact it we want to get only those numbers but in a contiguous piece of memory okay again how would you do this sequentially well you would just iterate through the array to the two arrays in in parallel i have a an index that goes through this and whenever you see a one you copy this over and increment some output index easy to do in sequential in linear time so the question is how to do this um in parallel and the trick is to use the prefix sums using the prefix sums we can compute exactly the position in the output array for any number let's do a quick example here so if you take the 7 if you compute the prefix sums over b that sums up

35:13 to 3 and that is the position in this array maybe minus 1 if you start at 0. and that's what you see reflected in the code here first we compute the prefix sums in b and then we do a parallel loop that's the important part now we can do this entirely in parallel now the second step

35:43 where if we have so all processing elements do this if check but only those that find in their cell a 1 continue doing doing something and what they do is they take the computed prefix sum subtract minus 1 for because we started with zero and then copy the element there to the array s

36:06 i hope this is um this is clear how this works and parallel prefix sums are the key ingredient to get rid of the data dependency we had in the sequential algorithm again remember here if we did this with a sequential algorithm where we just iterate through the arrays the problem with that is that the next position in this array depends on all the previous bits that we inspected and by computing the prefix sums up front which we just learned how to do this efficiently in parallel we can make the second step essentially trivial to parallelize

36:43 Question

36:48 okay let's see if you paid attention and to finish off with this here's a little question about this what's the parallel time and work achievable for compacting a subsequence of size n

37:58 all right um maybe a few more but uh yeah almost at 30. so indeed most of you got this right and the answer comes exactly from the code here the key thing that um costs in parallel execution is called is computing the prefix sums that gives us log n span whereas the loop here is is constant time in parallel so that's login time and for the work well we can use the the one the algorithm we've just seen uh with linear work for the prefix sums and then this is also linear work so we can indeed do this um in this optimal time and and work