Video 5-1: §5.1 Elementary parallel string matching

0:00 Intro

0:03 in the next unit unit 5 where i want to look at how to parallelize string matching we've seen a handful of different algorithms that can solve this problem in the sequential setting and some of you might have seen these algorithms before they're sometimes done in undergraduate classes as well but quite definitely not the parallel string matching algorithms and we also want to use this as another little playground where we can practice our knowledge on on parallel algorithms so let's get started with this here's the outline i want to talk a little bit of uh about just what you can get with parallelizing string matching in a very very simplistic way and it turns out this is already leading us a certain way but leaves leaves some questions open and we'll see that the current methods that we have only get us so far um so we need a new idea and this is a periodicity which leads to string matching by duals we might not get to the last section today but i think we should should be able to manage uh part one and two for for today so let's try to parallelize string matching remember um parallelization we're on this pram model we have parallel processing elements and we need something where there's no

1:40 data dependencies between one step and the next step then we can actually instead of running these uh one after the other we can run them in parallel so uh let's look at what what the status is for for string matching uh we've seen quite a few different methods but uh if you look at them all uh go through them again um maybe uh offline they all seem inherently sequential

1:51 Parallelizing string matching

2:09 and effectively maybe the brute force method out of the outside they all really became efficient by using knowledge from the the step just before and that's that's really a game stopper for for parallelism so uh what can we do about this and um how far can we get with with simple tricks that is what i want to look in this first subsection

2:41 it's more natural here to actually look at the problem of finding all occurrences of a pattern in the text it's more natural in the parallel setting because uh finding the first occurrence means you have to communicate much more with the different processing elements and clearly if you find all occurrences you can easily find the first one afterwards um it turns out that it's it's just more natural for the algorithms so we'll we'll switch gears here and look at how to find all occurrences of the pattern in the text you can imagine we just produce an output a bit array where it has the same length and as the text and we just set that bit array to 1 if an occurrence of the pattern starts at that position and a 0 otherwise that's an easy way to to find this and then we can use well prefix sums and binary search to find the first occurrence or or even smarter techniques

3:48 also um unlike in the previous section i do want to assume that the pattern is shorter than the text here it's always easy to test for this and if the pattern is longer than the text come on we don't expect any occurrences okay so uh that's the setup now um what can we do without um without trying too hard

4:09 Embarrassingly Parallel

4:12 uh there's a notion i want to introduce and that is embarrassingly parallel this is um well it's a piece of terminology that's maybe again not that's uh not great but this is the term that stuck and people use it so you should know it intuitively embarrassingly parallel means that a problem can be split into many small subtasks and you can do this easily and they're all independent of each other the solution might be depending on the solutions for all of the little subtasks but usually we assume that combining these solutions is easy a very typical very simple example of an embarrassingly parallel problem is to sum two large matrices of numbers or two large vectors for that for that matter doesn't make a difference the sum of a matrix is just the component by sum of all the different entries so uh every every number in the output can be computed by one processing element by summing up two numbers from the two input matrices and that's it right that's uh constant time um work efficient parallel algorithm for summing two matrices completely trivial and uh that's why people call it embarrassingly parallel it's uh it's so easy to parallelize that you already feel him almost feel embarrassed many problems are not embarrassingly parallel or at least

5:48 not in their entirety or not at first sight and one example that we've seen is sorting the entire problem rearranging a list it doesn't seem to allow this immediate splitting into into subproblems so it seems it is really not embarrassingly parallel but some some parts of it are embarrassingly parallel we we use this in quick sort comparing all the elements with the pivots and noting the results that is embarrassingly parallel because you can do it in parallel for all the different positions in the array so

6:32 i would like to ask you about your gut feeling do you think um that the string matching problem is embarrassingly parallel i'm asking this here knowing that you can't really know so this is i haven't told you about this we've just started thinking about this um so maybe it's almost like um asking you to randomly guess but maybe you have a gut feeling and we'll we'll revisit this question uh later to see um how well you you worry about this i'll just um leave the question open

7:21 maybe i'll wait a sec and lock the voting then that's more fun and i'll just ask the question a second time and then we can compare the votes so i'm waiting for the magic 25 votes again um we currently have this uh 19 and uh come on guys just first first thoughts what do you think is it easy to parallelize string matching or is it hard or does it matter what the parameters are like

7:58 give it a shot nothing bad happens and it's anonymous anyways all right so um let's lock the vote in um i won't comment on this now let's uh continue

8:19 so to be embarrassingly parallel we have to identify sub problems right and a natural thing in string matching is to say checking one guess is a sub problem and um that that's a suitable thing we can find all the matches by checking all the guesses that's for sure so uh that looks reasonable and an easy thing to do is yeah let's do all the guesses so uh all

8:23 Elementary parallel string matching

8:55 and just uh run in parallel for each of the guesses compare if the text at this position matches the pattern if we do this with n processors or n processing elements each checking sequentially if there is a if there is a match then we need theta m parallel time and we need theta of n times m parallel um total work and this this will be um the main shortcoming of this first approach but i do want to comment on on the time we can actually improve the time even to constant on this weird model where you can concurrently write to cells and have some um even the weakest way of resolving conflicts is fine and you will actually do this in the tutorials you will find solutions to these two tasks even though it's um it's it's written in a different way or it's post in a different way but uh you will you will do this and um

10:04 yep so you can do the check itself also in parallel and thus improve the time both of these will not improve the work the work remains at theta n times m and that's not that's not that great

10:19 uh we can do something different an entirely different idea that will work out to be work efficient but the the parallel time in this case is is stuck at theta m so it's not so clear how how good that is if m is really big and the idea here is to use the efficient sequential methods that we had now if you want something work efficient and you need roughly m time to check a single check there's no way you can you you make this work by doing end checks you have to reduce the number of checks to n divided by m if you want anything with linear work with work in well length of the text

11:14 i guess strictly speaking this is uh okay i'm assuming m is at most n that's um yeah we do need also theta m work but that's the same in in theta classes okay what we do is we divide the text into overlapping blocks so we double cover every position we cover this like this and then the odd ones cover it here and we cover it here all right so this is uh these are the little blocks that we use and now uh why do we do this and the blocks have two m characters so whenever there is a pattern uh occurrence here because we double cover everything and the blocks are twice the size we always find one block where the occurrence lies entirely within that block that is the important part and that means we can individually in each of these blocks use our sequential method to finding any occurrence in this in this block and then combine the output by writing the results to an output array or something similar okay so you divide it into blocks of that that many blocks each block has length 2m or m in in we ignore the constant factors world and uh running in an efficient sequential method for example kmp it needs n plus m time but n now is 2m

12:49 so the total time is is theta m so that's why we get linear work and the running time the parallel running time is theta m okay now i want to ask this same question again and let's see if you come to a different conclusion now or not and more importantly let's see if you followed the presentation and can can make sense of it

13:03 Clicker Question

13:47 okay i'm waiting for the magic 25 all right yep looks good um yeah you're absolutely right um the the string matching problem is embarrassingly parallel in this sense that you can find many small independent sub-problems only if the pattern is small and the reason is just if the subtasks are checking one guess then that guess you only have

14:46 you only have n minus m of these and um if m is roughly the same as n then there's not so many sub tasks whereas each of the subtasks is still a fairly fairly big problem but if the pattern is very small we don't really have to work hard if the pattern is really small it might be good enough to just check all the guesses in parallel it's not work efficient the way i suggested it but if the patterns are really really small we might not care so much

15:18 Elementary parallel matching - Discussion

15:21 that brings me to the conclusion of this elementary sessions elementary algorithms they're very simple they're conceptually simple and they're also easy to code up the most complicated thing might be that they rely on kmp but you know kmp is is uh maybe a complicated understand but not hard to implement

15:48 um yeah if um if we're changing models and uh not look at a a shared memory parallel machine but a distributed setting we could distribute parts of the text so um the sub-problems are independent even in the sense that they don't have to look at the same positions in the data that's that's another convenient feature but we only really get a great parallel speed up if m is small or if we bite the bullet and use this work inefficient method even then uh it's um you know if if we simulate the work span model on an actual machine with not 10 000 of course then the extra work does hurt so we we definitely want a more work efficient solution unless the pattern is really really small

16:51 yeah uh one thing we're stuck with seems to be the matching process um the simple way to parallelize it um maybe uh this is worth going back so there's there's two two problems with the current solutions this one's achieves great work but we cannot easily we it seems impossible to parallelize the k and p part here so we're stuck with um linear time in the length of the pattern here the time can be improved by doing these tricks to do the check in parallel but we're still stuck with the uh with the worst case n times m work and for a reasonable number of processors that will not help as much