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. In this series of lectures, we're going to teach you a new abstraction called MapReduce and an implementation of it in many languages but in particular, Python, called Spark.
Very exciting. But first, what we're going to do is teach you this fundamental principle that actually we should have taught you a couple of lectures ago called Amdahl's law.
And actually it's called Amdahl's heartbreaking law.
And part of it is, as much as you try, you can't get past this law, so it's heartbreaking that you can't get above that, but let's even tell you what it is.
So the model is the following — you have some enhancement. You want to upgrade your GPU, upgrade your memory, upgrade some part of your computer, some part of some system.
It actually doesn't even — this law applies to anything. It's not actually even limited to computers. So the model is the following — you have some enhancement.
Let's call it E. And you want to measure how much your speedup is. It 2 times faster? Overall, overall, 3, 5, 10 times faster? 100 times faster based on this enhancement?
And there's a very simple equation that we highlight how to calculate that. So the speedup with E is the execution time without E divided by the execution time with E.
And you can imagine that, right? If the time is halved, then the speedup would be a factor of 2. Imagine that, right?
The time with the enhancement, oh my gosh, it's half time to do this thing. Oh, it's a new kind of shovel. Dig a hole, okay?
Well, it's half the time that it used to take, so some time in the bottom, half the time on the top.
If you figure that out, the time will be 1/2, and that 1/2 goes over here, and the 2 flips it, becomes a factor of 2 speedup. That makes sense?
2x. So often, in fact, we encourage our 61C students and all students not to use a percentage speedup, because people just get that math wrong. Oh, it's 150% speedup.
No, you want to use 1.5x. It's just much easier to understand what that is. Okay, let's understand how we came up with that.
So let's think about the problem that every challenge you have — and this is particularly true with code that has maybe a part that can be paralyzed, like in OpenMP, here's a parallel section and a part that isn't, a critical section or part that's the serial part, maybe the setup part and the gather part at the end the joint part.
There's the forking, the join, but the parallel part's different from that.
So here's what we're going to say — we're going to say the enhancement E doesn't affect a portion s, so a portion s, like a fraction. So s is a fraction.
These are all fractional parts — s of a task. And again, this is larger than just computer science and computer engineering. But it does accelerate the remaining part, which is 1 minus s.
That's why this is a fraction. That's the percentage. 1 minus s is a percentage, so 1 minus s is the parallelizable part, or whatever, enhancementable, improvementable part.
That's the 1 minus s percentage, a fraction, and s is a fraction that doesn't get changed. And it's accelerated by a factor of P. P is bigger than 1, okay?
That's the hope here. So now, let's take a look at what that looks like, then. So here is this — you notice that s doesn't change. So this s here is my s.
That doesn't change. But the 1 minus s part is smaller by a factor of P, okay?
So what we get is the execution time with E is the execution time without E — this is kind of times s.
So this, since s didn't change, since this s is still here, that didn't change so that s — this has kind of been distributed out. If you multiply this out, let's distribute this.
Let's distribute this into this sum. You get execution time without E times s, which is that part didn't change. See, that part didn't change.
And then it was the old execution time — the parallelizable part is this fraction. It's the old time.
It's whatever this time was, which is the execution time of there times the smaller fraction, which is 1 minus s over P.
Therefore, the speedup with E is simply that fraction, 1 divided by — because that's the normal time.
We normalize that — the 1 divided by s plus 1 over s over P. That's the fundamental equation that drives Amdahl's law.
So now, let's pull that out — the same equation, just wrote it a little bit differently. And you get the speedup time is 1 over — s is the fraction non-sped-up.
1 minus s over P is the fraction that is sped up.
And in the perfect world, as the speedup factor goes to infinity, if I have a million cores, a trillion cores, a trillion helpers working on this, that term goes to 0, and you're left with 1/s, and that's it.
So the speedup can be no bigger, and in fact, in the perfect world, is equal to 1/s. That's it. Remember, s is the fraction. That's the serial part.
All right, let's do this together. For example, the execution time of 4/5 of a program can be accelerated by a factor of 16. That's pretty good.
80% of the code is parallelizable — think about that — can be accelerated by a factor of 16. That's awesome. What's the overall speedup? Am I at 16?
Am I 50? I can't be bigger than 16. Am I 15? What's the hit I took in that I didn't speed up the whole program?
So let's work it out. Well, it's 1 over — what's the fraction that is serial? Well, that's 20%, or 0.2. What's the fraction that's parallel?
0.8. Well, that 0.8 is going to be 16 times faster. So that's now 0.05. So 0.2 plus 0.05 is 0.25.
1/0.25 is 4. You put all this money into a 16 time improvement, but at the end of the day, you only had 4 times improvement? Heartbreaking.
That's the reason we call it Amdahl's heartbreaking law. So as we look at this — here, again, here's a piece of code.
Here's, again — s is s and P, s and 1 minus s, or the parallel part. Well, yeah, parallel part is always fractions, okay? So here, I look at this original time.
I have a piece of code that's mostly parallel. We're doing pretty well. And every time I add more cores to this — there's the number of cores I'm going to have here.
Every time I add more cores, I'm going to shrink this parallel part by that factor.
So now this yellow guy is 1/2 as high, and this yellow guy is 1/3 as high, and this is 1/4 as high. Try to do the graphic that way, but that's the idea.
So as I look into the number of processors, what I see is, depending on the parallel portion, I have different curves for how, in the perfect world, how much speedup I can get.
So if the parallel portion is only 50% of the code, well, then the serial part is 1/2, and therefore, you only have 2 times speedup.
So I could have an infinite number of processors, and I only have double speedup. That's amazing, in the network, of course. Well, how about 75%?
If 75% is parallel, then 1/4 — think about that — then 1/4 is serial, that means only 4 times speedup. The next curve says, how about 90% parallel?
Well, that means 1/10, and therefore, 10x speedup. How about 95%? Well, that's only 1/20 is serial. Therefore, it's only 20 times.
So 20 times is pretty good, but you have to almost get to 95% parallel before you can even get 20 times speedup, much less — I mean, look at the number of cores.
We got 65,000, 64k helpers, yet it was only a factor of 20 faster, and that is Amdahl's heartbreaking law.
So moral of the story is, do all the work you can to have very little serial code, have very little setup code, go parallel for the whole thing if you can, and then, very little, kind of gather and join at the end to be able to release your results.
That's the idea. If you want to really maximize it — it's kind of the overhead. It's almost like the overhead you're paid. I got a business, and I have to pay the rent.
That's the overhead. All the profit I make, the overhead factors in.
So whatever you do, try to reduce the overhead, the serial overhead of your code, so that you're almost all in a parallel stage.
Try to get to the embarrassingly parallel problem where very little setup — example, initialize all the sums. Remember how we were adding to pi together? Initialize them all to 0.
That wasn't done in parallel, but although maybe it could be, but that was done in serially.
And then compute all the pis — that's the big chunk of the work — and then some small fraction to gather together and sum it together at the end, all right?
All right, Amdahl's heartbreaking law. Sorry to be the one to be the bearer of bad news, but you got to know about it.
You got to learn about it, and that's probably in the perfect case with an infinite number of processors. I imagine the other elements of it.
Well, one was slower than the other, and this one failed, and we'll talk about all that when we get to the topic of cloud computing and how we'd have to deal with those failures.
We'll do that later, all right? See you 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.