Video 3-6: §3.5 Parallel computation, PRAM

0:00 <Untitled Chapter 1>

0:03 i want now to open part two of the sorting unit when we started this unit i said it has two purposes why i want to discuss sorting in detail one because it's it's just a beautiful piece a problem that is a nice playground for all sorts of techniques algorithmic techniques lower bounds and these things that we just discussed and the second reason was that it also is a good place to learn about parallel computation and how to use many different concurrent processors and this is what the second part will be about how we can sort with many processors

0:44 before we get really started with this i want to see if you have used any kind of if you have any kind of experience with parallel program programming and let's be generous about what that really means in detail um but um

1:06 most most graphical user interface applications actually force you to use a little bit of multi-threading so i want to see if people are have some familiarity with this and there's no reason why i wouldn't show the results for this one so um let's open that one

1:36 it's not that we will in any way require knowledge from parallel programming for this module it's more for me to know how much is it sensible if i make comments about how are these things addressed in practice how are these things done in programming libraries whereas if uh so it looks like half half so if uh if most of you have had not seen anything like this i would have avoided some comments but since a large fraction of you has some experience with this it makes sense to connect the theoretical model a bit to the current practical programming models this will make more sense in a second when we discuss the okay well all is wrong shouldn't have been there okay the different types of parallel computation in general and i want to briefly discuss these and we will focus uh on just one of them for this class the core thing why people get excited about parallel computation is that money can buy you time but it can buy you more computers so if you can just rent an entire compute center and compute a challenging problem but in parallel on all these many computers then it might be possible to solve a problem that otherwise would take years and would never finish in a reasonable time if you can

2:29 Types of Parallel Computation

3:09 parallelize it to many machines it's just a question of how much money you want to put in it so parallel computations are are very important these days and uh not only because you can buy easily more computers but also because we are reaching the limits physical limits on how much you can further compact and speed up integrated circuits so any future major speed ups will probably have to come from parallelization even the small handheld devices have multiple cores so anything you do has to be parallelizable if you want to scale it up that's enough of advertisement the two types of parallelism are basically shared memory parallel computers and distributed architectures

4:12 both are important and both have their place in in algorithms distributed computing is maybe a little less understood and therefore i'll leave it out of this discussion um there are many interesting algorithms here as well but we'll focus on the shared memory parallel computer so what do i mean by that again this will eventually be a formal model of computation but uh for now let's just keep it a little informal we have p processing elements think of these as as processors and they can work entirely in parallel they communicate by reading and writing from a single shared memory and this is again like in in the ram model we assume that this is unbounded it can be as big as we need it and every pe can access every cell in memory using essentially the same mechanism this is an approximation of single big servers and these do get fairly big these days you can easily have 128 cpu cores maybe with hyper threading even more concurrent threads that are executed and a terabyte of main memory even though expensive is doable so these are really massive machines but unless you use the many cores efficiently there's no way you will make good use of that such an expensive machine

4:29 Shared Memory Parallel Computer

5:49 Distributed Computing

5:51 just briefly distributed computing is similar in that there's also p processing elements that work independently and in parallel but they have private memory and so they can work on their private memory but communication between processing elements is only via defined interface can be over the network i mean it can be over the internet or it can be a more specialized faster network within a high performance computer this is up to applications but you usually send explicit messages from processing element a to processing element b so this is more like a cluster of individual computers connected by a network again we'll focus on on shared memory and the formal model now is the pram it's the parallel random access machine you know by now what the ram is if not refresh your memory in unit one what the pram adds to this is that there are p such processing elements and each is essentially a ram computer what's important is that these

7:06 these individual processing elements are identified with ids and we can use these ids in code and we can compute with them so that again it will become much clearer when you see an example but it's important that they have an identity

7:28 now we already had a parameter from the ram the word size and now we additionally have a parameter p so for every problem we now have three things floating around there's the input size n the number of pes p and the word size w view well we'll have to deal with it but often we can ignore the word size for the parallel computation it often is not the the interesting factor and for p we'll find um a different solution when we go to the work span model but um i'm jumping ahead of myself what has to be kept in mind is that they all can grow with n so having an assumption or an algorithm stated with essentially a linear number of processors is not unusual suppose you were sorting a list of n integers and the assumption there is you have n processors so you're sorting a list of uh a billion integers there you go here you have a billion processors if that sounds a bit unrealistic we'll fix that later this is um this is the the theoretical model there are fixes to make it useful for practical statements we'll come to that all of the pes independently run a ram style program and it's the same this is maybe um

9:05 they they really run the same program and uh in lockstep they run this synchronized their time is is synchronized all the processing elements make one step after the other but in parallel

9:20 and in this ram program uh we use the id to tell uh what is different for the different processing elements um that's that's the the way it's usually done and it's a it's a convenient and concise way to do it

9:41 uh each of the pes has an own copy of registers but mem is shared among all processing elements that's the shared memory model and as i already said they run in synchronous in synchronous steps

9:59 the the assumption that they run the same ram style program because they can use their id to branch off into different parts it's not it's not really a big restriction so this this looks like they have to go in lock step and execute the very same thing all the time but because you can use the id this is not true so that's the that's the model um the ram model if again if you have questions uh please put them in the chat i'm throwing a lot of definitions at you today and i hope it will later become clear how these affect things and we'll discuss some of this more in the tutorials uh we'll next talk about conflict management but i first want to stress on this slide this sounds all great so they all independently run their operations and if if this processing element adds two numbers in its registers and this adds to other numbers in its registers nothing bad happens the only complicated part is what happens if different several processing elements concurrently read and write the same memory cell this is where things get complicated and this is also where things in practice get well either wrong or slow or you have to make something sophisticated

11:21 in the pram there's different versions of conflict management what happens if you access the same memory cell and these go from strict to more lenient the strictness is the exclusive read exclusive write that means no one is ever allowed to access the same memory cell in the same time step and if that ever happens the machine just blows up and so you have a broke as a programmer you have to avoid this at all cost this is super strict and is stricter than most actual computers need it so it's not used a lot but sometimes it's used to show

11:22 Versions of Conflict Management

12:08 Concurrent Read but Exclusive Write Model

12:10 more flexible is the concurrent read but exclusive write model which means it's fine if if many processing elements read the same cell because reading doesn't create conflicts as long as the same data is written there and they read all the same value it's uh it's consistent but writing can create can create problems because you could write try to write different values to the same spot and then you have to decide what wins so the the crew pram just says this is not allowed whenever you write to the same cell it has to be a single processing element

12:51 there's no parallel uh right access you can also go to a concurrent read and concurrent writes so you do allow several processing elements to write the same cell but then you need uh you need to say what happens with different values that are written to the same to the same cell and there are again different models you can assume if this happens they must all write the very same value so there's nothing really to to do or and unfortunately this is closer to real hardware if several things right at the same time to the memory uh same memory location some arbitrary nonsense happens one of them one of the rights wins and if you're unlucky and you're not writing an atomic thing it might even happen that you have a chimera of of the two values half of the first and half of the second value so this is uh unfortune unfortunately closest to uh

12:52 Concurrent Read and Concurrent Writes

13:57 to actual cpus and memory systems but there are ways around synchronization steps around in software to to mitigate that but it's um it's fairly inconvenient to program as you might know if you have experience with that so these are these are sometimes called race conditions uh which is

14:15 Race Conditions

14:24 the big plague of all parallel programming and concurrent programming this is what programmers try to avoid at all costs and it's hard to do in theory we mostly work on the crew pram so we don't allow concurrent write access this might seem a bit restrictive but it really means we restrict the algorithms that we allow and if you look at the practical solutions for for concurrent programming they actually try to do software tricks to come closer to this so it's a reasonable decision to focus on this one and it means we have to take care in our algorithms that we never write to the same memory cell at the same time with different processing elements

15:13 all right uh let me check if there's any questions not at the moment um good uh if you do have questions uh let me let me know so we defined how the machine works like we defined what a pram is and how programs can execute at least at least on a high level of abstraction what's missing is the execution cost of such a program and this used to be very simple we said in the ram that the running time is just the number of steps that we execute now in the pram this is a bit more complicated because we have these parallel uh executions so we have to be a little more concrete a bit a bit more detailed and there's now three three things space is same as before it's the the total amount of main memory that we use

16:10 time here in is meant as parallel time or make span if you want sometimes also called depth that's the number of time steps till all parallel uh processing elements finish so it's the maximum over all the running times of all threats if you want right that's closest to the wall clock time you as a user have to wait for the algorithm to finish

16:37 and a new parameter is work that's the total number of instructions executed on all processing elements if you're if you're just looking at time and space then work looks less interesting but it will become interesting for two reasons

16:54 one because we don't usually have a billion of processors around and then work will become important and the second thing is work might be seen as proportional to the consumed energy and you do want energy efficient algorithms these days so just going parallel indefinitely and duplicating the work many times is not acceptable so all three are um are important and we have to balance them out by choosing appropriate algorithms the holy grail in prm algorithms what people try to achieve is of course minimal time well and space but maybe that's a bit less of a focus but also you want that work of your parallel algorithm is no worse than the running time of the best sequential algorithm okay

17:54 the running time of the best sequential algorithm for sequential algorithms work in time is the same right this is maybe a obvious comment so you you try to find something that doesn't produce that doesn't do much more work overall at least same theta class

18:21 then we call an algorithm work efficient a parallel algorithm is work efficient if it's in the same theta class as the best sequential in terms of work but at the same time it hopefully achieves a good speed up in terms of parallel computation time okay i want to briefly see if you are following along on this so

18:47 a little innocent question is every computational problem solvable with a work efficient algorithm let's see what you think about this i'd love to see a couple more people answer on this before i give it

19:40 give it away 23 24. let's do it till 30 again same as before come on guys 26 we can do more okay well the time's running up so maybe i'll just show them now uh it's roughly roughly half half

20:18 and uh so you will be interested to see the right answer and uh the answer is yes because um whenever i take the sequential algorithm we have if i have a sequential algorithm work efficient is always with respect to a good sequential algorithm if i take the same sequential algorithm and just declare this is my parallel algorithm even though it only uses one thread that is work efficient it's just a crappy parallel algorithm because it doesn't achieve any speed up but it's work efficient and you can call it parallel it's just um calling it parallel even though it doesn't it's a it's a crappy palette algorithm time is bad span is bad but uh it's work efficient okay let's move on

21:16 to the last part of of this introduction on the pram uh that's a criticism that i'm i'm sure many of you had in mind when i presented this uh we don't have a billion of processors just because we're sorting a billion integers so why should i care for this a weird measure of running time span and work and the reason is that you can always simulate an algorithm that for the pram on uh a particular machine that has a given number of processors p and then what you achieve is running time t plus w of p so t is the span of the parallel algorithm and w is its work then the actual time you get on this machine with p processors is t plus w divided by p and the work stays the same up to constant factors and so this really means i want to highlight this again this really means that work is important in theory the time is just t just the span but this assumes you have an arbitrary number of processors and you usually don't and if you actually simulate this on a machine with p processors you get this uh additional contribution w over p

22:47 i think um i want to briefly sketch how this works it's it's a very simple construction as it says here it's it's really just round rubbing round robin simulating uh the pe's

23:03 and so um let's suppose i have and that one has potentially very many um many many uh processing elements so time proceeds top down and now here i have uh i don't know p e 0 p e 1

23:45 and there can be many up to p in each time step each of these executes one uh one step maybe i can put myself over here that's time step one time step two we have another step but maybe um i think the the dots make this inconvenient let's let's keep it concrete and maybe add one more

24:18 so uh three and four maybe they all execute something in the first two time steps in the next two it could be that some of them are actually dormant and they don't do anything

24:36 and maybe next time step there's it's even more restricted only one is doing something and then again they all join and do something useful so this is how the time progresses that's the parallel algorithm so what we would have here is time is 5 because we have five time steps and the work is well whatever you have to count so that's 10 15 i guess 19 up to your instructor not being able to count and how do we do this if we have a machine with say just three processing elements

24:51 The Parallel Algorithm

25:26 Round Robin Simulation

25:28 what we do is a round robin simulation so in the first time step we use our three processors that we do have to simulate the first round of the black ones but then we need an additional time step to simulate those two so these are the first three we just schedule them in the first time step and the remaining two follow in the next time step let me do the same thing for the red ones and again we need two time steps here to simulate that for the blue ones we can actually fit them all in because there's just three and then the green is just a single one and then the purple again needs two time steps because they're all involved

26:20 now this clearly got more expensive but how how much more time do we really need we need the original time step um let's see if i'm i'm running slightly out of colors here but i'll try to manage for the the original means we can essentially pay for the first step of each color here by uh saying we needed that many steps already in the in the pram execution so that's the the contribution of of that part and then the w divided by p pays for all the other ones

27:05 and so we have to make sure that these steps don't sum up to more than w over p how many blue steps can we have well we always make sure that these are entirely full

27:49 up to the last round per time step per p ram step so we get this plus one as an upper bound because we make um we make them full as long as we can but then we add one more for each um sorry this is a t for it's one per original time step

28:24 so how many how many steps of the blue types do we have here it's it's too small an example to to show this but in general if this would have been a much larger number of processors you would pay the first three by charging to the green part and then you would have as many as there are but divided by p by three many more steps plus one for the last one because there could be an individual job left over if you sum this up over all the the t time steps you get a contribution in total of w over p plus t for these and uh that extra um amount of t just vanishes in the big o notation

29:12 so uh what this means is if we're given uh work and span for an algorithm we can actually estimate how long it would take to run it on a given computer with a given number of processors just from those two numbers and we could even transform such an algorithm in one into one that runs on such a machine by essentially simulating this proof idea in an algorithm

29:51 that concludes this part on on the model for parallel computation and looking at the time i won't have time to introduce the next topic so we continue with that

30:10 okay thanks a lot um i think i'll have to skip the zoom social but we can uh resume that tomorrow and i'll leave the live stream open for another minute or so if you have questions then please put them in the q a now uh also the canvas wire back channel if you wish

30:36 and tomorrow we'll continue uh well we'll continue with some actual parallel algorithms uh first for some um toy problems if you want uh it's a building block that doesn't seem very useful if you first see it but then we'll see it has ample uses to parallelize our sorting algorithms and that then will bring um

31:04 our sorting algorithm chapter to a close there's one question [Music] it looks like you didn't use 19 you use w equals five well here the work is the total number of these little boxes that's the total work that we pay and that's 19 here um

31:47 if i take the i mean okay we can we can compute this this formula but uh it ignores constant factors so i think this might be uh wait it it looks far off it's also an upper bound uh this bound is

32:01 if you choose a if you always have p steps that are completely full and well we have two p's and now we reduce it to a smaller p so that's on the that's the p ram

32:29 say we use i don't know capital p here and small p here the worst occurs if this p divided little p uh if that if that large p is the small p and there's just one left over

32:57 k times the small p plus one then you always get k full steps where you use p so you get this k times and then there's a single one left alone

33:21 then the the green steps is the first of these and we get k minus one of the blue plus one so it's in total again k of the blue steps and so that works out to be sorry that works out to be exactly w

33:52 would be the time times p we use that many processors all the time is that that's a different p unfortunately i would have to use that fact so we packet at the beginning it's uh it's more useful to keep it like that

34:27 the w over p and then you really get the number of blue steps is w over p and the number of green steps is t so the example was a bit too small um to see the full uh contribution that the blue part can have i don't know if that