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. Now let's try to figure out the solution to the problem we posed last lecture, which was how do we make use of this incredibly powerful machine, 2021.
We know how to deal with the wide vectors, but I've got multiple cores.
How do I think about it from a software point of view to be able to make this machine scream, make this machine do all the performance, the compute, on some huge data set.
How do I make use of multiple cores attacking at the same time? Let's get started. So I go to my Unix machine, I type px minus x.
Please find the equivalent command on your computer. Usually it's ps with some kind of command. It used to be -ef. Now it's x.
Here's what I see. I've got 156 different programs running at the same time right now. Not right now, but at the time of that slide, 106. How does my laptop do that?
My fan is not running. It's quiet. How is it running 156 programs all at the same time happily? The fan isn't even going.
Oh, my gosh. I'm being overheated. Listen with the microphone. No fan, very quiet, happy.
How does it do this? This is the analogy. Imagine doing 156 different assignments at the same time. It's crazy.
Here's the idea. First new name for this lecture, a thread. A thread stands for a thread of execution. It is a single stream of instructions.
Think of an old school program. A single PC. You load in a program, a.out. You load it, and you're running it.
You're loading a.out. Just think about that for a moment. There's some control. Make a function call.
Now it goes here, then it comes back. It comes back here. It's a single thread of execution. That's a thread.
A program within a.out could split or fork itself to have multiple threads of execution all running at the same time, and then it might have a way to join them back together to have a result.
So these are kind of analogies here. So it's an easy way to think about parallelism. It's a single thread of execution. I'm just kind of following.
It's almost like a single finger. I'm on this line. Now I'm on this line. Now I'll make a function call.
Now I return. A single finger, single thread of execution. Imagine I have old school days. I have got a single CPU and a single core.
How do I handle multiple threads?
How did your computer, in the days long gone, that had a single core and had a single CPU and a single core, how was it able to run multiple programs?
The OS is a program. How is it able to run the OS and anything else? Well, here's how it always did it, time sharing.
The idea is the single CPU, single core, can — by the way, I make this analogy before. I'll make this analogy again.
If you're a parent with multiple kids, and if you have more kids than parents, or if somehow your spouse leaves and you're in charge of all the kids and you have more than one, you have to give a lot of love more than just a one-on-one.
One-on-one defense doesn't work anymore. You just play zone defense, as a lot of kids talk about. So what does that mean?
You put the youngest to bed, and then you hang out with the middle one. You put that to bed, give some kisses. Then you put the older one, and you keep going.
You give a little love to every single one. So it's like a little slice of time for each particular one.
Each one thinks, oh, you're giving all the love to me, and then they go around, they read a book or something.
They don't realize that you're actually giving love to other people at the same time. That's what the CPU is doing.
The CPU says, let me go to the first thread and give it a little bit of time, a little bit of time. It's running. It's processing something, and then pause it.
Go to the next one. By the way, unlike the analogy of having children where they go off and read a book, it's not do anything.
When you're not giving attention to it, it's not doing anything, because you're the only one who can actually make it compute.
So you go to the next one, give it a little love, the next one, give it a little, and you keep rotating, and then you go back to the first one.
And if you do this fast enough, if you time share fast enough, slice through time fast enough, you will never notice it.
It'll just seem like your computer is a little, and the more you have, the less slice you get, but you're like, oh, my computer is a little slower.
And now my video is maybe dropping frames or something, or maybe Zoom isn't doing the right thing if you have a really overworked machine.
YouTube sometimes can give you a very high — well, this might be also transfer of data, but Sometimes even the processing of data can't. not drop pixels, but it can't have the highest resolution.
I need to lower my resolution on YouTube, not because the pipe isn't big enough, in terms of data, but I just don't have the compute time to take all that in and do this.
I'm going to say, I'm failing right now. I'm going to now pinch down the pipe and say give me a smaller. It might actually do this.
You might actually have a system that says, I have a big enough pipe to handle a 1080p, or a 4k stream, or an 8k stream, but I don't have CPU cycles.
So I'm going to pinch it down. Just give me 360, or 720, or something smaller than that to be able to handle that. Time sharing. Slice it through if you have a single thread.
Single CPU, multiple threads, you time share between them. And by the way, I'll give you a little 30 second story. When I was an undergraduate, we worked on a time sharing system.
It was called Multics back at MIT, and we had a system. The week before finals we'd all be writing our papers. I went to the lab, the computer lab, to write my paper.
I didn't have a laptop or a personal computer at the time. It was my freshman year.
And I'm writing a paper, and the slice of time that I got was so small, with all the MIT undergraduates doing it.
I would type a whole line of characters and not see my cursor update. Imagine a computer so slow it doesn't even update the cursor.
I remember this. I remember being so frustrated because it would then give me a little slice. It would type all of them, and I would have a typo.
Then I said, oh, my gosh. I would count how many characters to go back. Go back 60, change an A to an E, but it wouldn't update. My cursor wouldn't even update.
Imagine this world where time sharing was so stretched thin, in terms of resources, it couldn't even update the screen in a text editor. That's what it was.
Writing a paper on this was incredibly painful.
We all learned to work in the middle of the night to do this, because during a 5 o'clock, 6 o'clock, middle of the afternoon, you couldn't even type 80 characters without having it paused until it gives you the whole line.
So time sharing can go bad if you have too many things asking for work for one CPU. You would have 100 kids, each kid was like ah, all crying at the same time.
We'd be bad. So in threads, more detail. Threads are a sequential flow of instructions that perform some task.
And we've been calling this a program for now, but now we're going to know that it's really called a thread.
A lot of times, we start with an abstraction and kind of reveal the abstraction later. It's really called a virtual address space, not just an address space.
So we're doing the same thing here with a program. A program was a program. Now a program, really, we're talking about a thread for now.
Each thread has a dedicated program counter that knows, for that thread, what you're doing. Separate registers. Ooh, interesting. So now you're thinking, how is that different?
Well, separate registers, you can still access the shared memory. We saw that before.
This is actually important. The distinction between a hardware thread and a software thread. Each physical core. So each core — the element is a core.
That's the unit now — provides one or more hardware threads. So a hardware thread is a thread running on that core. So each is executing a hardware thread.
So one of the threads is kind of loaded, in a way, onto the core. It's a hardware thread now.
The operating system supports, and can multiplex between, multiple software threads, and the idea is, I might have a program that divides itself into 100 different threads.
Those would be software threads, but I only have a four core machine. So now what does that tell me? Only four of those 100 software threads can be hardware threads.
If it's running on a core, live, it's kind of loaded, then it's mapping it onto that hardware thread that's mapped into that core, it becomes a hardware thread.
100 software threads, four hardware threads on a four core machine.
I might be able to actually be clever to get more hardware threads running on these four cores, but for now, we don't know anything about that.
So we're going to say only four for our four core machine. I only have four hardware threads.
And by the way, if you're still a software thread and have been mapped to a hardware thread, you're waiting, because nobody can process you. Just like the kid can't read.
If you're not being actively processed into a hardware thread, if you're a software thread just sitting there, you're not processing. You're just idle. You're waiting. That's the idea.
Hardware threads are running on the core. Software threads are all the ones that you created, all the ones that are kind of there and waiting.
All the ones in the total space are all software threads. The ones running on cores are hardware threads. Just some nomenclature.
This Professor, Edward Lee, recently emeritus, I believe, he had this wonderful quote about threads, and I'll just read it to you. Normally, I don't read slides, but it's just too good.
Although threads seem to be a small step from sequential computation, in fact, they represent a huge step. They discard the most essential and appealing properties of sequential computation, understandability.
You can have code that's hard to read, but in general, understandability, predictability, and determinism. Threads, as a model of computation, are wildly non-deterministic.
It means kind of random in a way. And the job of the programmer becomes one of pruning that non-determinism. Determinism means that I can basically promise you what the output will be.
I'm not rolling a dice in it. I'm not shuffling anything. There's no randomness there. Non-determinism means I often don't know the order that these threads are going.
These threads get out there, and what order they come back, I don't know, and that's the hard part about programming with threads, is how do you manage all these threads taking different amounts of time.
One thread went over there and just got spun in a loop and maybe is going to come back in a year, maybe never come back. So who knows.
Who knows what my program does. A single-threaded program could do that too.
I hire all these workers. Go out and do some stuff. I pay all these bees. Go do something, and then some of them haven't come back, some of them have.
Some come back in different orders. What do I do? How do I manage that is what Edward is talking about. So here's the idea.
The abstraction is they're all simultaneously active. Remember, I can rotate the time sharing. It lets them all rotate.
From the point of view of software, in a way, I don't care how many hardware threads can ever be run.
I'm just going to say, well, you know what, it makes sense to break this up into 100 pieces, just because that's the way, logically, this problem breaks up.
So I break it up into 100 pieces and let them all go, and you're going to notice that, if there actually are only four hardware threads possible — I'll say it this way.
It might be faster, it there are only four hardware threads and I have a problem, to break it up into more than four software threads, and you're going to say why.
Why do this? Here's why. Let's say one part of it gets stalled. So one of those hardware threads just gets stalled.
So one quarter of your whole thing is just being idle, stalled, because some part of the code is there and it's going to do extra work. Who knows.
It's just stalled. It's going to eventually return, but it just stalled. Imagine if, however, you broke it into 100 of these guys, and 26, number 26, this is the one that's going to stall.
Out of the 100 pieces, there's one thing that just a particularly hard computation, let's just say. So when that comes in, it's going here, and imagine if it's 100 now.
Let's go back to this model. If only one of those 100, or if it's only four, one of those four is going to be stalled and it's going to take a long time.
If I break it into 100 pieces, then basically I can compute all 99 of them. Let's say it's a lot of work.
So all 99 of them can finish, and that one guy is still computing. Okay, finally it returns.
In the four model, these three finished, and then this is still waiting for that first one. That first stalled guy is still stuck, still stuck, still stuck.
Okay, now it finishes, and then it still has 25 more to do.
But if I broke them up into 100, it's like those other 24 things that are now waiting because the first guy got stuck, can be processed over here if I break them up into 100 pieces.
Only that one guy that gets stuck is stalled there. So you could actually imagine that it makes sense for a particular problem to divide up into more software threads than you have hardware threads.
That's what I'm saying. It could just be it. And I don't think I described that very well, but the idea is you're just stalling with yourself and the other 25%, 24% of the problem.
But in my world, these guys are computing all those guys, and you're stuck on 1/100th of the problem.
And then when that gets done, you're done, rather than have to then compute the other 24 undone guys. That's what I'm trying to say.
And who knows what's happening in that particular problem, but it could make sense. There's a knob. I have a problem.
How much do I slice this up into for the given amount of hardware threads I can run it on.
Given the amount of course I have, given the amount of machines I'm going to dispatch this to on the cloud, how much resolution, how small a slice should I do?
So you play with this curve, and you play with it and you see what the knee in the curve is, what the low point of the curve is in terms of time.
Point number one, you have this abstraction of software threads. You're going to multiplex software threads onto hardware threads.
Here's the pool, and now you're going to grab some of them and pull them in here, pull them in, pull them in, work. Okay, pull it out, put another one in.
You going to try to get them all to a maximum there. How do you do that? How do you bring them in and out? Well, you can decide.
Whenever you've got a blocked thread, you got a cache miss, user input, network access. There's some reason that thread is stalled for whatever reason. We call that blocked.
It could be a lot of those things. I've got a cache miss. I've got to go to Sacramento. It's 1,000 cycles.
Well, get that guy out of here while you're going to Sacramento, make that a request that goes out there, pull it out, and then bring somebody else in to get some work done while the Sacramento is returning.
Maybe it's even farther than Sacramento. Maybe now you don't have the virtual memory, and maybe I need to go to disk. Maybe it means it's a page miss.
Oh, my gosh. How many is that, a million clock cycles for a page miss, possibly? So get this guy out. While it's waiting on it, while that's happening, do other work.
You could also have a timer, like a little time slice. So you say, well, okay, they're all fine, no cache misses.
Let's say I'm doing just R-Type instructions, adds, and subtracts, and XORs, just simple stuff not even a memory access. I'm computing. I'm in raw compute mode. Well, give some other people a chance.
Give some love to other people. So let some other people. So maybe slice out after a couple of timers. So you can multiplex them in different ways.
How do you remove it? How do you remove a software thread from a hardware thread? Here we go. How do I take it out?
How do I unplug it and put it back in the waiting stage. Well, I have to interrupt this execution. I've got to stop running. I need to save its state.
I've got to save its state. We did this. We learned a little bit in virtual memory, how you move things around for multiple processes.
So you have to save its register, save its PC to memory. You've got to pull it out, save it to memory, and now you've got it. So that's important.
So I can reinstate it. So now all the things that are part of that world of computation have to be saved, and that's obviously the registers and the PC.
How do you do the same thing? How do you start a different software thread? How do you load that onto a hardware thread?
Well, you go to memory, grab it's previously saved registers onto the hardware registers, and you jump to its PC and you keep going.
So basically registers and PC is the piece that's needed for these guys. Pull it out. Pull it in. Pull it out.
Pull it in, and you're doing this for removing and adding different software threads. So here's an example, very simple. I've got a thread pool. Here's my pool of threads.
Here's the list over here, a couple of all the processes, all the threads that need to be running, and the OS is going to map those threads to the cores.
So that's the idea, and you've got to schedule those to make that happen. There are four cores. Each core is actively running one instruction stream at a time, and that's it.
So I've got this huge pool, and they're being mapped to the four hardware threads.
If, here, I have only one hardware thread per core, and I'm running on that, and I'm just doing this until the program finishes. By the way, you're seeing here, many of these are daemons.
Many of these are programs that just continue to run. If the name ends in a D, as in the list here, user S, even user node D. The D means Daemon.
It means it's running all the time. This doesn't stop. It's not like, well, shoot, that was hard. We're all done.
Are we done yet? No, some of the programs never stop, and so the computer is always just processing, even a computer that's not running anything. I'm just in the Mac, in the finder.
I'm just in the OS doing nothing. I'm not running any programs, nothing's running. Yes, things are running. It's listening for a hardware connection.
Something is running to be able to handle the keyboard. That's your OS. Are there some network things? There are many things that are happening in the background.
Whose updating the clock. All those things are running, even though you don't realize it, as part of the OS. So even if you're running no user programs, many things are running in your system.
You should check that out, by the way.
Type ps minus x, and you'll see the list of all the things running, even when you're running nothing else, or maybe just run terminal and then type that.
You'll see, wait, I'm only running terminal, and there's a ton of things being run at the same time. All those are being processed.
All that is complicated, but the nice thing is the OS handles it for you. So far I haven't talked about, at all, explicitly loading this thing in.
We haven't even talked about how to even split and fork and join. Fork myself and join it back. We haven't done any of that stuff. We're just talking about the big picture.
Mostly we're talking about what the OS has been doing all along, and that's what's happening. We're going to see how to make this work.
We're getting lower and lower in the abstraction level of being able to do this ourselves, explicitly touching some code that actually splits this stuff and joins it up in a couple of lectures.
All right. 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.