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 wonderful abstraction called OpenMP that can allow us to work with those multiple cores very efficiently in an easy way, without having to add a lot of code in C. So if you had a parallel loop, here's a very simple loop.
It has 100 iterations. i is going to have the value of 0 through 99, inclusive. And you just have one thread just doing all of that.
If you had four helpers, how would you do it in parallel?
Well, the smart way to do it, if you know about caches, in which you know that it makes sense to have maybe one worker work with one particular cache block, and if you have at least a wider cache block, when you bring the block in, you can work with all your neighbors.
Again, we don't want to have four different workers all working on the same particular word or at the same particular block.
It'd be nice to kind of separate them out, divide it up, so we break them up into 0 through 24, 25 through 49, 50 through 74, and 75 through 99.
And so now you have four different workers, all working on one part of the loop. So I'm going to work on this part of the array. Go away from me.
I'm going to work on this part of the array, and you do the same thing. So there are four of us all kind of owning a space of the array.
That's the cleanest way to do this.
You could also have sliced this up a different way, which would have been really bad for the cache, in which each one of them is going to work on i mod 4, and I'll be i mod 4 equals 0, so 0, 4, 8, C — 12, 16.
and you work on i mod 4 equals 1, so 1, 5, 9. You know, you could do it that way, kind of how the way direct-mapped cache maps every other color to that.
But that's not the way we want to do this in terms of parallel execution. You want to own a space of it. I'll load the whole cache block in.
I work in this, and don't bother me. I'm going to be in this whole part of the array.
So you want to kind of separate them out in memory so they're not stepping on each other's toes, if that makes sense. So this is how we divide it up.
This is a smart way to divide this up. How to do this in OpenMP? It's not that bad.
I first have to include the header file, the omp, then I just had to say a #pragma.
#Pragma is a way, kind of a directive to say, I want to do something special that's above and beyond. #pragma omp parallel for, and it's done. That loop will be paralyzed.
That's all you got to do. That's amazing. And loops are so common, this is a very effective way to do this. So here's an example.
I grab a pen. I'll walk you through how this entire thing works. There are different compilers that'll support this. You've got clang.
Here's an example. You've got gcc. You've got gcc-5. And I would recommend the top one, gcc-5, because it lets you only have a very simple line.
Look, -fopenmp. That's all you need to say, is -fopenmp, and here's your source code, and you get a.out, and a.out works.
If you want to use gcc, you have to add -lopenmp and then you could also name it, and with the -Xpreprocessor, much cleaner just to say, use gcc-5, which is really nice.
All right, what does this code doing? All this code is essentially doing is it has an array of 10 elements, whose value is the same as the index.
So array element 1 is the index 1. Array element 9 is index 9. Really easy, okay? I'm going to tell OMP, OpenMP, that I want to use four different software threads.
I don't know how many — I have no idea how many hardware threads I'm allowed, how many cores I have, whether I have hyperthreading on or off. I don't know that.
I'm just going to say, I want to use four software threads. Let's work with that. This says N is going to be sizeof(a)/sizeof(int). Essentially, that's just 10, so N is 10 elements.
Here's my #pragma I talked about a second ago, omp parallel for. That means this for loop is going to be paralyzed. Here we go. So let's take a look at that.
What happens here? Well, for i=0; i is less than 10; what happens? I'm going to print the following.
I'm going to print the thread number, and here's get_thread_num(), and I'm going to print the value of i.
So what I'm essentially doing is saying which of the three — there are four threads, 0, 1, 2, and 3. They're numbered 0 through 3 for four threads.
And I'm going to then assign the value of a[i]. I'm going to overwrite it. Before, a[i] was just 0 through 9.
I'm going to replace it and add the — 0 through 9 obviously has only single digits, so that's only ones values.
I'm going to add a tens column, and the tens column is going to be the thread number. That's what this is. Basically, stop the thread number, clobber the tens column with the thread number.
What that's going to give me then at the end when I'm all done — so only this part is paralyzed.
Then at the end, it says, we'll go through all the array and print the values of the array. That's all this is doing, nothing really magical here.
But here's what's really — I'm going to show you a demo in a second. It's going to be fun.
Just like we predicted, the — I've color coded this, if this helps a little bit. So I'm going to show you this here.
So this single digit, the tens digit says, all of these were owned by thread 0. 0, 1, and 2, the first three — this is like 0 through 24.
Here, it's only 10 elements. And by the way, this automatically happens, works. Even though 10 isn't a multiple of 4, it works beautifully.
And just all that details of, well, it's not a multiple of 4, so you can't — it just handles it dynamically. Beautiful.
Thread number 1 handles the values 3 through 5, so this is 0 through 2 is thread 0. Thread number 2 handles 6 and 7, and thread number 3 handles 8 and 9.
So it's neat. Look at this — three of them, three of them, two of them, and two of them.
It did as well as it could in terms of dividing them up into four equal parts. Amazing. The interesting part is when you look at what gets printed out.
Part of what Professor Lee was talking about in that quote was that it's unpredictable when things will return, when those software threads get mapped to hardware threads and run and then how fast they finish and complete.
Let's look at this. This happens to be a very pretty thing. Look — 0, 1, 2, 3, and then — oh, look — 0, 1, 2, 3, and then 0 and 1.
So that looks like they did it in order. Now let's run it twice. I had this queued up. This is the same code, nothing different.
This code is available to you. I'm going to run this code now. Let's run the for loop. Oh, look how nice it is.
All the 0's hit first — 0, 1, 2 — then all the 1's — 3, 4, 5. Then look at this — then the 3's hit. Look at this.
Then the 3's came in, and then they finished. And then you got a 2 and the 2's. Now let's run it one more time. Watch what happens.
The 2's, the 1's, the 3's, the 0's, 0, 3, 2, 1. Look at this. 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2 — look at this, okay?
0, 1 — this is — uh-oh, uh-oh, uh-oh! Look at this one.
The three 0's finished, then the 1 started, then two 2's finished, then two more 1's finished, and then the 3's got in the game. So this is really interesting.
You have no idea as I'm running this who's going to be divided up. Now that they're all together, we can just keep trying this.
Now, the 1, look — there's a first 1 came in there, then the 3, then another 0. I'm just showing you, this is what the realities of this are.
So as you're thinking about writing code, you have to write code that's impervious to how long it takes these workers to finish.
That's the hardest thing to do as you're stepping back and, boy, how do I divide this up?
And also, I don't care how long — I have to have code that is able to handle, naturally, just resilient in terms of handling this. And this particular thing doesn't.
If I care about the order of printing out, any side effect like this is going to be affected by the order.
So you have to have your computation be, again, impervious to how those threads get loaded into hardware threads and return and finish. In summary, let's do just two slides for summary.
It's a C extension, no new language to learn. Well, let's learn Go and make you do a project in Go.
People have thought about doing that, and that's a lot harder than just living in C, getting better at C, but using all the — you know how to do that in C, all that you know about C, to make C parallel.
So it's a wonderful extension we're really, really a fan of. Multithreaded shared memory parallelism — you add a compiler directive, the #pragma.
You get this runtime library with .h files that includes all the headers that you need.
Here's the nice thing — the #pragma, any #pragma you have, is ignored by compilers who don't know about OpenMP.
So it's wonderful, and it's the same source code for multiple architectures — 1 core, 16 cores, hyperthreading on or off, 28 cores. Doesn't matter. Same source code will just work.
It's just beautiful that way. It also only works with shared memory. So here's the programming model. You've got a main thread.
We call the main thread or master thread. I prefer the word "main thread," and then it's going to fork.
It's got to fork its way, and you have then multiple streams in the parallel region. So all these are multiple streams all working together.
This parallel for — this fork is a way — what are these? These are called patterns. This is one of the software patterns for parallel programming.
The idea — you fork into these multiple threads, and they go through, and then there's some join at the end.
And all this is — you used to have to explicitly call a fork and explicitly call a join. This parallel for does all that for you, which we really love.
But if you wanted to have this explicitness, you can get to that, but fork can join is another option. That's another model to think about this.
So there's a parallel region, and then you have some serial region, then a parallel region, and this might be this, then another one. It might only have three, and you divide this up.
And so you have these serial regions, and you have these parallel regions. We love that. So they begin at a single process. I call it the main thread.
This is a sequential execution. Then when a parallel region is encountered, it forks it into parallel threads. They execute simultaneously, as much as you can, as much as the hardware will allow.
And at the end of that, there's a join which brings it back to the serial portion again. We're going to see Amdahl's law. I keep talking about Amdahl's law.
We haven't touched Amdahl's law yet. When we teach you, you realize the point of Amdahl's law is it's really painful being in these serial portions.
As much as you try to speed up the code, the longer you spend in these serial portions, the harder it is to speed the whole thing up, because that's what dominates over time.
So what kind of threads are we talking about? Remember, I mentioned before, these are all software threads. I generate — Sorry, I c — Thank you so much.
I generate these software threads. The OS's job — it's not my job. Don't worry about it. Not my job, man — to multiplex these onto the hardware threads.
So the operating system does that hard work to figure out who's idle, who's stalled, who's blocked, or who's making a memory access to go to Sacramento.
Okay, get this guy out and get the next one in. All that's handled by the OS. It's wonderful.
I'm trying to look at other things I want to say here.
You're certainly competing the hardware threads. You certainly have a fixed amount of hardware and all those softwares — those are competing for that space there.
The key thing that's actually really hard is that, be careful when you're doing timing. Timing is a complicated thing. We encouraged people all in 61A, 61B, CS10 not to use clock timing.
Don't use clock timing. Figure out what this is.
So we have to be able to share with you some of the hardware support, some of the software support to do timing, because I almost feel like I need to do timing on this.
Well, let me just have a stopwatch and start doing — have a single thread and time that, and then compare that with 100 threads and then stopwatch.
We kept telling people, don't use the stopwatch in timing.
But in some sense, we need to think about what support we have so that I don't have to rely on my broken stopwatch for measuring that.
We'll learn more about OpenMP and lots more examples in the next couple of lectures. We'll see you there.
Đă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.