Video 5-2: §5.2 Parallel string matching

0:04 in the next sub session um I want to look at the string matching problem again we've just covered a lot of algorithms for string matching in the last section but they were all sequential we didn't care about parallelism it turns out this is a a nice problem to get started

0:29 and the reason for that is uh that some problems are really easy to parallelize and we call those embarrassingly parallel it's a kind of acute term but um is one of those wake things again there's a way to split the algorithmic problem into small subtasks and each of these subtax subtasks must be computable solvable independent of all the others if a problem is like that you can just assign all the sub subtasks in parallel to different processing elements and then you get a huge speed up from the parallelism a typical example that's that's clearly like that is if you have two large matrices and you want to compute the sum I'm not talking about Matrix products for now if you just do the sum remember sum of matrices is just the element-wise sum so every element every uh entry in the output of this algorithm is depending on two things in the input and it's not talking to any of the other sub problems in a way matrix multiplication is is similar you can also compute those uh um in an independent way but the smarter algorithms for matrix multiplication don't do that they try to reuse some information whereas for the sum uh you there's nothing to be gained it's uh it's easy enough as it is

1:58 such an embarrassingly parallel algorithm uh comparison embarrassingly parallel problem is the best case for parallel algorithms then there's not much that you need to think about unfortunately most problems aren't like that and I think it's insightful to think about sorting again we've talked about that at length in the the unit before the last one we didn't care about parallelism at the time but if you think about this this this task of rearranging elements in the list into sorted order it's not so clear what an individual subtask would even be we had dividing conquer algorithms so they they started with breaking things in half and then that was sub tasks but uh it's it's really not so clear um how you can Define small subproblems that are also independent of each other we'll see that there are some parts are like this but you need to work your way around them is not obvious so sorting is not is not necessarily one example of such a problem how about string matching um

3:13 without telling you anything about the problem and how you potentially could solve this I will just ask the question now and we'll come back to that later foreign okay I will I'll wait till we have 40 or so and then I'll just lock the question this time for the pedagogical effect of looking at it later

4:30 so if you want to cast your vote do it in five four three two one and because the live stream is five seconds delayed as if it means so let me talk and Waffle around for a while three two one locked

4:49 all right we'll come back to it so it's an interesting case uh we've seen a lot of algorithms uh in a way all the algorithms for string matching that were particularly good according to the metric of unit 4. were exactly the ones that exploited maximally the knowledge from the previous step remember we had character comparisons was what we counted and we tried to not do redundant comparisons but by the the essence of a non-redundant comparison is one that we haven't seen and redundant was we built on the knowledge we have so it's kind of the opposite of this inherently or embarrassingly parallel it sounds like this is this is exactly not what you want to do so we might need different algorithms

5:44 before before we dive into the problem a bit more I want to rephrase it that makes it a little more natural and simple for a parallel algorithms it won't it won't at the end affect uh the vote that we've had but this makes it a little cleaner unit 4 reset string matching is find the first occurrence of the pattern in the text if there's one now I'll I'll say just report all and the reason is then we don't have to communicate between the processing elements to find out if we should answer no if if any of those solves a sub problem and doesn't find An Occurrence of the pattern they would have to ask all the others hey did you also not find a pattern and only if everyone says no no no then you can report no match to avoid us that hassle to spare us from from that hassle I'll just say everyone reports a match if they find one and if not the user will have to figure it out later that's a bit more natural in the parallel setting and then it's natural to Define sub problems as checking individual gases so uh we have we have some some way of defining sub problems that comes from from string matching and we could say that checking of one

7:00 gas is is a subtask so let's try the easy thing let's go back to the Brute Force algorithm for string matching I've copied this on the slide it's almost literally the same as what we had in the last unit what I added obviously is the red part I'll comment on on this type of parallel pseudo code in a second one thing that I took out was the sequential brute force method at the end had if none of the iterations returned a match then there was this return no match we don't do that here

7:45 so the type of code we write for these parallel algorithms will usually be a for Loop or something similarly like this and we just tack on this keyword in parallel which is supposed to mean all these iterations of the for Loop this inner part that's repeated many times sequentially we just go through all the different values of I but now if I rate if I write in parallel the understanding is we can do all of these each on a different processing element and the index the loop variable gives us the index of the processing element

8:26 this inherently requires that all the iterations of the loop body can be done independently if they cannot if they build on each other's computation and you don't and you don't pay attention that's your problem

8:41 this is similar to if you have programmed in openmp you may recognize that this is precisely one of the things that openmp can do for you and there's all sorts of caveats if you if you use this without too much thinking then things can go wrong that's in a way the same with this pseudocode

9:04 the inner loop hasn't changed so each individual processing element is getting some index I I guess and then it just goes through the pattern and checks if it matches all along and instead of returning I just say report a match at I that's some some big intermediate stage what we would really need is another thing another step afterwards that collects the results um this is a problem we'll talk about later so I I'll leave that out

9:36 long discussion for a simple algorithm but I wanted to make sure that the parallel pseudocode is clear so if you have questions on on how the code is supposed to work or what what what is supposed to mean to write a loop like that with in parallel uh then then let me know or ask

10:07 and remember we'll have two measurements of time span and work or time and work that's one of those slides where I wrote time but uh it's parallel time or span all the all the way through what's the time for executing this algorithm usually when you see a for Loop you think oh this is so in so many iterations but haha it's in parallel so it doesn't count it each of these steps is done in parallel so we only really look at what does the longest of these iterations how long does the longest iteration longest running iteration take and that's a loop over the pattern and so it takes time linear in the size of the pattern Theta of M

10:50 now this is if you use the code AS given you'll see in the tutorials that for this task of checking where the two strings are equal you can actually do better depending on the machine model if you allow some concurrent axises you can do this much faster which is a an interesting speed up at that point unfortunately it's all not really that useful because work is really poor if you sum up the work that you do it's in the worst case you do M comparisons in each Loop iteration and you do this across roughly n uh processing elements so this is in a way like the brute force method used for sequential algorithms for the the sequential Brute Force algorithm and we've we've discussed that length in the last section that there's much better Solutions than for the worst case than the Brute Force algorithm so work is not good time is great you can't possibly beat constant time but if you remember Brand's theorem from a few slides back unless you have absurd numbers of processing elements that won't help you if work is bad the overall time is still slow maybe we can do something else and of course we'd like to take advantage of all this fast sequential string matching that we've developed

12:20 and it turns out a fairly General technique works here as well you can use blocking you can break the problem in a different way into sub problems um and that allows you to improve the work so what we'll do is we split the text into overlapping blocks so that we never miss a character so let me um illustrate this on a on a quick example just graphically so then I think it's it's clear why we do that in exactly this way now it doesn't need a power of two so that's your text T and I don't care about the the actual letters here it's just um conceptual picture and let's say um m is um three so the pattern could occur here where it could occur here what could occur here at any of the positions right it's wherever you have a three character long stretch that could be one occurrence of the pattern

13:33 what we want to do is to use a fast sequential algorithm or a small section of the text and find check if the pattern is in there and the trick here is that works basically out of the box but you have to make the portions of the text slightly overlapping so that the length of the um overlapping Parts is 2m minus 1. which is five and so the first five are assigned to one processing element so all of these red ones will be caught by the first processing elements if there's An Occurrence it will find it now how about An Occurrence that spans this boundary that might not be called that should go one further

14:33 we have to cut we have to catch the orange ones as well so we overlay a second one starts at M and this will cover all the orange ones and then for the next red one which again would escape this one by one character you have another start so you start at zero at three and then at six again

15:07 and so that red one would be would be caught by that one okay so it's a simple picture proof that no matter what you do um one of the blocks will always see An Occurrence of the pattern if there is one

15:25 with that preparation the algorithm is really simple you just iterate over all the block IDs if you want and compute what is the portion of the text you have to look at that's this five characters in our example and you you can use say the KMP algorithm to check if the pattern occurs in there

15:49 now is this um just a safe effort I stored the result if if KMP finds no match then you don't report anything but if it does then you report the result so I'm probably clear is the is it clear to you guys that the algorithm works correctly

16:10 there's basically two two things it should never record never report a match that's not really in the text that won't happen because it's it's looking at a substring of the text and it only says yeah there's a match if I found found the pattern there the other thing is it cannot miss a match that's what I try to improve with this picture no matter where the match starts one of the blocks will entirely contain that these M positions and so we'll have to find the match

16:42 again second question how good is this algorithm if we look at the time again um parallel time means this parallel Loop doesn't count it's happening all at the same time so we just have to find out how long the loop body takes we call the KMP algorithm which we know has running time n plus M for a text of length n and a pattern of length m now we're not using it on the full text but on a small snippet so if you insert that you get overall linear time in terms of the pattern so the Theta of M because we use it on a very small piece of the text and if you compute the work is also work efficient the reason is that we have not so many blocks so even though each block uses beta M effort we only have n over M roughly plus one maybe that's still Theta of an overall effort overall work at least if you assume that the pattern is shorter than the text that's work efficient and maybe a simple check can can catch that corner case so that's great we have a work efficient algorithm now but we've already seen on the last slide that the parallel time m is not the best possible we've had a better algorithm

18:09 just where the work was crap the correct answer is the is the third one which a few of you got okay interesting rendering of this character it's embarrassingly parallel in the sense that you can you can solve it as efficiently as as possible so that the total times is um is dominated by the work efficient part if the length is much much longer than m then you can say you can say that this parallel time Theta of M is is not bothering me too much the overall work divided by the number of processing elements that I have is probably dominating this and so there I would say it's it's embarrassingly parallel turn the argument around and it's clear that it cannot be yes if the pattern and the text have roughly the same length what you would get in this case here is a parallel time stays the same and work stays the same so you you don't speed up at all over the sequential algorithm and so uh that's work efficient but not really parallel you haven't sped up anything so in a way it's easy to paralyze string matching only for short patterns that is uh

19:56 all I want to say about the simple string matching methods that we'll look at in detail the two things I showed you the the code is really simple is also reasonably efficient to implement and you could even distribute the text and it would still work but um when the pattern is also long it might not be so helpful so you could ask could you improve on this can we get work efficient methods where the span is also better than M so we can really parallelize somehow non-trivial this matching part this is only possible if we can parallelize the matching process

20:39 that we can do if it's just checking uh two strings for equality but the pre-processing of the pattern is also part of this and as far as I know this is not not possible with easy methods but people have figured out more complicated ways to do that

20:58 um I skipped those here if if you're interested to see a part of this more complicated algorithm you can check out the recordings from last year but I took it out in favor of some other things also because it was not the entire story there was always the pre-processing missing which is much more complicated so it was it was never so satisfying for me to teach that showing you this nice lovely bit that I could explain and then leaving off with this black box that we didn't dig into now the black box is just a bit bigger but I want to mention at least uh in in theory you could solve the problem faster you can do log M times that's again an exponential Improvement if you want uh even if the pattern is long if you have this concurrent right you can even do the matching part much faster for the pre-processing part there seems to be a very a lower bound that you cannot do it in constant time even if the machine allows you concurrent rights uh and again um no details on that just so that you don't walk away and say oh all the simple methods don't work so nothing works that's not quite true in terms of the practicality

22:18 um I'm not sure if if these methods ever have been implemented so that's maybe the statement to make