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ả.
PROFESSOR
And welcome back. In this final lecture in this series, we're going to learn about how to synchronize this. How do we prevent that race condition we saw in the last video?
Synchronization. How can we have some software and maybe even hardware support for that? The idea is I've got a single shared resource. By the way, this is true for any parallel system.
This isn't just while it's in C and OpenMP and how do you do this. No.
In life, in computational thinking, you've got some resource that's trying to be requested, be used by parallel workers, parallel actors.
How do you limit access to that parallel resource in a way that won't give you the wrong value or won't do the wrong thing?
For example, how do you prevent two people from editing one file at the same time? This is true. Dropbox.
I log into two different laptops, and I'd try to modify the same file in different ways. This one, I write A. This one, I write B. I say with both files, what happens?
How does Dropbox handle that? Dropbox handles it. It says, there's a conflicted copy. So that is a way to tell me that there's — do I get a notification?
No. But the point is, there's a way for them to deal with this shared resource. So this is true writ large, in some sense, of any paralyzed system.
Otherwise, things can get mixed up. Here's a solution. Just take turns. Maybe if I'm in Dropbox, if I'm opening a file and editing it, I can't even open it.
Now, it certainly lets me. But I can say, you know what? You can't open this file. Someone else has the file open.
So maybe that means when you open a file, you write a secret thing, or something that says this file is open.
And when you try to open a file, every OS would look to see if that secret thing is sent, and therefore say you can't open it.
Now what happens when there's a race to that? So there's all this conversation. How do you prevent the race to this? Both of us, exactly at the same time, go grab it.
They both looked. So there's a whole issue of how to prevent that. But we've got to think about synchronization in a deeper way.
For example, all controlling your microphone, and trying to all talk at once.
If someone gets the microphone, and once they grab it they have to release it, it's a good practice for controlling conversations in classrooms as well.
The word for use in the parallel distributed computing world is called a lock. We have to lock out. We use a lock to prevent other elements from accessing a shared resource.
This is also, by the way, known as a semaphore. Semaphore is unlocked, so both are used in the same way.
The idea for this — we'll just do it in C — if I have a variable called a lock, when it's set to 0, it's unlocked. When it's set to 1, it's locked.
So if it's ever 1, it means it's locked and someone has control of it. Let's do it. Let's play with it. Let's actually code this in C. Here we go.
I have a little loop that says, while the lock is not 0.
So while I'm waiting for the lock to be — while the lock is being taken, I'm just going to sit and spin. This is called spin waiting.
So I'm spin-waiting for lock to be released while lock is not 0. So I'm going to sit, do nothing while lock is set to 1 or grabbed. Now it's 0.
The moment it's released, I'm unlocked. And what I want to do — I — one of the threads, I'm going to grab it. I'm going to set the lock.
Lock equals 1. Now I've got the lock. Whatever that shared resource is — maybe here it's pi, the summation — I'm going to say, now let me do it.
I may contribute my stuff to pi. So I do my shared resource. That's all sequential, by the way, because only one person is accessing that at one time.
But that's okay if the other 999 people are still computing their stuff. I grab the lock. Nobody's looking. Nobody needs to write to pi, great.
There's no loss of time, really, because nobody's trying to grab it. If somebody else posted, oh, I went to grab it. Now I'm just waiting, spin-waiting, just like I was spin-waiting before.
I contribute my contribution into pi. I kind of put my value into the final accumulator. And then I have to release the locks so the next person can do that.
So lock equals 0. That's what I'm doing. So I spin-wait until the lock is free. It's 0.
I grab it, set it to 1, do my stuff, and then I release it. That's this kind of code you're going to see all throughout. Now let's see how this might work.
I've got two different threads, all running the same stream of execution. So they both do this. One spins and waits. The next one spins and waits.
Now here's the problem. This, the thread 2, finds the lock is not set before thread 1 sets it. I talked about it before.
How do you handle the fact that these guys come out of order? And in fact, how much time thread 1 got versus thread 2.
Thread 1 did one thing, and then releases it and then goes here. So in the time — watch this. This is, by the way — I just want to make sure you understand.
This is time. That means this guy was spin-waiting until it became free. Then it went to go slow motion. I'm going to set lock 1.
In that slow motion time, thread 2 jumped in there. It was spin-waiting, and it saw that it was free. Now they're both going. Can you feel it?
The race condition to go set it. They both, thread 1 wakes up, sets it to 1. Thread 1 thinks, I've got control of the lock.
Thread 2 thinks the same thing, and they both now have control of the lock. So that little code that I showed on that previous slide looked really clean and really good.
Spin-wait for it, then set it, do my private work on it, and then release it. It's there. That doesn't seem like there was anything wrong with that.
Except when they interleave, in a way, that two different threads thought they were waiting for it. They both wake up, and they both grab for the lock, and they both set it.
And they both think that they have controlled it. What's going to happen is you're going to lose one of those values.
Each one of those is going to contribute their stuff into some, and one of them is going to be overwritten by the other guy. That contribution is lost now.
This is trouble. This is real trouble. So there's an issue. Both threads believe they got the lock.
And by the way, try as you like, there's no solution to this. As you try to hit that bullseye, you're going to continue.
Well, one of you had two locks, and one grabs the — no. I don't care how clever you're going to be, we can't solve this. At this level, we can't solve this.
Go ahead. Good luck. I'll wait. Pause the video.
Go ahead. I'll wait. It's not going to happen. You're not going to find a solution C to solve this problem.
This is deeper. It's deeper. There's something more fundamental we have to add at a lower level. We have to add some new instructions.
The only the way to do that, we'll see that in the next lecture. Last slide on this series. I'm very excited. This the second part of TLP, TLP 2.
OpenMP, we love. Very simple parallel extension to C. How many more lines? Like an include line, and then a parallel pragma, and you've got a parallelization. We love it.
Go play with it. Stop this video and start playing with this. It's wonderful. All you need to do is hit parallel 4 with that.
C is easy to learn. Not very high level, so it's easy to get in trouble. So why living in C rather than, say, going to go and try to do the same thing?
Try to compute parallel. Try to add up some values of pi and go.
Explore how different or difficult or easy it is to do that compared to doing it in C here with the OpenMP. We also saw that race conditions are an issue.
We tried to introduce locks in semaphores as a way to do that, but we saw that we can't do it at the C level.
We have to go even deeper to the assembly level to be able to work with that. So we need some new instructions.
We're going to see and do that in the next series of lectures. Okay? We'll see you then.
Đă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.