Video 7-2: §7.1 Brent's Theorem

0:00 Work and span metrics

0:04 where we left off last time is at this point we defined the running time of a parallel of a Pam program a parallel algorithm as consisting of these two parts span and work span is the the overall number of time steps until all the processing elements finish but they can do this in parallel whereas work is the overall number of instructions summed up over all the processing elements uh and the first question is what should we aim for should we minimize work or should we minimize span or try both I mean ideally both but you might have to have a trade-off and the the main goal is to minimize the overall time so the span uh because that's uh that's the the thing you can't easily um get smaller and as a secondary Criterion will minimize work uh and often we'll aim for something that's called a work efficient algorithm so work efficient means that the work that you're parallel algorithm spends is in the same Theta class as the best sequential algorithm and so we allow a constant Factor overhead but other than that if we take our parallel algorithm and run it on a single thread it should not be much slower than what's best possible there so uh to wake up and get you

1:25 started I'd like to ask you whether that's always possible we had a phenomenal 87 people vote on the attendance code so we should have a reasonable number for this question

2:55 one so quite a quite a split um we think about it it is true you can always find a work efficient algorithm and the answer why is is pretty boring uh it's because I haven't told you that this work efficient algorithm should have good span work efficient in isolation just means what's in the definition namely the same Theta class as the best sequential algorithm so you can always take the best sequential algorithm whatever it is and that is a work efficient algorithm by definition it's just maybe a really crappy parallel algorithm because it might not use parallelism at all all right so okay maybe a um kind of a boring way to answer the question a much more interesting question is can we always find for a problem an algorithm that has the best possible span that's known and has and is work efficient and that's that's not so clear and I think um uh there's at least examples where we where we may not know yet um but I'm also not in not aware of an impossibility result that would say it's it's Unthinkable uh but that's that's more challenging to get sometimes but just keep in mind work efficient in isolation only says what it says namely same Theta class as the best sequential

4:29 Brent's theorem

4:30 algorithm right you haven't as much um we were basically recapping and have had one question uh the the main the main part of this introduction slide that that was missing last time is is this theorem and I didn't want to rush it so this uh if you look at this first time it it might seem like a fairly strange Theory um I'm I'm always assuming by looking at the span and the work I'm assuming that we have as many processing elements as we want because span is essentially the time you need if you have an infinite amount of processing elements and that's very unrealistic and even something like a linear number of processing elements one processing one one core for every part of the input yeah not really we often have a fairly small number maybe a dozen cores or a few dozen cores on a on a b server uh but certainly not Millions so um does that mean that this work in span is is not actually answering our question and it turns out the answer is is kind of still useful because we can convert working span into the into to the actual time on a machine with any number of processors that's known as as brand theorem um if we have any algorithm

5:49 where we know span and we know work um all of this is assuming where specific input size and so on so under the the usual models it can be worst case can be average case that doesn't matter uh but these holds especially the span works for an arbitrarily large number of processing elements then we can also simulate the same algorithm if we have a given number of processing elements and the time we achieve is this the span Plus work divided by the process number of processors and uh without affecting the work so that's that's the uh the span that we achieve now um the proof is essentially a a picture I mean the that statement already says what you're doing but let me try to illustrate it a bit um in an example so suppose we have some some parallel algorithm and it runs on uh many processors but because I'm not able to draw many so well on one slide let's say many is five so here's the five uh processing elements the five uh RAM machines now in the first time step so time moves down here in the first time step uh they each do something each of these boxes should be one instruction they might read something from memory or write something

7:19 or do computation uh what exactly it is doesn't matter uh then maybe in the second time step that do another thing uh let's do a third time step where maybe not everyone is doing something only those two are and then a last time step where they again all do something and then the program terminates now suppose we want to simulate this on just three

7:53 processors so I can't do five things in parallel but I can do the first three so I take the first three of those boxes and do those in time step one and whatever is left I do in the next time step again moving it just across the processing elements and once I'm done with that so notice that this is kind of wasted here processing element three is is just uh sitting there doing nothing for a for a Time

8:28 step then once I'm done with that I take the next time step of the algorithm I'm simulating and do the same thing and again I'm leaving processing element three doing nothing at the end of it for the blue time stamp we actually get by with the same time it fits on the machines and I guess you can see what the thing will look like here now so why is that good

8:53 enough if you look at uh how much time we need um the number of time steps here that's exactly the span so uh we call that here T that's the number of rounds I have to simulate now how big is one round well at most um as many processors as I'm doing work here so if I uh if I want to know what that is the number of processing elements on the right I can take the work and divide it by T that's the number of processing elements I can use there so that's my um my large number of processors and here I basically have this P hat divided p and I have to round up and if you insert what we know about this

9:58 then then that's uh something like this and uh I'm doing this for each of these rounds and if I sum this up uh I basically get I overall sum the same work I haven't done more work than

10:30 before and for the span if I want to determine how many rounds I have to do this um I have at least T because I might have um short rounds like the blue one and then I have overall W / P that comes from this here if you take that and multiply L It Again by T then you get exactly that contribution and this this plus T also eats up the slack that I'm leaving potentially all but one processing element running idle but it's at most one time step wasted for each uh of these of these steps so here I would have to to include the rounding but in in Big O that's the same so um like here the rounding should be there if you want to spell this out we would have t times and then W / T * P rounded up but we can upper bound this by that thing plus

11:52 one and so you see here again it's w divided P plus T and we get another plus t for the rounds where it's much much small smaller so in I don't know if the calculation was was very clear uh but the idea from an algorithmic point of view is very simple if you have an algorithm that runs on many processing elements but you know the span and and work that it needs you can calculate how much the same algorithm would need if you run it on a pram with a smaller given number of processors and the algorithm would just be schedule around Robin assigned the next free processor whenever you need another time step