Video 7-3: §7.2 Parallel string matching

0:00 Embarrassingly parallel

0:02 in the next section we'll look at some simple first parallel algorithms and we'll look at the string matching problem which you know from from unit 4 but this time we'll look at it from the parallelization angle and it will turn out to be a relatively uh easy problem and um what I want to introduce here is is a term that's uh maybe a bit bit uh bit funny but uh people kind of stuck with it um call problems embarrassingly par parallel if they are very easy to parallelize and slightly more detailed what we mean by that is uh the overall problem can without much effort essentially immediately be split into many small subtasks and each of them can be solved independently of each other and the second part is important they have to be solvable independently because that means we can do them in parallel if there are any dependencies that one task needs the result of another one then parallel is m is tricky uh but in an embarrassingly parallel program or a problem uh that doesn't happen uh the tasks are all nice and independent and a prototypical example is summing up two matrices this maybe not such an exciting operation everyone's doing Matrix multiplies that's what machine learning inference is but uh if you just sum up

1:23 two matrices the sum of a matrix and another Matrix is the entrywise sum so so you can just compute each of the entries in the output separately by taking the respective entries of the input so that's a a prototypical embarrassingly parallel problem and you can write a simple algorithm for that that just does this this Loop over the output cells in

1:56 parallel in a way that's that's um almost by definition the best possible case for parallel comp computation we haven't talked about independence that much yet um but what what else could you speed up other than doing many many things all at the same time and the easiest uh for that is if they don't have anything to do with each other and they can just be done one after the other now not all problems are like that um sorting in a way is not really like that at least we haven't seen any way to easily break it into small problems uh there there many there may be parts of sorting that that are like this and we'll come back to that uh but if you take the problem as a whole it's not clear what would be a sub problem of sorting that you can you can solve independently of the others and um the overall problem is still solved by solving all the small problems so it's not always that

2:59 Parallel string matching

3:01 easy so we have two options now um what do you think is is the true uh card for for string matching I mentioned it's a relatively easy problem but

4:26 yeah I think we have roughly the number from before so let me uh let me share the results now and uh we'll come back to that I won't won't tell you yet uh let's have a look right let's think about it a bit so first of all of course we talked about this problem string matching before in detail ah sorry I'm back on the slides welcome back to the slides too uh we'll discuss the the question in a second we talked about string matching in detail now we've seen simple things like The Brute Force algorithm but that wasn't really uh wasn't really the most effective way to solve the problem and everything we've seen uh in particular things like the the can moris prad algorithm uh they have a somewhat inherently sequential component they became fast precisely by reusing the comparisons that we've just done and they were exactly trying what the Brute Force algorithm did not do well namely learn from the compar that they already already done in the past but in a way that's exactly what you cannot do in a parallel algorithm at least having these independent sub problems smells like uh the opposite so um what can we do um in another way to look at the problem there is some some independent

5:52 sub problems namely all the guesses in the terminology of unit 4 we can try to find uh for all different positions in the text whether or not there is a match of the

6:09 pattern um so here we we'll look at this this formulation where we find all occurrences um and uh that makes it a bit more natural here so we can take as one sub problem checking each of the

6:26 guesses so a simple algorithm that follows that approach would be like this so the first one is a a for Loop and it looks otherwise essentially like our Brute Force algorithm from unit 4 uh but I've added here an in parallel so that's the way uh how we program pram um the pram machines we can use four loops and say in parallel and what that means for the machine for this for running this pseudo code is assign each of the uh each of the uh values of I a different processing element and do the loop body in parallel okay it's a slick and short concise way to do this uh there's essentially also languages that do roughly that you have to pay more attention to details though but it it looks otherwise very similar so open MP is a a library for for C or C++ where you can use parallelism uh it has many pitfalls but that part is is easy and the rest of the algorithm is is like in the root force method so for each of those guesses we have to iterate through all of the

7:47 positions and we do all the checks and if we found a match then we report it and at this point you see it would be inconvenient to try to Now find out the earliest match so instead we we just report all the matches

8:10 algorithm uh it's it's okay from the perspective of span because instead of spending time linear in the length of the text which is usually much bigger than the pattern we uh just spend time proportional to the pattern even if we do it simply as as in here and we can actually speed this up further uh you'll do this into the tutorials so um instead of doing this simple Loop the way um so this this code uh has has that span because each of the iterations of the outer loop still has this inner loop but you can speed up the inner loop further at least if you allow certain concurrency on the accesses to memory but the big problem is the work uh because that's much more what than what we can can do in the sequential setting so here we have the product of M * the work for each Loop times the number of iterations and that's essentially like the brute force method now you could say ah forget about work span is great I don't care about work but remember Brand's theorem you you must care about work because you're not usually running on millions of processing elements you're running on a few dozen so the overall time would really be this Plus

9:30 that's divided by your number of processors and so if the work is almost like the sequential if the work divided by the number of processors is almost like the sequential running time you haven't gained anything from parallelizing it so that algorithm um is not that great at least it's not that great if m is not tiny right now we we can do better um we can instead of doing each guess individually we can uh break the text into blocks and use something smarter within the blocks so that's the first kind of General trick this kind of blocking technique will come up in in other examples uh and it's the first non-trivial technique as well uh to do better so the important bit is that the blocks are overlapping each of those has two M characters not just m but we start every M character so we we double cover the entire string that looks like this so we take the first 2 m and then we take the these two and these two right is uh looks like a brick wall uh all the way through now we can discuss why we do that in a second um but then for each of the blocks we again do things in parallel but then in each block we use a

10:01 Blocking and KMP optimization

11:05 a fancy method that we've learned about before we call our KMP algorithm on just the little block of the text and the pattern and we return whatever that returns so why do I need these overlapping blocks uh that for that maybe I want to make my picture a bit more accurate

11:35 I guess there's some boundary conditions at the end but you have to just fill it up so the lengths of the blocks are chosen to be 2 * m twice as long as the pattern so my pattern should be something like this roughly that length half of the black boxes now if I only had these this first row of boxes I wouldn't find the occurrence of this of this pattern here because it's not entirely within any of those blocks but if I double cover everything no matter where I try to hide my pattern there is one block where it's contained entirely in the middle at least all all M characters are covered in one of the blocks and so one of the calls to KMP must find that that occurrence and so we can uh report it from there it has the slight um the slight nuisance that if you're not careful with the blocks you might report a match twice um but if you chose them if you choose them like here so that they they never overlap in exactly M characters then uh it works

12:47 out so let's let's uh analyze a bit how well this works uh first of all we have to do this Loop the overall Loop n / M times roughly within big go the rounding goes away and inside of here how much time do we spend this is this is constant time and this one now you need to remember what the running time of KMP was it was or text of length n and a pattern of length M the running time of KMP is n plus M order n plus M so um

13:40 if our text has length n and the pattern has length [Music] M then uh that's the running time of KMP now what what is n and M in our case uh m is the same but then the text is only how long again it's one block 2 * m right yeah so that's that's still linear in m so each of the uh loop iterations has time M and how many iterations do I have and divided M so the overall uh running time is is linear in the total size of the text or the overall work sorry for the uh for the time for the span of the problem uh we do all of these in parallel so the span is determined by Just One of the loop iterations so it's just just this one that's what's written

14:53 algorithm uh I guess here it kind of depends well first of all uh for coming back to the question uh let me show it again I guess maybe now you uh you can tell uh I mean embarrassingly parallel means that we don't have to do the fancy KMP trick even and so we're bound to the uh simple method from before where we just do all the checks in parallel and then uh that's only really a good algorithm if uh if the text is much much longer than the pattern and uh for the KMP version here span m is okay if m is small if if M and N are roughly of the same length then we haven't gained anything then the parallel algorithm is not much faster if n and M are roughly the same nothing is one okay uh but if question okay okay yeah so uh the typical example of patter of string matching would assume that the pattern is much smaller than the text but

16:08 Advanced theoretical bounds

16:09 yeah so what can we say so far about string matching uh in parallel the methods I've shown you are fairly simple once you know KMP the code was just a few lines but these already work reasonably well I mean uh under the assumption that your pattern is is not enormously long but if the pattern is reasonably small compared to the T they give you a lot of speed up for parallelism um can you do better H and it turns out you can do better even if the pattern is long but it becomes a really tricky theoretical question so there's uh there's several barriers that you have to overcome um if you remember what KMP did it does a pre-processing step on the pattern and you have to speed that up as well or parallelize that to be better than than Theta M span uh and also the matching part when you uh when you try to find your your Curren is in a block that has to be sped up and parallelized and so it turns out this is uh this is a theoretical possibility on the pram but the algorithms are as far as I know not pra not not practically relevant and a bit beyond the scope of the of the module but as as in many occa

17:27 uh occasions before I'm I don't want to leave you with the impression that what we've we've seen is all there there is possible um you can do better um but it has it has it's much more complicated and it's not clear if it's gives you a speed up in practice uh but that doesn't necessarily uh stop the question from having a positive answer in the in the model so here's the just for reference the state-ofthe-art um as far as I know and then it depends on the model again you can do instead of M log M time so an exponential Improvement if you want to phrase it like that and if you have this concurrent rights then uh you can even speed up things further but again this is uh not part of the exam material it's just for or your curiosity and interest