Video 7-1: §7.1 Parallel computation, PRAM

0:02 so once more welcome back to efficient algorithms comp 526 um we'll look at the new unit branching out a bit from the previous topics this time we'll look at parallel algorithms it's a little detour in into this world of speeding up algorithms further by using uh multiple cores or even uh more fancy machines um I'll show you some some concrete models of how to do that but live at a fairly High abstract uh level of abstraction um in this unit but I think the the core ideas shine through and software Frameworks are catching up to come to that high level so we're uh we're getting closer to what programming uh looks like towards the end um but uh in case of doubt I'll show you the the cleaner algorithms as opposed to the more Messy implementations as we still have them at the

1:01 moment the learning outcomes therefore are to know strategies to parallelize algorithmic Solutions and problems um not so much implementing them in practice I'll comment on the gaps there um you should also know when things are not possible to speed up by parallelism um I want you to know this concrete model that we'll look at uh just to make again make these impossibility results uh formal we need a machine model uh we'll look at how to analyze things on this model and then a few concrete examples of parallel methods uh we'll see some some fairly simple ones and then the culmination of it at the end will be the the Sorting methods in

1:49 parallel and we'll start just looking at the models for today what is parallel computation um I've asked you uh already what uh what your prior experience would that topic is uh so I should maybe clarify on the the content on the the terminology there a bit so uh what what's what's listed here is concurrent programming that's the model of having several things in a program be done independently and potentially at the same time even though they might still be executed in sequence one famous example is python it supports concurrent programming but because of the global interpreter lock for those of you who care about the technical details it can't actually do real parallelism unless you have a c extension so in a way everything in Python is still sequential but you can program concurrently so concurrent means you program so that the program could be run in parallel it's a programming model rather than uh an actual mode of execution and yeah you often have to do this still with with um fairly clumsy tools explicitly calling threats or if you have um a better framework then uh things get a bit more

3:13 convenient and so most people haven't done this um which doesn't matter much for this module I'll show you the the clean abstract world and if you ever dive into uh stick your toe into the the Practical side of things um the longer you wait the better it gets um things improv there a bit why do we want parallel computation in the first place well it's simple money can't buy you everything uh but it can buy you more computers so if you can parallel your problem even if it gets bigger if it can be parallelized you can solve it by putting enough money in uh with some limitations of course but uh still uh often parallelization is is the main route to scalability

4:01 there's two kinds of computers that are usually considered um for parallel computation and what we'll focus on is the shared memory parallel computer so you should think of one big piece of memory and it's all in one big box in a in a computer but there's different CPUs um that can work at the same time and they can all talk to the memory independently but they see the same memory so the main the main way how they uh communicate is by putting certain values at specific places in main memory where they uh have a convention that this is used for communication so um we call these individual CPUs processing elements just to be more generic because they don't necessarily have to be full CPUs and this for uh just to keep the the terminology a bit more generic uh but you can think of them as different different CPUs working in parallel all working on the same memory uh you can have these in in big servers you can have uh hundreds of CPUs and maybe terabytes of main memory if you want to spend the money on it so they can get fairly big and even if the problem uh is is fairly large you can maybe solve it uh in a single box

5:30 and if that's possible it's it's usually going to be orders of magnitudes faster then well the other big option you have is essentially a cluster of computers uh there you would have uh individual boxes each with their memory um and and a CPU or several CPUs and they talk to their own memory so you need a secondary layer of communication usually some n Network it can be fairly fast but most of the time these messages via the network are the bottleneck in the computation then so for us this is uh just to give you context um we'll not really talk about these we'll mostly live in in this scenario uh where you can solve problems really fast and the main bottleneck is still the computation not so much just

6:29 communication so here's our formal Machine model for this and it's based lo and behold on the model we already have the ram model from unit one uh the main extension now is the ram had this one well it should continue uh the ram had this one long piece of memory that actually is unbounded and you had a single CPU that can do operations now you have several CPUs the picture will look essentially the same as before uh but each of these is a little Random Access

7:20 memory so they each can access uh memory in the same way the same operations everything the same as before um but they're also uh numbered so that's Z one and two so they have an ID and you can use this ID in in programming them otherwise they're like before they also have a word size that's a second parameter and we have a a third parameter next to input size and word size which is p the number of these processing elements or the number of of

7:54 rams now they each run a ram style program the same kind of programs we've used before and um will allow our elves like before we'll write pseudo code instead of actual primitive instructions and we'll extend the pseudo code with instructions that can run in parallel I'll show you examples on this uh next week um but I want to stress one one important point the Assumption here is that all of those run in lock step each of the okay my picture is gone um well let me draw right on this slide then each of these Rams does one instruction in one time step and then they all uh come come together and wait for the next clock tick so there's one clock for all of these uh Rams they have the same they have a synchronous timer that's a it's a feature of this model that makes programming easier it's a feature that makes it less realistic because most machines that we can build don't work exactly like this they have separate clocks and they can even run at different speeds uh but that also means a lot more messy consequences so um we'll ignore that here we'll uh design algorithms with this slight simplification but you can uh you can translate much of it uh nevertheless if

9:15 you don't rely on this on this feature too heavily I'll comment on that again later when when we look at specific examples so in a way it's the model we had before but one long big memory that they all share plus they run in lock step they all do one step then they all uh write back their results to memory then they do the next step and so on in particular if they all access memory um we uh they all happen to do this at the very same

9:54 time because they access the same memory we have to somehow say what happens if several people access the memory at the same time uh and there's there's different um conventions or different versions of this Pam model so p is the parallel Random Access machine and then you have certain prefixes before that that tell you how memory accesses are are handled the most restrictive one says exclusive read exclusive write you as a programmer have to guarantee that in any time step for any input only ever a single processing element is accessing each position in memory and the assumption is if that is ever violated the machine just explodes and you're you're to blame so that model is very strict on the other hand if an algorithm works for that model it works for any of the others and it will never cause problems so if you can solve a problem like that with that constraint that's great uh this Con this this uh restriction is a bit overly uh strong we don't really need that the typical stand standard assumption is the crew Ram concurrent read and exclusive right because it doesn't matter so much if several people read the same memory cell there's no inconsistency that can arise from that but we still insist that any

11:13 right AIS is from a single processing element only and the last one you can try to also give give that up you allow concurrent rights but now we're in danger territory because we have to say what happens um we need a a rule for for uh resolving the right conflicts and there's different further variations one option could be okay it's fine if several people try to write to the same location but if they do they have to write the same value and again it's up to you programmer if you don't make sure that that happens just the machine explodes and you're to blame uh or program crashes or something like that uh so it's up to you but if you guarantee that the hardware says fine nothing really happens they all write the same value so no consist inconsistencies um or the machine could say I allow this but um you have to deal with the consequences um you can you can do anything but which value gets written to memory is unspecified and your program has to be correct no matter which one wins that's another option uh guess what actual Hardware does it's much much closer to this one and it gets worse because they can reorder statements and it gets worse because things are not in lock step so

12:35 many of the problems you're facing as a programmer when you're implementing things and try to do concurrent programming is dealing with the limitations that Hardware was designed to be very fast and offload a lot of the responsibility on you now that said we'll mostly look at these so um we'll assume that our programs have to make sure they don't concurrently right to the same place and that's a good way to program even those machines that allow arbitrary rights because uh often it's it's really tricky to get those

13:24 right uh let me show you this one and then um we'll finish for today uh every Pro every model of a machine has to tell you what is the cost of executing things for the standard word Ram it was simple just the number of steps was the total cost the time and maybe we were also looking at the total space how how many memory cells did you need now time has become a little more tricky now because we have many many processors it's still not so hard because they run a lock step remember so we can still Define time as the number of times steps until all of the processing elements finish and uh this is also called sometimes uh sometimes called the depth or the Span in particular span is is widely uh widely used uh we'll we'll come back to those terms so that's the time of a pamm program is the number of time steps until all the processing elements say they're done uh By the time by the way we don't assume any limit on the number of processors so it's not like okay my phone has eight processors great so that's all I can ever use no no no Pam says uh you can have as many it's like the Ram uh like the memory in in the ram

14:39 model it's unbounded you get as many as you wish for and we'll come back to that assumption there's a second second uh cost measure though that now becomes relevant which is the product of the number of processors and the time basically or the span that's the total number of instructions across all the processing elements if you want you can think of this as something like an energy cost okay it's great that you can fire up as many processors as you wish but you still have to power them somehow um and we'll also tackle this

15:16 assumption so we have three things to look at now and um we'll try to minimize the time for the span but we'll also have to keep work in in check