Video 5-1: §5.1 Parallel computation, PRAM

0:00 Intro

0:02 okay welcome back to efficient algorithms we're finally leaving behind all the topics that are often covered in undergraduate computer science classes as well to some degree and now our start some some exciting topics that go well beyond that the first such topic is this one unit five parallel algorithms so we'll look at how you can on the conceptual algorithmic level take advantage of the fact that basically all computers we have apart from the smaller embedded devices have multiple threats of execution multiple cores and so uh you need to you need to specifically program them to take advantage of that that's what we'll look at my goal for you is to know uh some fundamental strategies how you can parallelize problems we'll keep it away from the actual code and this is unfortunately one of the one of the case cases where I can blame it on the technical side the software tools for parallel programming are not as convenient yet as they have become for standard programming sequential programming so some of the things we'll touch on here uh need a lot more engineering work to be fast in practice than the sequential methods just because there's more technicalities involved at least at this point

0:47 Learning Outcomes

1:30 I want you to also be able to say when a problem is not possibly sped up by parallel algorithms and we'll look at the formal machine models for that that allows such statements we'll analyze algorithms and that will require a little rethinking of of what we mean by time and we'll look at some concrete methods uh where the parallel algorithms are interesting we'll look at more but these are the the non-trivial parallel algorithms

2:03 we'll start with the models and then we'll look basically at two problems string matching in parallel and sorting and for sorting we'll need some intermediate steps that maybe don't make so excited and exciting in isolation but without them it seems really tough to get other problems going so these are again fundamental building blocks and we'll put it all together in in the last part

2:31 Clicker Question

2:33 before we set the stage for that let me ask how much experience you have with parallel programming is this tends to vary a lot I think we have very few students from the um Big Data program they usually do a little more of openmp MPI you do a little bit of that what course is that looking forward okay yep so you will you will do a little bit of that uh you will you will see how it contrasts to what we'll uh discuss um and maybe uh enjoy the less tedious parts

3:32 okay I've only had 25 votes for the for the join code and more here so I'll probably show the code again I guess um Okay so a few of you among the seven have done this but also a lot of people have never touched any any parallel programming now I mean this is probably a large chunk of the people who haven't really programmed before starting this course so it's kind of obvious but I think the the subset of people who've done programming and parallel programming is much smaller than the set of all programmers is something that people are usually not so familiar with there are many different types of things that could be called programming in parallel so it's is also in the details of what that exactly means let me switch back to the um attendance code and

4:36 I probably should have also asked if you've seen parallel algorithms before I guess the answer is no for most at least uh it's very rare that this is taught in undergraduate classes

4:48 Types of parallel computation

4:52 all right why do we care at all uh if you have a lot of money to solve a problem you can buy lots of computers maybe unless there's Global shortage of semiconductors but let's leave that aside this is a when I wrote that there was none um and uh things will get better in principle money can still buy you lots of computers maybe just not some of the chips uh but that alone doesn't make a program faster it can't buy you time if you want to solve a certain problem really fast you have to make it work on several computers at the same time and that that can be a challenge

5:38 now let's uh Jump Right In into a distinguish uh to distinguish two Notions which both can be called parallel computation but they're very different in the techniques and that's why we have to focus on one of them uh the the one that we'll look at is a shared memory parallel computer so you can imagine it's one big device um which has shared memory that's the distinctive feature so all the processing Parts can access the same memory but there's several processors So to avoid using any specific technical jargon I'll just say processing elements which is standard terminology and the algorithms literature on on parallelism where a processing element can be a single core or it can be a hyper threat core or it could also be an entire machine as part of a super computer so a super computer somewhere are in between those two is sometimes a bit um tough to make the clear cut okay let me finish this first though shared memory that everyone can access but several individual pieces that can compute okay uh there's also the main communication between these different pieces that compute happening through memory so they certain they can they can make this up we'll have to program them to do it but they can say memory location 42

7:07 is a special memory location I use this to send to send messages by writing some specific value there the typical thing of this uh I think this is still this is still amazed basically the same numbers so you can buy these machines beefy big compute servers a lot of cores but not those thousands maybe hundreds but they can have really big memory uh you can have main memory in the terabyte range it's expensive but you can you can build these machines the big other uh parallel form of computation is distributed computing again we have same concept different processing elements that can compute but they have private memory and they send explicit messages to communicate so there's some network connection on top of the uh individual machines and so they can only communicate by sending messages across the network think of a cluster or a compute Center of the old style at least where the machines are fairly separate

8:21 so this is a different scenario and you can maybe imagine that here the bottleneck will be the message is if the network the network usually is orders of magnitude slower than the rest and so the real dominating factor is the message is and that's a bit of a different world it needs different trade-offs now super computers I think these days are somewhere in between because they are distributed systems by the setup they are composed of individual machines but they're connected by so fast Network that they can almost be treated like a shared memory machine in some regards so sometimes the distinction is not so clean uh for for us keep this in mind uh a single big beefy machine with

9:12 a couple dozen of processing elements and huge shared memory that's the the main thing I have in mind for this um the way we will model this remember we want Eternal truths so we want statements of the kind no algorithm can possibly do this better than so and so to compare it to the algorithms you do have and for these statements you need a formal Machine model that tells you what are programs like and how is performance measured and for this unit that's the P Ram the parallel Random Access machine you may remember the ram model I hope you do the pram differs from that by having several processing elements no surprise now the the rest might be a little awkward at first so kind of um bear with me and and pay attention so every of these processing elements has an ID and we always assume 0 up to P minus 1 are the IDS and they can use this in their program I'll come back to that they also have uh it's a still the word Ram model so they operate in in words of so and so many bits W bits and that's a parameter of the model remember we used to think the word size is is roughly like logarithmic in the

9:33 PRAM - Parallel RAM

10:50 input size and now we have another parameter P which the number of processors also can depend on n so our machines grow with the problems I've discussed this back then a bit more maybe it's no longer such a shock to you It's Not Unusual that for the algorithm formulation we just assume we have as many processing elements as we'll have inputs this is not usually realistic but it's also not usually a problem for Designing the algorithm and I'll um I'll show you why in a couple of slides but the thinking for Designing the algorithm should be you have loads of processors no shortage of processors

11:38 each of these this should really say the same all of these processing elements run a standard Ram program as we've done it all the time at least under the hood and this time we assume they all run the same one and they run this to a good degree synchronously so one time step is the same for all the processing elements they run in lockstep uh they do a step at a time they can't do different things because they can use their ID as as a variable in the code so they can Branch off in different directions depending on which processing element it is

12:21 hpe has its own registers but the large memory the unbounded memory of the ram model is shared so they all access the same one I already said they they run synchronously um and so that makes it easy for us to Define time we can just count time steps again

12:42 if you're worried about how realistic the model is that's usually the the part that needs extra work this is not how current Hardware realizes parallel processing um what almost all software Stacks above that do is establish some sort of synchronization and so you can essentially emulate this the question is how costly it is so this this is the engineering part I alluded to there's some constant Factor overhead involved in synchronizing the different PES and the goal in practice will be not to do this too fine Grant you're not not after every little step and often you don't have to but for Designing the algorithms it's very liberating to ignore that part and worry about it separately it's two separate concerns and the good parallel algorithms that work on the pram unless they exploit this this very very much also yield good algorithms in practice on the the machines that we have

13:49 now there's one problem that if if you think about this for a while um we say all the different processing elements run happily their program a ram program can involve reading and writing memory so it could happen that two processing elements at the same time remember they run synchronously lockstep uh they could both try to write a value to one location in memory and so we have a right Conflict at this point and we have to somehow resolve this now as a theoretician that is a question of the model what should happen and there's there's different models which restrict what the programmer is allowed to do um and they're they're all reasonable in their way one model is the exclusive read exclusive right pram I know these these acronyms are uh us awful but um that's that's how it's stuck so I think it's best to just remember what this stands for so the exclusive read exclusive right parallel Random Access Machine model uh just restricts the programs so that it never happens that any two processing elements at any point in time read or write the same location very restrictive but no at no point will that ever happened uh that we get this this conflict situation if you think about it for reads it's

15:21 actually not so controversial what should what should possibly go wrong if they both read the same location they will read the same value not much I'm done so the the crew P Ram allows concurrent reads but enforces exclusive rights that kind of still has no problem just the rights cannot go to the same location at the same time and again um so you should think about these models as before they start running they look at the program and if the program contains rights at the same point they somehow magically recognize that and say no I'm not even starting it's the programmer that has to proof this up front that your algorithm satisfies the restrictions so it's really a restriction on the programs not necessarily in the machine itself

16:19 uh the the crew is often the model that we'll think of because that's what what programmers often find easy to work with because that is free of weird things unfortunately that's not what current Hardware does um but again I I said that one of the complications is getting performance right in this space is tough and so there's usually Hardware that does one thing software above it that tries to restrict the most confusing things from happening the other model is the the concurrent read concurrent right pram which just allows everything but now you have to somehow say what happens if two processing elements right to the same location you can resolve this in a different way a simple option sounds awkward but can be really powerful is the common

17:16 crcw P Ram that only allows concurrent rights if they have the same value then again no conflict really another option is the arbitrary one and unfortunately so this is where your computer does almost uh you are allowed to write to the same location but the abstraction doesn't guarantee you what happens really unless you put other mechanisms in place to synchronize the rights to make sure that they're properly ordered logically uh anything can happen that's what we call a race condition and that's what plagues parallel programmers day in Day Out and I think we still haven't found a really good solution for this that is at the same time easy to use and exploits the the hardware to maximal Performance maybe we'll never do this maybe it's never never gonna be possible uh so this this is closest to the hardware but if you can design a parallel algorithm to live in this space no concurrent rights it'll be much easier and faster to implement on the real machine

18:23 that's why this is our default but it makes sense to keep all in in mind as possibilities uh last slide on on the model I think is um what is the cost of an execution because we have several processing elements now this is maybe a little less obvious but space is still clear it's just the total memory that is used by any of the processing elements time a natural way to define is just the total number of time steps till all of the processing elements have finished uh the make spend in other terminology so this is this is the real wall clock time you have to wait if you start the computer and wait till all the processing elements are done it's often also called uh not time because that's a bit ambiguous but depth or span uh pick the term you like best um depth alludes to uh a visualization where you you say what what can run in parallel is next to each other and what cannot be parallelized goes below and so then the depth becomes the number of time steps now this is new we'll have a third one a third metric that will be almost as important as the other that's work and that's just the total instructions okay executed across all processing elements

18:28 PRAM- Execution costs

19:56 you might wonder why you care about this an easy one is that's probably proportional to the energy you're using which is much more of a discussion these days especially in Computing Cloud compute centers but there's another reason that we'll come to why why work cannot be ignored

20:18 what are we aiming for in theory at least is minimal time as always we like to be fast um but we can't ignore work so the best possible we can hope for is what people call a work efficient algorithm so that's an algorithm that's essentially as good as the best sequential method in terms of work so you take you take a an algorithm that only works sequentially that gives you a Theta class of the running time and the usual way we usually think about the worst case and so on you take that Theta class that's your goal for the work of your parallel algorithm the way it's supposed to spend at most a constant Factor more total effort but somehow squeeze that in time so that can it can just be run in parallel on several processing elements okay other three the three things make sense space time and work or space span and work

21:32 now a little corner case for you to ponder whenever we Define a notion it's useful to think about whether we're talking about the empty set and nothing can possibly ever be work efficient

22:25 I'll wait till 40 people have voted that's what we eventually had on the all right so there we go yeah it sounds like um you should expect always to have this but no you can always have a work efficient algorithm now the trick is um it doesn't say that this has to be a fast parallel algorithm in terms of time it just says work efficient so you just take the best sequential algorithm that is work efficient it's probably a crappy parallel algorithm unless you spend some time on it by the way I like you don't need to change your vote now to reflect that you've known it up front and it's all um I won't I won't look at these results also the video shows that you changed your mind was always fun to watch

23:51 so one one more reason for the recordings right so the simple reason is you can take the sequential one but again um the real interesting question is uh one that also improves the parallel time and there it's not so clear I want to finish this this introduction on the model with an important argument that um I think is often like is sometimes lost in the discussion and it's very unfortunate people often complain about the pre-ramp model that it's unrealistic because it assumes you have this humongous number of processing elements and I think that point is is missing the point the other part that it assumes the synchronous time steps I take that uh criticism that that makes sense and you have to worry about how to realize for some of the algorithms um on the more relaxed Hardware that we have the number of processors is not really a problem and the reason is Brand's theorem which says whenever you have some parallel algorithm with span T and work W with time T work w I'll use span to avoid the confusion with time uh I already remember some of the slide Stones so I sometimes use span avoid the confusion with time you can also call it parallel time that's is all the time we defined the

24:00 The number of processors

25:28 number of time steps till everyone's finished so you have an algorithm with time T work w uh then you can always simulate that algorithm on a specific P Ram that has P processing elements in time that's not t but t plus W divided p and roughly the same work so in a way before we look into how why that's true I want to point out this um this corollary of this uh didn't want to cross it out if you have a theoretical algorithm on the pram that assumes whatever number of processors it is actually a family of algorithms that could be tailored to any number of PES and if you know the work and span of this theoretical algorithm where there's many processing elements as you want you can always translate it to real time and work bounds for a specific number of processing elements and so you can you can predict fairly well roughly how well it will do and so it's um it's much more useful than it first sounds now the argument you will be disappointed by the proof of this theorem because it's very simple and also shows that um there's a constant Factor overhead paid in terms of the time that may not be negligible

26:59 let's suppose we have a pram algorithm that uses many processors and let's suppose many means five so I I finished the drawing at some point um and so I'll draw the the time downwards this is time we have time step one two three four and so on

27:32 the instruction that each processing element does so it could be that we have five processing elements working on this and they each do some instruction in time step one then they do some other instruction in time step two

27:56 uh and another in time step three maybe this time not everything not everyone participates because some are already done and and maybe here's this just one but then say time step five they all come together and finish off whatever they've done so how can it come to these gaps they all execute the same program but they remember they can use their processing element ID so they might be idling around uh during some steps and wait for the others so that's where we'll see examples that's possible now let's suppose we have to simulate this

28:46 on a pram with only three processing elements so how would you do it well yeah you only have the three processing elements so uh so all you can really do is pick one of these tasks at a time so you take the first three put them here

29:13 and then there's two left so you need another time step where the same processing elements now do the remaining two so what you do is just round Robin's schedule the tasks that you need to do

29:29 and you may need a little more time to do this if all the processing elements participated but sometimes you can do it in the same time sometimes you need an extra step how bad is this algorithm in terms of first of all the work is almost the same you need a little overhead for the scheduling who does what I'm only sketching this very high level so work will be similar just um a little overhead per step now if you look at each of these I need to turn this off how long is this well it's

30:17 it's the number um it's a number of processors we don't have a let's call this P Prime that's the or big p for is that larger and now we divide it by the little p that's how many rounds I need and I have to round up now I do this for every time step and if I sum this up uh I have at most P most capital P in each step but actually if you sum it up you can only have as much as you have work on the right so the total number of boxes is the work

31:11 so if you sum up this term over all the faces we've done on the left this capital P will sum to work in a way it's how many are active at each point in time

31:39 so it's um I should have introduced proper notation for this but if if you say capital p i is the number of processing elements that are active in Step I then p i divided P rounded up is the number of rounds you have to do uh in this in this round robin schedule and if you sum these up over all the times then the pi is sum to W but because of the rounding up you need to add a plus T you have at most plus one in each step uh let me smuggle in a an intermediate step here to make that clearer if you round something up you can always bound that by adding one and drop the rounding and then that sums to W over P plus t okay so at least in theory you can always simulate whatever parallel algorithm you have on the number of processing elements your machine has and you still get a reasonable estimate for the time now if this time is good or not depends right it depends on T and it depends on W