Video
Đăng bởi Quản trị viên OpenER ·
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 last series of lectures, we're going to talk about a couple of details. We titled this "Thread-Level Parallelism Part III" — hardware synchronization, how do we deal with race conditions.
That's essentially that first part of it. What's deadlock? There's some more details of OpenMP. We'll have some fun here.
So let's jump right in. Hardware synchronization.
As a review, OpenMP has a beautiful way to — a beautiful abstraction to be able to add parallelism to your C code. You have a couple of lines of code.
Maybe there's a header file, and you say, I want it parallel. You have #pragma that says, I want to parallel this for loop.
And all of a sudden, this beautiful for loop that used to be a full serial thing is now parallelized across all the threads and just works, and it works in a really nice, clever way.
What this means, in some sense, is it's doing what we talked about a couple of lectures ago.
It takes a for loop and says, for i = 0 to some max value — here is max — it says, let me just chop that up.
So maybe if it's two threads, it's going to save 0 to half of it. So if it's 100, 0 to 49 is one of them, and 50 to 99 is the second one.
So it kind of keeps each of the threads — each of the cores is going to be working on a contiguous part of memory, rather than one from here and one from there.
You could do it that way, but it's a really bad way to do that for your caches.
So you have a contiguous area of memory that each of the cores is going to be able to process.
You should also have — so this is what the third point says — you should have a simple shape to be able to parallelize something.
Sometimes, even a doubly nested loop doesn't parallelize very well. It makes more sense to see if you can unwrap that to be a single top-level parallelization rather than two loops inside of it.
It gets complicated, so make sure you practice it. You'll see it as you practice with some of this, maybe for your project as well.
You're not allowed to have a premature exit in any of these.
So if you have this special code there, like a break, a return, an exit, or goto, is don't put this — don't jump outside of any #pragma within that.
You can move around inside that, but don't jump outside of the #pragma. You can mess with things. That's not appropriate. We talked about this.
If you have a shared memory system, and two memory accesses can form a data race. You can have two memory accesses both trying to read and update a particular variable.
It doesn't even necessarily — in C code, doesn't necessarily look like that variable is going to be in memory, but that variable, a sum — maybe we've tried to sum up pi — sometimes, depending on how you write your code, you cannot have people affecting a shared variable.
That's going to be trouble, and that's a data race, and that's a race condition. We want to try to prevent that with some kind of synchronization. So you want to do this.
You want to be able to not have to serialize all of it.
Could you actually have everyone contribute to some shared space, as they're all at the end of the thousand different software threads, and you want to be able to have them all add their contribution to an eventual sum that's going to be pi, hopefully, very close approximation.
How do you do that without having to do it in a serial way? Because you can imagine this being something with, now, I have a million different software threads.
It'd be nice if you didn't have to serialize that whole part of it and make it in the serial part. How could you parallelize write to that? So that's important.
We're going to see you can't do it in C. You can't write this in C. You've got to have lower-level support at the hardware level to make this happen.
Hardware synchronization is the secret to this. So the secret — and you're going to see this in every solution of any particular hardware device that has this problem.
It happens at the upper level, language level. You need to have hardware support to fix it. And the solution is something called atomic read and write.
This means you can read and write in a single instruction, and nobody else is permitted to have — no other access to that is permitted between that read and write.
And the idea is this is in a shared memory space. So this is a shared memory space. So a common implementation — here's how we do this in a very regular way.
This atomic is a swap between registers of memory.
So in some sense, you then link a read and a write with this, and the write would fail if the memory location has been tampered with, as it says here in the slide.
And RISC-V has variations of both. We'll talk about that. So we're going to call these Atomic Memory Operations, or AMOs.
And the idea is you perform an operation on an operating memory and set a destination register to the original memory value.
You remember back in the day — and here's a picture of what this looks like. There's a couple of instructions that support this.
And you can see them here — Add and Swap is what we're going to see in a second.
This is what it looks like if you look at the way it's broken down in RISC-V. And here's what's doing. I'll just give you a summary of the slide.
You remember, if I want to add something to a memory location — so a memory location has a value. There's a memory location that a of 5 — there's a value there.
And I want to add something. I want to add 10 to that value. I can't do that. There's no operation to add 10 to that value.
The only way I can do this is to bring that value into a register, add something to that register, and put it back. It's a three-step process.
| I'm telling you about this atomic memory operation is you're allowed to do that.
They're providing you a hardware support to do all three of those, and now we can think about how you might even build the control and datapath to make it work.
All three of those will happen at once, and nothing can be interrupted in this process. So what it means is, here's example for the add.
Here's an example of amoadd, so let's take a look at that real quick and what that looks like here. And this amoadd — here we go, amoadd — rd, rs, and rs1.
Here's what it's going to do.
I have a value in rs1, and I want to add it to the value at the memory location pointed to — I'm sorry, I have a value in rs2, and I want to add it to the value in the memory location in rs1.
And it'd also be nice if I then read the old value of rs1 and stuffed it in rd. So it's kind of a two-step process. Think about this.
So this is what's happening. So let's look at this. So first, I read in — this is a pointer, okay? This is a pointer.
This is *p. This is a pointer p. I'm going to read — this says, read in. This is a load word into t, into a local variable t.
I'm now storing the old value in that register, the old value in the memory location pointed to by r1, and I write it into rd. That's what this says.
x of rd is t, so I read the old value, put it into t. And then I update that value.
Here's the x of rs2, which says, what's the value I want to add to? I want to add 10 to the thing, to a of 5.
So this is my *p, so basically, like, 10 plus *p. This stores my 10, and I'm going to say — this says, rd gets *p. That's what's happening with this line, okay?
x of rd gets *p. And then I say *p = *p + 10, and 10 is stored here.
This says *p = *p, which is the t — see, t is *p — + there's my 10, okay?
So in one operation, it's doing read the old value, then do an add on what the old value was, and then put it back as the new value.
That's in one operation as an atomic value. And swap is this swap idea. So let's look at this, how we do it. If we do a swap, what happens here?
The lock is going to be a register stored — the lock is going to be in memory location stored in register a0. So a0 is a pointer to where my lock is.
Remember that, okay? So A0 is kind of the address of the p here. Got that, right? And remember, setting is 1, and unset is 0.
Free is 0. So first, I'm going to set t0 to 1, okay? t0 = 1. Now, what does this do? amoswap — aq stands for Acquire. rl stands for Release.
This says I'm going to acquire the lock. What this says, this says — t1 gets the old lock value, okay?
So t1 is going to get — remember, this is the old — if you remember the add, this guy gets the old value, and this is the new value I'm going to try to put in there, okay?
That's the idea here.
So a0 is going to now get — that memory location is going to get my t0, and t1 is going to get the old value of it, the old value of whatever that lock was, the *a0, if you think about it, okay?
Now, I'm going to spin. I'm going to spin on this — branch not equal to zero. So if t1, meaning what I got, what was there is already 1, branch not equal to zero.
So if it's a 1, meaning it was already grabbed, oh, it's already busy. I just go back here. I branch back up to there, and I spin on this.
I spin on here, okay? Spin to win on that. But the key is the amoswap that makes this work. Here we go.
If I fall through the branch not equal to zero, that means it was 0, so now I can do my thing.
And here's the key — it's not like — remember, this is the whole thing. If I fell through it, it meant that I grabbed it. This is the whole beauty of this amoswap.
It's not like, well, we both could read before. If I fall through the branch not equal to zero, this says that I have it now, because I wrote the 1.
Nobody else wrote the 1. This is atomic operation, so only I was writing the 1.
If there are two competing guys, and it falls through, only I'm going to be the one that falls through the branch not equal to zero. I'd be the one that actually writes the value.
So now I'll fall through. If I don't take the branch, that means it was 0.
This takes the branch if it's 1, which means if it's 0, that means it was free, and I just grabbed it. That's the idea.
This swap stuffed the 1 in there — not anybody's 1, my 1 only, so now it's mine. And now I go through. Now the critical section — now I own the lock.
That's the key. If I was doing this, if I somehow break the amoswap — if you remember, the amoswap had, like, three things you were doing.
The critical idea is only if — how do I say it? Because it happened atomically, it happened without any interruption. That's the reason this succeeds.
Now if I get to that critical section line, I know that number 1 was written to by me and me alone. That was the problem before.
Two people wrote the 1, thinking they both had it. Only I had it in this case.
So now I do my critical section and read it, bada-bada-ba, bada-bada-bing, and then I want to release it. How do I release it? I release it by swapping out x0.
I don't care — when I do the swap, I don't care what the old value is. I know it was a 1. I know *a0 is a 1, because I owned it.
This value, the old value, is going to go into x0. That's ignored. Nothing happens there.
And I basically take my x0, which is 0 and I stuff this into there, and now I reset it to 0, and now it's free. I release the lock.
I'm good. This is it. The critical part about it was that AMO was an atomic operation. I can read and write at the same time.
So the way the broken synchronization is it's while locked, and we're both spinning, and two people could be in a while lock, and they both say, oh, great, the lock is free, bloomp, and they both write their 1, thinking I own it.
Can't happen. This can happen now with this amoswap. This is the same idea. So this is the same idea.
By the way, if you try to translate 1 to 1, if I just take this by the — this is broken, okay?
If I take this 1 to 1 and write this in RISC-V, it's not going to work. The same problem happens with RISC-V without this. You need the amoswap to make this work.
So this is, in a way, my piece of, keep trying until I get it. And once I get it, I know this is mine now. I'm guaranteed this is mine.
I've got the lock. I've got this, and I unlock with the simple there. So all this kind of process through, so all this — this is this, and this is this, but done correctly.
This is broken. This works, okay? That's the idea. Pretty powerful stuff.
How does this work in OpenMP? Do I have to — no, no, wait, Dan. I can't use C anymore? I have to now write RISC-V?
No, you can do this in OpenMP too. Here's how it's done in OpenMP. Let's take a look. So first, we're going to declare an abstract data type called a lock, omp_lock_t.
Who knows what that is? I don't have any — is it a number? Is it a whole struct? I don't care.
I just have to reserve one of them. I have a lock. Here is my parallel section.
I say get_thread_num(), id is thread numbers in my parallel section, and now I want to have a piece that only I do, the sequential section.
So I first say, omp_set_lock(), and I say, address of lock. And now, only when I get it do I proceed into that section, knowing it's only me who's in that sequential section.
By the way, all 1,000 threads are all saying the same thing if they get to that at the same time, and only one of them is going to grab it.
Then the second one will grab it, then the third one will grab it. I print some ID, and then I end the sequential section by saying, omp_unset_lock().
And I have to put address of lock, so I pass it in, the pointer to that lock, both times, okay?
And then when I'm all done, I don't know whether that required this omp, the lock — there was space there. I'm going to have to free it.
So I had to go back to my parallel — I had a parallel section before and a parallel section afterwards, and I'm pretty good.
And at the end, I'm going to destroy that lock, and I'm all done. Pretty clean. Pretty nice and pretty clean. So that hardware synchronization was key.
That AMO was key to make this work. Normally, you have libraries that — this is true.
Any time you're above the lowest level, normally you have to be able to — well, in C, that's how you do it, because OpenMP — any other language has to have a way.
Every language has to have way to synchronize these parallel things to say, nobody — only one person can own these, as I said, lock or semaphore, at a time.
You have to support that. So this is going to be supported in almost every language that I know of that supports parallel programming.
There's an idea of a semaphore, or idea of a lock, that's built in the system.
And by the way, the way it builds it in is by going down to and actually making calls to the AMO levels below that. It'll actually compile or interpret down to that.
That's the key here. OpenMP also has other #pragma for other things — critical cases, atomic, barrier, ordered. There are other things. Please read the manuals in the bottom.
There's many more features — private variables, reductions, a lot of stuff in there.
If you're going to really dive deep into OpenMP, there's a link that at the OpenMP.org site that has there, and there's a nice hands-on documentation, which is useful to play with that.
There's a tutorial there. So here's an example of a critical section. Here's an example of another way to do this.
Mutually exclusion says that only one thread at a time can be in the critical section, and they're going to wait their turn.
So let's go back into our adding up, trying to approximate the value of pi. I can just say, here, look at this. Look how clean and beautiful this is.
I can do the lock. I certainly can do the lock, and that would be fine.
I can work with that, but it's a lot more pieces of — so if you make a lock, you preserve it, and blah, blah, blah, blah, blah, or I can just say, omp critical.
Very beautiful and very clean. So we got omp parallel. Here's the open and close here, omp parallel — actually, open and close here. This is important.
This is an open and close here for that omp parallel. And within this little range is omp critical. This is the loop that closes here. So this is the line there.
And right inside the parallel — I'm saying, this is a critical section within the parallel section, saying, this guy better be only one thread at a time.
And there it is — pi += sumid, and it works. So we started by — and if you remember, by the way, there's 1,000 threads here, software threads.
We started by saying, well, let's just have a couple of threads. Four would be fine. And we said, well, why don't we have 1,000 threads? Well, then it's kind of annoying.
At the end, I have to wait till the 1,000 things — that they're all done to be able to add them up. That's a little annoying.
It's not really a big deal for 1,000, but if I had that number of threads that's a lot bigger, that'd may be a problem. How can I synchronize that?
Well, let's just put that pi +=, and then we introduced explicitly a race condition just to teach what race conditions were. Then we said, well, how can we get back?
And so now I'm at the point of, right paren. I'm now closing the thought the thread, the conversation about how to do this.
And so I introduced a problem to then fix it to be able to teach you what this critical section was and how you can do this with hardware synchronization, and that's the key piece here.
Now, now that I bring up this idea of locks, I now have to bring up the second kind of problem that you have introduced with parallel code, which is deadlock.
We talked about race conditions and how to deal with race conditions with these locks. But once you introduce a lock or semaphore, you now have the possibility of deadlock.
What is deadlock? The deadlock is a situation where multiple actors are each waiting for each other, and we're frozen. Livelock, by the way, is the same idea, but people are moving.
There's motion, but still, you're kind of stuck. So deadlock is, oh, you're lurched. And I'm waiting for you, you're waiting for me, and no one, nothing moves.
Here's a beautiful picture, just to show you, of deadlock. And I believe this is a traffic jam. I think this is in China.
I'm not sure where this is within that, but someone took a picture of a beautiful case of deadlock that computer scientists all around the world said, ah, deadlock.
And we all grabbed that photograph and are using it in our slides to teach deadlock. I mean, that's amazing. All it takes is one car.
It's just, like, one car could — I mean, look at this. No one can move. The problem is, you get in there. Oh, let me just back up.
Well, people are behind you. Now nobody can move at all, because if you actually pack it in so no one moves, you're literally stuck. No way to do this.
If you just judge — if this guy can just move here and move here, then these guys can get through, and then it all freeze up.
But you can have this kind of situation if you don't have the traffic lights set up rightly. The most famous deadlock, by the way, is it's called the dining philosopher's problem.
And here's the problem — we've got these philosophers around the table, and each of them, in parallel — this is a parallel system — thinks a little bit, because they're philosophers.
They think about something, and then they grab a left fork. It's available, and if it is, pick it up. And then there's a fork on both sides, by the way.
Five people and five forks is the idea. You can do this again with two chopsticks, one on each side, but let's just do this one, okay?
Think until left fork is available, and when it is, pick it up. Think until the right fork is available. When it is, pick it up.
When both forks are held — I don't know who eats with two forks, but eat for a fixed amount of time. So two forks, and maybe you're pulling apart some meat.
I don't know, putting apart some piece of tofu or something, okay? And then when you're done, put the right fork down, put the left fork down, repeat from the beginning.
Well, what can happen is everybody goes and picks up the left fork, and everyone is now spin waiting on the right fork, but everyone picked up a left fork.
And so this actually works better with chopsticks, to be honest. And so everybody goes to the right one, and there's no right one.
So all five are stuck in this deadlock scenario, where there's no — and it's just like the parking situation, the traffic jam. No one can grab their right fork, so nothing happens.
Here's an example of livelock. You walk past somebody in the hallway and say, oh, I'm so sorry. You go like this, but that person also walks like that.
You say, I'm so sorry, and you walk like this, and you do this. And the person follows you, mirrors, trying to do this.
And if these are robots, you can imagine a scenario where each robot pauses for the same amount of time and then moves to the right and then pauses for the same amount of time and moves to the left and never pass each other, ever.
You can imagine a little simulation where they just do this wiggling back and forth. That would be a problem. So all this is deadlock. We have to think about how to prevent that.
What are some solutions to think about preventing deadlock? We'll let you think about that, but that is something certainly we need to think about. We also want to talk about timing.
We want to be able to think, how do we prove that this wonderful — how do I adjust the parameters to make this parallel program work faster?
Normally, if I were looking at 61B, 61A and an algorithm, I'd do the algorithm analysis and count the number of basic, primitive operations, and I have what's called a running time, which is a number of primitive steps.
That time — by the way, running time is not time. You learn this in CS10, 61A, and 61B. It's not time. It's primitive operations, a count.
It's a count, really, and it's a count. So it's how do things grow as the size of the input grows. That's what running time is. We said, don't use the clock.
Don't use wall clock time or stopwatch time. Well, when you're running parallel code, often, you do use wall clock time, because you have a thousands things.
You care less about how many steps each of these threads does, but how much faster is this parallelization compared to before? So in some sense, you are using wall clock time.
So let's go back to the — let me undo that idea that you never use wall clock time to actually do that.
OMP, or OpenMP, provides some support, some software support, to be able to help you with that. What they do is they provide something called omp_get_wtime(), which is a void.
It returns a double, but doesn't take any arguments. The idea is that returns the lapsed wall clock time in seconds from some other time in the past.
And the way you can then figure this out is you have two calls. You assign the time — maybe it's seconds since 1900. Who knows? Seconds since the year 5.
Who knows what that is? It's some random — it's some random — it's some value of the number of some time in the past. Boom. And now I then run my code.
I then split it 14 ways. I join, I split in four, can join, and I come back, and I stop it.
And now I can say — and there were some parameters to this, so maybe it was the number of threads I have, or how I do something, or maybe the algorithm.
Whatever I'm doing, I'm doing something.
I want to kind of measure this better than this as the number of threads goes up, say, or this is, I run this on different machines, or machines that have different numbers of logical or physical CPUs.
So then you have a second, you have the end time, and then you subtract these two. So this is the number of seconds since, say, 1900.
This is the number of seconds since 1900 in the future. And if I subtract these two, then the only thing I'm left with is the difference in time between start and end.
So that's how you used omp_get_wtime() as a way to measure wall clock time to see how some parallel analysis works, okay? That's the end of this mini lecture.
We'll see you at the next one. Thanks so much.
Đă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.