Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
DAN GARCIA
And welcome back. Now, let's see a really nice example in which we try to compute pi.
First, we'll try it in serial, and then we'll try it in parallel and see if we can do this. We like this problem because we call it embarrassingly parallel.
It slices up really neatly into different slices of problems that can be farmed out to workers, and they come back, and each of the workers doesn't need the neighbors value.
There's not a lot of communication between them. I'll just do my job and then give it back, and then you put it all together at the end. It's a nice fork and join model.
There are two ways to do this. This is the traditional way. If you will look at x squared plus y squared equals 1, that's a circle of area 1.
And if you looked at a quarter of that — so the top right corner, if you just solved that for y, you get y equals 1 minus x squared.
Square root of 1 minus x squared. That's the upper right value. That's the upper right value here if I do this. And look at this — this is in area 1.
Sorry, area pi radius 1, and the area equals pi.
This is simply y equals square root of 1 minus x squared from, and if I integrate this from 0 to pi, I'm going to get a quarter because I'm going to get a quarter of pi.
0 to 1, I'm going to get a quarter pi. If I multiply that by 4, I get pi. So this is just integrating this equation just from here, just this curve, just this curve.
And I say what's this area in here, and this is 1. And I integrate this, and this is height 1 also.
This is square root of 1 minus x squared, but I multiply that by 4. And I integrate between 0 and 1, and I get pi.
So this is mathematically telling me I have just pi. There's no sense — it doesn't tie it in, it's just that. It says pi is a number, and there.
There's another analogy, which this curve, this is beautiful. This is also, if you integrate this from 0 to 1, pi, which is a nice curve.
It looks like that picture on the right, you see. What we like about this over the top one is that square root can be slow from a floating point calculation point of view.
But squaring is really easy, so we can do multiplication really fast, much better than the square root.
So we're going to try this one, and we'll see if we can integrate this again from 0 to 1 and do this.
So remember, it's 4 over 1 plus x squared, and here's a piece of code that does this serially.
Here's what we're trying to get to at the top — 3.1415926535897932384, et cetera. So let's look at what this code does.
I have only 10 steps. So I'm going to 10 different rectangles to approximate my area. And the step size is 1 over the number of steps.
So that's the width of each of those rectangles, because if I remember, look at this. What's the width of that rectangle? That's step. Okay, what's the height?
Well, remember this before. The height is 4 over 1 plus x squared. And so this is 4 over 1 plus x squared.
Whatever the value of x is, x is a value from 0 to 1. So I initialize my accumulator sum as 0.
And then I'm going to go through — you always want to iterate on integer values. You don't want to be iterating on floating point values.
So I'm going to count how many steps, because you always have a very clean cut line. Floating point has this noise, right? Rounding noise.
So you don't want to have — well, sometimes, I ended up having some number of iterations, sometimes some other number, based on the noise. I want to have a clean number of iterations.
Now I have exactly here num_steps iterations. x is going to continue to move to the right.
So here's the value — oops, here's the value of x as it continues to move to the right. Whoops, as I continue to move to the right here.
sum starts at 0, starts at 0, and is going to be the area of that rectangle. This is the width. And this is the height.
Okay, so none of that's — none of that's magic. I'm doing that here. And when I'm all done, I print out the value of pi. Let's see what I get.
Well, I'm trying to get 3.1415926535. Well, I got to the 2. Well, this is supposed to be a 1, 3.141. I didn't even get there.
So I got two significant figures. If I increase num_steps, I'd do very well. I would increase num_steps to the biggest number I possibly can handle. I would do really well.
Take a long time, but I'd do very well — not very accurate. So let's increase the num_steps, and let's parallelize. Let's actually play with this and see how close we can get.
Parallelization version — boy, I wish they were a way. I wish there a way to just have a one-line change and make this work.
We do, that pragma we talked about before, that pragma parallel for, and I'm now done. So I'm now going to parallelize that for loop. OpenMP does all the hard work.
I obviously have to add the include file. But that's all I got to add. I love this. Isn't it nice?
Two lines I add, and this thing is now parallelized. Num_steps is still 10. And we can see what happens. Here we go.
Here's my parallel for. I'm going to sum plus equals. Let's see what happens here, all right it looks pretty good. And, uh-oh.
I've got a problem. Why is there a problem? Anybody see what the problem is here? Each thread needs access to this shared element.
The whole idea of parallelization, one of the core ideas of parallelizing anything, just in life, anything, is, what are any shared resources?
If I've got a shared resource, I really have to be very careful about the shared resource.
If I have multiple workers all working on and reading and writing to a shared resource — imagine — I don't know, imagine a Google Doc.
And they're all reading, and writing, and copying, and grabbing a thing, and grabbing their own version, which is in their cache, and then putting it back. It could really be ugly.
Google Docs is nice, because it's not really their own copy of this.
But if I had a folder, and I'm copying a version of paper, and I'm putting it back, and then you're grabbing a copy — obviously, we're writing in parallel.
But there are issues like that. So this shared value sum is a problem. We don't like that. The code's going to run sequentially.
That sum, it knows that sum is sequentially.
So we've got to think about how to do this in a way that I don't have this single sum that's going to be shared across these guys. So let's do this.
What if I do the same thing I did with my for loop, and just slice it up, and say sum 0, first thread, you're going to deal with the left side of this.
And you're going to deal with the right side of this. And then I compute independently sum of 0 and sum of 1.
So I'm going to have this sum array that I independently compute and independently contribute to. So here's just two — rather than one accumulator, I'm going to have multiple accumulators in parallel.
And then, when I'm all done, I then add them up.
The join is a sequential thing, where I go through each of the sum — all right, what was your — it's like all these workers went out and worked for me.
How much do you make? Okay, how much you make? How much do you make? And I write them all down at the end of the day.
But they all were doing their thing in parallel, working their job. At the end of the day, the boss asks you, how much did you make?
And here, it's saying, how much did you accumulate? How much area did you calculate? How much did you calculate? Done.
So that seems like the right way to do this. So let's do a trial run here. So now, what did we change?
Well, I have to have — I'm going to hardcode the number of threads to 4.
We talked before about how to ask what the total number of threads are, or I can set that somewhere. And by the way, here's the way I'm setting it so NUM_THREADS is this constant.
I'm just setting it to 4. So I did that before. And I'm going to do my parallel loop. I have to — here goes my sum.
And I'm going to initialize my sum to 0. So it wasn't as easy to do as before. Before, I had a one-liner, sum is 0.
Now I have to have a little loop to initialize all my sum accumulators to be 0. I do the same thing. Everything is the same, except that what am I doing differently here?
Here's this idea. Each of them is going to grab a different piece of that array.
Just like I was doing my for loop before, each of them is going to be contributing to a different sum of id, where id is my get thread number.
Aha. We did this before when we did this printout. We kind of showed what that was. Here, I'm also printing out this piece of it and the ID number, same as before.
All that's the same code as before. I am accumulating it out to the various values of the sum. And at the end, I initialize pi, the return value, to be 0.
I keep — sequentially, not in parallel — contributing sum's contribution into pi. And then I print what pi is. How's number? 3.142425.
We did pretty well. I've parallelized this at least into four different ways. And hopefully, this is pretty close to being four times as fast. It's not going to be perfect.
There is some overhead. I still have to do this adding up the sums in sequential order. But I'm getting close to a four-time improvement in speed. Love this.
Did pretty well. Let's increment this to now — just change one line to say, rather than NUM_STEPS is 10, number of steps is now a million. And how am I doing?
3.1415926535897 — not bad, not bad. So we're actually doing fairly well. This is a pretty good job. I'm feeling very confident about this.
I love this. Now, I got to take a second back. How do I parallelize computing sum? You remember, that sum at the end, I had to stop.
And remember, that was fine, but I did this. This is, I'm stalling for four threads. It's not too bad. It's only four threads.
This has nothing to do with number of steps, number of threads. Could I parallelize that threads? What if I had a lot of threads?
What if I had — could I parallelize that — parallelize computing the sum in some way? That would be interesting.
Well, let's try this one, let's bring that pi — remember, that pi plus equals sum of id. Let's bring that into the loop somehow.
So now I put this bracket around omp parallel — pragma omp parallel. So here's this bracket around that. And I brought the pi computation into that loop. Let's try it.
I'm so excited. Now, it'll be a little bit more efficient. Just that last group of four, let's bring it in there. What do I get?
Okay, so the summation is now inside the parallel section. So there's not much speedup here, right? You're only speeding up these four guys. But what happens when I run this?
3.1415926535897932 — uh-oh. 3.13? Wait. I've got a number of steps is a million.
Wait, wait. I got a million — I got 1,000 threads here — look, 1,000 threads, so I added more threads here, a lot more software threads. That's different.
So I cranked that up. I still got my million steps. That's doing fine, except — is that a million? That's like 100,000 steps.
So it's 100,000 steps. It's still pretty good. But look at pi. What happened to pi?
That's crazy. Something went wrong here. And what's even worse is the value changes between runs. If I were to run this 10 times, like you saw before, the value's going to change between runs.
What is the problem here? Well, the problem, somehow — the only thing I did differently was I added more threads. That shouldn't be the problem.
I changed the steps down by a factor of 10. That shouldn't be the problem. I brought the sum into the parallel part. Can you see why that's an issue?
What's going on? This, my friends, is called a race condition. And this is a big idea.
When you run in parallel, or you run with the — when you run with the parallel people, having race conditions is something you have to really work hard to avoid, because it's a way to have garbage values.
It's a way to have not just garbage values — I mean, this pi calculation is almost useless anymore, right?
I was trying to do this so I could get a nice, very high-resolution value of pi. I'm not getting that at all. And it's going to change between runs.
You can't have that. We can't have that. This is, again, pruning that nondeterminism. And one of the things is, this race condition is the reason for that.
What if more than one thread grabs that? So more than one thread grabs — watch this. Pi equals pi plus my sum of id. So far, so good?
That's no problem. So what's happening? And this is at the end, by the way. The loop, all that main loop — here's the main loop for 100,000.
Here's the main loop for 100,000. This is just a little bit here at the end, where I have to now do this calculation at the end. This is problem, because what happens?
At the end of — this is the day. This is the work day. And now I'm at the point where all thousand people have to contribute their computation into the value of pi, okay?
Plus equals — plus equals says, pi equals pi plus there, which means each — what happens if two parallel threads grab the old value of pi?
They both grab the old — let's say the pi is 3. Let's just say pi is 3. So I'm going to add it up. Now it's 3.
Okay, I'm going to add my little fraction to that. Maybe both of us calculated 0.1 — 0.05. So 0.05, 0.05, 0.05. Should be 3.1 at the end of the day, right?
If here's pi at 3, and I calculate 0.05, and you got 0.05, and we both calculate our piece to it — so pi should be 3 plus 0.05 plus 0.05 is 3.1, okay?
And then there's more to get the 4, blah, blah, blah, et cetera. So stay with me. We both read 3. You can see this race — can you see it happening?
I'm going in slow motion. We both take our 3. We both internally add our 0.05. And we both — now, you write first.
Now 3 becomes 3.05. And I write mine. Pi becomes now 3.05. We both wrote our 3.05.
And it's not like we're able — one of them was thrown away. The first one was thrown away, because this one was — this could have been 0.06, put it there.
And then 0.05, whoop, it wrote over that. Trouble. Trouble, trouble, trouble, trouble, trouble.
The only way to deal with this is we got to figure out — so that's the problem. This is called a race condition.
This is a nondeterministic — by the way, this is when they were both the same. What if one is bigger and smaller? What if this is 0.06 and 0.05?
And here, and here, whoever writes last is going to be able to own that number. And the other one is lost. So it's nondeterministic. And I've lost values.
So this is really trouble.
We've got to figure out how to prune this. So we're going to look at how to kind of lock the other people out of code that really should be sequential.
Now, we had a sequential at the end. But we want to be able to do this in a clever way that we still get a little bit of parallelism.
But we got to have a lock. There's got to be a way to lock people out of this to be able to do this in a kind of clever way, okay?
So let's see if we can do this. I still want to be able to measure it. I still have 1,000 threads. I still want to be able to parallelize my contribution to pi.
But I want to do it in a way that makes sure that not — two people aren't both trying to write to pi at the same time, because if they're independent, if 1,000 people never happen to run it and override at the same time, I'd be fine.
It'd be great. And it'd be parallel. Each one is contributing their pi, rather than having one serial guy at the end. So I like that.
I want to get to that place. But I need some help from software to support and prune that race condition, okay? We'll see that in the next video.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.