Video 5-1: §5.1 Elementary parallel string matching

0:00 Introduction

0:02 all right then welcome back to comfy physics another time a new unit fresh topic even though quite related to the previous unit we'll still talk about string matching but this time how to do this in parallel and

0:25 this will be a relatively short unit it just gives you another kind of flavor of string matching and a new perspective on it and will turn out to be a second somewhat illustrative problem to see how parallel algorithms work for this okay without further ado do what we'll do is see some parallelization strategies that indeed work for a whole class of fairly simple problems

0:56 and we'll identify what cannot possibly be sped up further in some cases um so again these two things are are going beyond just string matching but it's a nice way to illustrate them and then there's a concrete new method that you haven't seen there's another string matching method which is particularly suited for for parallel execution

1:18 Parallel string matching

1:24 so um we have seen quite a few string matching methods in unit four and uh they were more or less efficient apart from the brute force method but all except the brute force method really gained their efficiency from building on the knowledge of the previous the previous guess right the brute voice method was kind of oblivious for each position in the text it started from scratch but all the others what we were doing in many different ways was trying to gain advantage from what we've already learned in the previous position and take that knowledge to the next position in some way or another sliding forth and back and and all these things now if you think about string matching from a parallel perspective this sounds exactly like poison what we need for parallelization is that things are data independent that the next computational step does not depend on the data or the result of the previous computational step and here we did exactly the opposite so it seems like for for parallel string matching the sequential methods are worse than what we had before

2:42 okay someone posted on campus wires the live stream working fine okay the app is a bit slow i'll continue with the parallelized string matching in a second looks like it's sorted for now if not you can still use the slider q a if you want

3:18 all right back to string matching um it looks like all the effort we spend on making the sequential methods faster is to the detriment of parallelizability and so it looks like we might need new ideas we're turning this into parallel

3:37 i want to take one modification to the problem just because from a parallel perspective this is much more natural string matching in this unit will mean we want to find all occurrences of the pattern in the text just if you think about it finding the first occurrence would necessarily mean some synchronization step after the parallelizing after a per in parallel finding all the occurrences and then it's it's just an additional step after this uh so it's kind of more natural to stay with all the occurrences if you want you can still find the first afterwards but it seems in parallel not to make much uh there's not much you can gain from the fact that you want to find just one whereas in sequential it was kind of natural to stop out the first uh we'll also assume that the pattern is shorter than the text as before otherwise you don't have to do much

4:33 Elementary parallelization

4:36 i want to look first at some elementary tricks and this is the part that goes beyond string matching it's something that we haven't talked about in the sorting chapter because we were deeply buried into getting sorting methods fast but in a way let's start rethinking parallelization from scratch and try to find what is easily doable and so there's this notion of an embarrassingly parallel problem slightly cute term uh that just means it's a problem that's so easy to parallelize you shouldn't even be very proud of doing it it's embarrassingly parallel it's very easy to break into many small subtasks and they can all be solved independently of each other i left the definition deliberately vague there's no quantitative notions in there because i think the term is is more of an idea or an abstract concept than a concrete mathematical definition but a typical example could be the sum of two matrices so you have uh two matrices with floating point numbers you want to add them up well how does that work with matrices in the outcome every entry is just the sum of the two corresponding entries so you could assign one processor at least on the conceptual level to each outcome element and it just gets the two elements from the input matrices and

5:57 adds them up that's n squared if n is the size of the matrix say it's a square matrix n squared little tasks and they're all independent right that's embarrassingly parallel in its essence then matrix multiplication is somewhere in between right the individual tasks um they there's some potential overlap but it's still independent enough it's over a little more effort but you can still in a sense independently compute each of the each of the outputs if you wanted

6:34 and if you can do this that's the best case for parallelization because remember brent's principle you can in a sense just schedule all those little tasks on the processor you really have one after the other

6:48 the other problem we've seen and looked at from the parallel perspective sorting is is actually not embarrassingly parallel it's not really clear how in sorting you would break some the whole task of sorting the entire list into small little tasks that are independent but if you look at our algorithms that we that we designed there are subtasks that are of this type for example the partitioning step in in a quick sort where we compare all elements with the pivot element that's a task that every element's outcome compared to the pivot is independent of the others so you can do this completely in parallel and that's exactly what we did

7:32 now an interesting question is how about our nice embarrassingly about our stream matching problem is this embarrassingly parallel that was sorry wrong direction and for this question i haven't really told you enough or we haven't covered this yet so there's no way you can know other than your intuition or maybe you have seen it before but i want to ask this question now and later compare and ask it again just what do you think um what's true for the string matching problem

8:42 we had 30 votes for the last question and we're at 30 now well 31 indeed okay three two one and let me lock this one uh so you see the results are are different um okay i can show you the correct one here and then switch back to this one um

9:07 Subproblems

9:17 let's discuss what's correct later after i told you what could be sub problems in in string matching a natural candidate is to take each of the guesses as one subproblem if if you think about it we want to find all occurrences every position in the text could be the start of an occurrence so we could decide we could say each each guess is one sub problem and the task of the sub subproblem is to check if the guess is a match now that's great because these are indeed independent right

10:01 i can try to take advantage of learning from what the outcome was in one guess and apply that to another one but i don't have to they're in essentially in essence they're independent and so i could do all guesses in parallel and that's not that's not the crappiest way to do it let's put it this way it's also not the final answer but let's first see what we can do if you assign each guest one processor and that just sequentially checks for all the characters in the worst case it has to check m characters if these are all matches or all near matches so you would need m time parallel time for this for the matches and you would need as many processors as there are guesses so n minus m right and that's that's what's down here uh so the work is n minus m the number of guesses times m and that's the same across these other ideas it's just the parallel time that we can slightly improve and here it actually depends on the details of the machine

11:11 so you should have seen the parallel and in the tutorials or you're doing this this week but i think you've you've seen this last week haven't you okay some nods some definedly denying so you can you can look this up

11:38 checking whether gas is a match is really checking if all these characters match and then it's a it's a match if if and only if all the characters match so that's a big and is this equal and is this legal and is this equal and is this equal so after after the character comparisons it's the same problem as computing and of an array in parallel all the bitwise end of all the bits in in a in a bit array and you've seen how to do this in in log m time on a crew ram and in constant time if you can actually do concurrent writes and you can even have this this strict version of conflict resolutions so that's all i'll need so the parallel time is really good it's constant it's the best you could hope for but remember again brent's principle you don't usually have as many processes as the text is long so you also have to take the work into account and this is essentially n times m as the brute force method so we know there are better sequential methods this method will not be work efficient all right so what can we do we can be slightly smarter by saying let's try to take advantage of the fast sequential methods that we have

12:45 Solution

12:54 and so a way you can do this here is you divide the text into blocks and it's important that these are not just m long but 2m you will see that they're they're overlapping

13:23 and then the first block is this part the second block would be this string and then the third part this thing and so forth and now you're finding inside of each of the blocks you use a fast sequential algorithm so you use a sequential method like kmp say inside each of the blocks to find all the matches of the pattern inside the block now the the time for this will be essentially linear in m because both this snippet of the text and the pattern are length m up to some constant factors so you need you need that in parallel time now have you found all the matches by doing this

14:15 so suppose there is a match somewhere in the text say here it won't be found in the first red one because it only contains a prefix of p it won't be found in the third but there is this second that overlaps and then we know that this occurrence is fully within this red segment so it will be found in the second block if an occurrence is exactly aligned with one of these blocks it'll be found twice uh if you want um you can be you can try to be smart and avoid that case by

15:00 checking the outcomes i guess is the easiest it won't only be it will only be reported in two blocks in this and in this so it might be enough to just uh avoid that i wonder if it's enough to just make the blocks to m minus one long and then we don't have the problem

15:19 then you don't catch all overlaps potentially uh that's a mind that's a detail that you can solve either way either filter out the the duplicates or try to avoid them up front what we achieve with this simple method is parallel time m

15:39 as us here but we've seen you can do better the positive side is the work is efficient because um this comes down to to n times m to n divided m times m that's the number of blocks right and divided by m with a factor of two that is is emitted in the theta and each of the blocks takes m work so the total work is is linear in n remember we used to say we used to write theta n plus m for the sequential methods but with the assumption that m is at most n

16:20 we know that is the same as as linear in n so why did we obsess with writing this like that in the previous in the previous unit the thing is that if you pre-process the pattern you might apply the same pre-pressed pattern to several texts and then maybe you don't know at the time of pre-processing the pattern how long the text will be so you might already have spent the time linear in m and then you discover oh the text that someone's giving you is actually shorter and you wouldn't have had to do anything but it's already done that's why in the last unit i was a bit more careful and said in general whatever n and m are the the time will be n plus m here i'm a bit more sloppy and say let's only look at the case we're given the text the pattern at the same time and if the pattern is longer than the text we don't bother to do anything and we have a way to check the length and somehow without iterating through the pattern and the only interesting case is when the pattern is shorter than the text and then these are the same

17:28 so that last part is is a work efficient method but it's it's not perfect in terms of the parallel time right and so um if i were to ask you the same question again

17:47 i'll open a fresh copy so you can see you can change your vote and we can keep the old result i'll wait till till we have 30 even though the picture is is fairly clear now okay

18:28 if you were quick last time you would have seen this answer anyway so why is why is it um in this sense embarrassingly parallel only if the text is much much longer than the pattern in that case you can use this second method and break the text into these blocks of length 2m and can use a work efficient method and still have an efficient parallelized method fairly efficient whereas if if the pattern and the text are roughly the same length there's not so much you can do even even these more fancy methods they look like the parallel time is is decent but then the work is so big so unless you have many many processors you won't really have much of an advantage and for this work efficient method down here um if the pattern and the the text are roughly the same length it doesn't really do anything it falls back to the sequential method

19:34 Wrapup

19:37 all right so let's wrap up what we've seen so far uh the elementary methods are simple and that's always useful it's always a good thing to have we could even run them not on a on a shared memory machine but on a distributed machine where on a distributed compute cluster or something like this where each compute node only has a portion of the text because the problem is is local in the sense you only need a segment of the text that's roughly as long as the pattern you could still do this and the simple methods would nicely work with that but we only really get a speed up if the pattern is quite short now what would we like to improve upon this what can we do on top of that

20:28 it would be nice to have work efficient methods but then improve the parallel time so we get better speed up and the only way to get that is to get at the matching part somehow we have to parallelize the the matching process the idea of breaking the text into little chunks of roughly size m that looks useful but unless we parallelize that step as well we will be stuck with parallel time m so it looks like we need some new ideas at least with just black box puzzling together either the brute force method or existing sequential methods we won't break this this m-time barrier and that's what we'll look at next