Video 3-8: §3.7 Parallel computation, PRAM

0:00 Introduction

0:03 welcome back to com526 where in the sorting unit and in part three we'll talk about sorting with many processors using parallel computation this will also be a theme that goes beyond this sorting topic but i introduce it in the sorting chapter because it nicely fits there and it's sorting is a problem that's simple enough to solve sequentially in many ways and at the same time it's not completely trivial to do it in parallel indeed depending on how you look at it it's far from trivial to do it in the best possible way so i think that's a nice a nice topic to look at from this new angle of parallel computation

0:55 i think it was two-thirds or so had seen some form of concurrent programming and i'll give some more general introduction to this because also the terminology might be not completely clear so first of all money can buy you love but also can buy you time but it can buy your computers so that's why people love parallelism you can easily put a big basement full of computers and call it a supercomputer but the challenge is to make use of these machines because they're different from just having a single processor that runs absolutely much faster it's not the same thing you may know these stories about moore's law about the number of transistors in integrated circuits doubling every 18 months or so that has been true for a long time since i don't know it's 60s or so ish and it seems to be still kind of true but in 90s early 2000s this meant that the speed the clock speed of c of processors also doubled in that and that's roughly that with that speed and so you didn't need to do much to speed up your programs you just waited for the next generation of cpus but these times seem to be over just because of too much heat essentially created in the circuits so the more product the more

2:17 the modern processors still have more transistors but they use them in a different way they can't just crank up the clock speed so instead we go into the into the breadth and add more cores to uh cpus that's just for background i'm probably not telling you much new uh you all have devices in your pocket that are probably quad core eight cores whatever this used to be exotic machines uh some decades ago and today you hardly find a machine that is not a multi-core the raspberry pis might be some of the exceptions i think they have really traditional single core architecture all right just for for context um if you talk about parallel computation there's two main fields or realms that you should probably keep separate because they're quite different in the algorithmic solutions that they require and there's on the one side shared memory machines and on the other side there's distributed computing uh these are abstractions there's many many different forms in each of these but they're still um i think they're they're distinctively different in some abstract way that i'll i'll explain to you i want to stress that we'll focus in this class on the shared memory point of view and we'll look at it on a from a fairly abstract

2:55 Parallel computation

3:42 machine model so that what you create is is portable across different machines but the algorithms will look at if you just take them as they are they will not be the best way to do it on a particular machine there's lots more you have to do to put into this which unfortunately is often machine dependent to some degree so we'll try it again to stay in this realm of of eternal truths and take the the abstraction of the machines we have

4:13 what is a shared memory parallel computer so it has different cores different processors and the terminology we'll use here is pes processing elements just to have a separate term that you're not confusing with uh cores or processors these are a little ambiguous in actual hardware you may have a processor maybe the chip and then the chip has several cores maybe each core has actually several hardware threads because they're hyper threaded so the the con the discussion becomes a bit complicated and to avoid that i want to use a new term uh and that's also in in the textbook that's referenced on the website so pes is just the term we'll use for individual things that can execute pieces of code okay and we'll always assume that we have p of those even though we'll not always need this parameter

5:18 now if you have different different entities that compute they have they need some way to communicate and that's where the two models differ shared memory and distributed computing in a shared memory computer you have one big piece of ram think of it like in the in the pram model it's one huge array that will be our abstraction uh and this memory is accessible from all the the processing elements so they can all talk about memory address 5000 by the whatever some bit pattern and they will see the same memory the hardware has to do some tricks to make this efficient in particular caches are a complicated topic in parallel computation but we'll for today for this sorting topic ignore this these complications

6:08 um and this this is the only way that the processing elements can communicate they share this memory so they can write to specific memory locations certain values and then another processing element can read from there and that's how they learn something about the other computation

6:28 uh if you want a typical machine that fits in this topic think of a big compute server that has several cores they may have quite a few cores not thousands but hundreds and they can have really big shared memory so this is this would be expensive to buy a terabyte of main memory but it's not technically infeasible

6:50 the other the other model of parallel computation that we will not talk about in this module much but i i want to mention that mpi is is more in this context and this would be more openmp if you want to contrast those two and also like the java concurrent framework so say java threads um same c plus plus threads and python

7:19 all the things that tend to be built into a programming language they tend more to be on the shared memory side even though some sometimes they abstract even further and then the two models are maybe not so distinct anymore i will see more concrete examples okay what's what's a distributed computing what's the difference we again have processing elements but they have private memory which is only visible to them and if they want to communicate they have to explicitly send messages and mpi is one way to do that uh where it's sort of transparent if these are different operating system processes running on one machine or if they're communicating over a network

8:03 usually you'll assume for these messages that each processing element has an id a number well semaphores are that's a different different way we'll we'll talk less about this you'll see in a second why semaphore is a way to manage synchronization between different processing elements on the distributed computing model what you will assume is that the messages kind of synchronize the processing elements in the simplest way processing element i says i want to send a message to processing element j over here and so it waits until that guy has acknowledged the confirm the receipt of that message and that's a way how they can synchronize their communication their their computation by having this one wait for the other to acknowledge yes i received it and i'm at the same spot now that's one way of of synchronization um you can ex well you may guess that waiting for the answer might not always be the best thing um but that's that's the simplest and it's actually often quite powerful

9:13 in terms of concrete hardware that fits into this model think more of a cluster of machines that are connected through some some ethernet or some more dedicated network you will have heard of super computers which are interestingly somewhat a combination of the two they tend to have a cluster because you can't build a single machine and scale it up that much but each of these little each of these elements i shouldn't say little consists of one of these servers maybe not quite as big but definitely with several cores per node so a supercomputer is is combining the two models and that makes programming them sometimes a bit more challenging

9:59 we'll can we'll concentrate on the first model which also means we'll concentrate on on problems where the entire data you're working on fits into one compute node but again terabytes of main memory is not a fantasy so this is not much of a restriction it's more a question of how much money do you want to put into the machine or do you have to work on an existing cluster

10:25 PRAM models

10:28 now these are the models uh or the two big these are the two big paradigms um and i talked a bit about hardware that we actually have but what i want you to work on for the algorithms is even more abstract and that's the the parallel ram machine so parallel random access machine model uh in for short pram you will remember from unit 1 hopefully unless you forgot in which case you can go back to the videos what the ram model is like it was in short it was one big array of integers essentially as long as you need it and each integer was a certain size w bits and then you could fetch a cell store a cell compute internally that's pretty much what you can do and have conditional branches

11:26 now for the pram you have p of these ram machines but they share the memory so the memory is shared among all the processing elements it's a shared memory computer remember um and another important thing is all the processing elements run a ram problem program but it's actually

11:57 the same for each where we just use the id of the processing element as a variable inside the program so they can do different things they can depend depending on what their id is they can go into the one end or the other end of the code but the pseudocode we'll write down will be valid for all processing elements that makes it easy to write it down and then each processing element depending on its id may do different things

12:26 and now the last last big step last big part of this model that makes programming it much easier is these p processing elements all run in lockstep they have globally synchronized time steps and they all execute one instruction then they wait for everyone and then they do the next instruction now that's the biggest criticism people have for this model because this is not what current what what hardware can really do in in hardware that we have multi-core processors uh the different cores they run at not necessarily at different clock speeds but they run at a different number of instructions for a second for sure because the instructions take different times and especially you can have instructions that access memory that have to wait for caches so the time is not just the same time for each instruction and so they get out of sync so much of the work that you have to do after the abstract algorithm has to do with getting the synchronization fast on the existing machines and it may be fair to say that this is um still active research how to best do this there's been a lot of advances to make this a little less cumbersome what we'll touch on here is just the basic underlying part that is

13:44 more settled i would say so we'll just assume that all the the processors do one step at a time and we don't have to bother about synchronizing them now you can simulate this on an actual machine by explicitly synchronizing using something like summer force it would be a slow down so it's it's maybe not the best possible way but it's definitely implementable this is not completely esoteric it's just not the most efficient way on the existing machines we have okay is the model clear so far

14:24 so p independent rams they all execute the same program and they run in lock step now if you if you think about this for a moment um you have different processors they all happily compute things they have their own sets of registers right these are separate they don't see each other each other's registers for computing but if they load and store to the shared memory they hopefully see what the other processors do because that's the whole point of shared memory but what if in the same time step several processors want to write to the same location they might override each other's values or they might create a conflict and we stuff we have to do something about this so what's uh that's what this slide is about we have to somehow define in the model what should happen if more than one processor writes to one specific location in memory uh and you could have you can come up with different solutions um one would be you completely forbid this the er ew pram says all reads and all rights of all the processors have to go to different locations if your program doesn't ensure this it will just the machine will explode or whatever i mean it crashes with some error it's not allowed your program is not uh

15:48 wouldn't compile or something like this it would throw an error that's one option this is very restrictive but sometimes this is enough what's definitely slightly more general and and works just as well is to allow concurrent reads because reading the same location at least is well defined they will all retrieve the same value so there's no no problem on that side uh and indeed this is something that hardware supports uh reading a value from shared memory is fine if this is done in parallel there's not a substantial slowdown from doing this and this model still writes have to be exclusive so only one one processing element can write any cell at any time

16:37 a more general model allows concurrent rights but then you have to say what should happen and there's again different ways how you can resolve these conflicts um an interesting one that is that might be it might be a bit weird at first you allow concurrent rights but if they happen they all have to write the same value so there's no conflict really it's just the processing elements don't know about this but you as a programmer can make sure from the outside that if several write to the same location they will always write the same value we'll see an example in the tutorials for this weird model why this can make sense

17:17 the other one is maybe more like what hardware builders would like you can write several values to them to the same location but then arbitrary things can happen any of those values wins and you don't get a guarantee which one there are other things that uh that would happen that could happen you can come up with with different models and um in a sense it's not completely fixed what the hardware will do there have been different approaches tried and so this is still somewhat ongoing that's why we have this wealth of different models just to make to play with the possibilities that they give us the default model here though will be the crew p ram so we allow concurrent reads but we don't allow concurrent writes that avoids the main bottleneck that p-ram algorithms see in practice apart from the synchronization namely if several processing elements write to the same location you get into something in actual machines called cache coherence problems and then there's cache coherence protocols just as an aside like this is not in this model but suppose one processor writes to a certain memory location it actually doesn't write to main memory it writes to its local copy in its in its own cache if this other processor wants to write

18:41 the same location then these caches contradict and so they somehow have to be reconciled that they reflect the same value and that means they have to talk to each other and that's slow so in a in a way um writing to the same location is something that will inevitably slow down your concurrent programs and there's essentially nothing i know of that hardware can do really about this uh there's ways to make this not get completely arbitrary behavior but they all have a slowdown so it's um it's not only a nice model to look at because um it allows interesting algorithms it's also one that encourages you to do things that will run fast by only allowing one right access for your memory location okay

19:47 Time

19:48 there's one last thing about the model we have to tell if we want to analyze algorithms how expensive are different things and as before there's different cost metrics that we could look at

20:04 space and time are the same as before so not really surprising but we'll have to talk about time in a second a bit more space is easy in the pram model because we have this shared memory we'll only look at how much shared memory we'll use so that's same as in in standard ram or time in pram there is a well-defined time namely the number of time steps that the program runs now notice that uh

20:35 not all processing elements are necessarily still active till the last time step they all execute the same pro program but they have their id that means they can go to different branches so they might go to sleep or basically terminate ahead of time whereas some other processing element might still be running so by time we mean the number of time steps till all of them have finished

21:01 you will call you will see this called either the parallel time or the depth or the span of an algorithm all are really talking about the same thing maybe this doesn't really deserve to be in small print we will usually assume for the analysis that we have as many processors as we like again not a reasonable assumption in practice but i'll come back to this in a second it is a reasonable assumption for the analysis why we do this in in short we want to see what is the limit of parallelizability in this algorithm and not what's the limit of the machine we're looking at so we give it as many processors as it can sensibly use and see if that helps to bring the parallel time down okay

21:57 and the second important parameter is the total number of of instructions executed across all the p processing elements so in this sense for work in work you pay for using many processors because the the time is in a sense multiplied with the number of processing elements

22:16 Work efficiency

22:18 and then the goal of designing pram algorithms is to minimize the time as as usual our goal in algorithmics but we also want to minimize the work so the the ultimate goal would be have a parallel algorithm with minimal parallel time or minimal span and the work not much worse than the best sequential algorithm okay and this is what we call work efficient so the work of the parallel algorithm is big theta of the work the the time of the best sequential algorithm we know of

23:07 simple question just drilling on this definition now let's see if slider works again for everyone we've got quite a few votes for the other for the last question so i'm slightly i'm somewhat confident hopefully

23:34 and you guys read the question very carefully we're at 49 of the last question i say it's three two one and locked all right so it seems the majority is convinced and wrong

24:28 i don't enjoy this as much as it sounded but let me explain why you're why you were wrong it's probably how i post the question partly the question is does every computational problem allow a work efficient algorithm and it doesn't say that this has to be a good parallel algorithm it could be a crappy parallel algorithm that just runs on one processing element and does exactly what the best sequential algorithm would have done in other words it is the best sequential algorithm just not making use of parallelism and so it's by definition work efficient so you can always do this but in an uninteresting way right so

25:10 you can always achieve work efficiency but this is not by itself interesting interesting is the combination good span and work efficient but [Music] why care about work at all i mean we care about time and we can buy a few more processors so why bother about um about work this is not really time that we spend uh the the thing where it becomes important is

25:20 Why work

25:45 Brents theorem

25:48 where it becomes important is the observation that you don't usually have uh vita of n processors if say you're sorting a list of of 10 million integers you don't have 10 million cores no way and even if you had maybe this is not how you want to use them so these notions of span and work seem a bit well in a negative sense academic i want to convince you that they're not as not as useless as they may seem at first sight and this is what's known as brent's theorem if you have any parallel algorithm that has a given span t and a given work w uh where i mean here the work of the span assume that you have as many processors as you want then you can actually run this on a on a what is this doing you can actually execute this on a pram

26:42 Parallel time

26:47 with double with p processing elements so if you have the your concrete machine you can insert what p is and you can work out that the parallel time comes down to this it is the span of the original algorithm but plus w divided by p and you're still using essentially the same work up to a constant factor more so why is this important it means if we have some parallel algorithm with this unrealistic assumption arbitrarily many processors if we have analyzed the work in the span we can go to a concrete machine with a given number of processors and compute what is the time and work on that machine okay and the way to do this at least in theory is very easy uh as this this is one line proof but maybe a little example is useful you just schedule the steps that the the algorithm would do on arbitrarily many processors round robin across the the p processing elements you have so maybe in the interest of time let me do a smaller example

27:53 suppose the original uses six processing elements and so time proceeds top down the first time step they all do something they execute one instruction and then in the next time step they do another instruction remember they're all nicely working in lockstep they proceed through this at the same time and maybe the algorithm is really fast it gets the job done in three time steps so that would mean t is 3 here and work is well if we just sum up all those we get to 18 assuming there's no other no other overhead now how could we simulate this on say

28:52 four processors if we don't have six we would take in the first time step we would get these four scheduled in the next time step we take um these are actually seven so seven times three is not eighteen uh so in the second time step we have three left so these are these first ones for the first four processing elements what they do in time step one if we simulate it on four processing elements we have to do another round of these that's the remaining three okay so we need two time steps then same thing happens for the red ones

29:41 and maybe i should have cut the example short this is probably easy enough for you to imagine how this continues we can make it slightly more interesting by saying a few of these actually finish early so uh we don't have the full

30:01 but we do the same thing we take the the first four that we have and there's one more that has to go in the second time step so you can work out what time and span on the for processing element pram would be then

30:16 and if you think about this in general if you have to simulate if you have to simulate here these these uh what could i call these m steps that we do you need m divided by p time steps each now we just need a bound on m so here

30:42 we used m processing elements on this side instead of the p that we have and we can use the uh work and and time to to get to this so the work is m times the time so we can solve for m

31:17 and then what do we need here for one of these simulation steps we need m divided by p and if you insert what m is that happens to be um d divided by p w

31:41 and now we don't have this just once we have this t time steps the decimal messes up that it doesn't yeah okay solving equations is a tough one what's the use of you being here if you don't tell me i'm doing nonsense okay so we have that number of steps for each little execution step and we have t of these steps right so the the total time for the simulation is t times this one if we want to be precise we have to round this up so it's t times w divided p times t rounded up and now i wish i had a little more space

32:52 wish granted uh so you can upper bound the rounding up by plus one right so you can you can multiply this out then you get w divided p plus one times t and that's exactly the bound that we get here uh you can analyze the work as well the work we're doing this roughly the same number of steps right there's maybe a little overhead for simulating this that i i didn't show on the slides is the concept kind of clear so what does round rubbing simulation mean you just take from left to right the next available job it's a general way of scheduling jobs here we do it on very tiny little jobs it's one operation of one pram processing element so we probably don't want to do it at this small scale but the same idea on a more coarser scale with bigger tasks does work well

33:54 okay so much for the pram model question yeah it doesn't make a big difference you're right ron robin is one solution so the question was why do we take round robin's scheduling here instead of something simple like first come first serve the only uh you have to make sure that you first execute everything from the black portion the first time step in the original program get all those finished then wait and then start with the red ones because remember these black ones these black instructions could be write something to memory so we want this to be happened be finished before we continue with the red one which could be read that memory from a different processing element