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ả.
[MUSIC PLAYING] PROFESSOR: Hi, welcome back.
It's time to introduce the concept of pipelining, which will increase the compute throughput. But we are not going to start with computers and compute tasks.
For now, let's start with a real life example, or almost real life example. Let's suppose that Dan and Bora go back to college.
And they're in the same dorm with some of your favorite TAs, Avi and Caroline.
And now on, say, a Sunday night, Avi, Bora, Caroline, and Dan all need to do the laundry. In the basement of the dorm, there is a laundry room.
And the laundry room has a washer, a dryer, a place to fold the laundry. And then, a means to stash the laundry to take it back to the dorm.
So the washer takes 30 minutes, the dryer takes 30 minutes, folding takes 30 minutes because it's kind of tight space in there.
And then stashing takes 30 minutes because we need to walk our laundry back to our rooms.
So since there is 4 of us that need to do our laundry, we have four tasks. A for Avi, B for Bora, C for Caroline, and D for Dan.
So let's see how we could do that.
So if you have a strange RA, they may decide that we have to do it sequentially, meaning that only one person can do the laundry at a time.
So first we'd go Avi. At 6:00 PM, he would start his laundry and he would go through his four cycles or four phases of processing the laundry.
He would first go wash it for 30 minutes, then dry it, fold it, and stash it, and will be done at 8:00.
Then Bora can go at 8:00 and wash it, dry it, fold it, and stash it. He'll be done by 10:00 PM. Then Caroline can start.
She would wash it, dry it, fold it, and stash it. Will be done by midnight.
And Dan would have to start at midnight and finish his four phases of laundry execution by 2:00 AM.
Is there a better way to do this? Yeah, I mean, if you look at this scenario, we had 3/4 of a time our resources were not utilized.
Washer was used for 30 minutes every two hours, dryer was used for 30 minutes for every two hours, and the folding area was utilized only for 30 minutes every two hours.
We used the stairs for stashing our laundry only 30 minutes, every two hours, in two hours.
So we certainly can try to do multiples of these things concurrently, multiples of these phases of laundry concurrently.
So instead of having sequential laundry that takes eight hours for four loads, perhaps we can do better. So here is an approach of pipeline laundry processing.
We still have four tasks — Avi's, Bora's, Caroline's, and Dan's. And we are still going to start at 6:00 PM, but we should be able to take less time if we overlap our tasks.
So Avi still has to start at 6:00, and he's going to go through his cycle of washing, drying, folding, and stashing. And he will be done at 8:00.
But Bora doesn't have to wait to start at 8:00.
Bora can just start at 6:30 and go through the four phases of laundry processing.
Caroline can start at 7:00, wash, dry, fold, and stash. And Dan can start at 7:30 and be done by 9:30, just in time to record his next lecture.
All right, so there was a dramatic speed-up that happened here. But notice what happened, let's just make sure that we understand exactly what happened.
The speed-up was, instead of eight hours, it took us three and 1/2 hours for four loads. So that's pretty good. There are still things that happen sequentially.
So phases of laundry processing still happen sequentially. So each one of us took two hours, like before.
But multiple phases, or multiple stages of laundry processing, happen simultaneously.
And in particular, take a look at what happened at 7:30.
While Avi was stashing his laundry, Bora was folding his laundry, Caroline was drying her laundry, and Dan was washing his laundry, which fully utilized all the resources.
But while we were starting up, the resources were not fully utilized.
It took us three cycles to fill up the pipeline so that we had the full utilization. And then it took us three cycles to drain the pipeline.
So if that is not obvious, at 6:00 PM only the washer was used.
At 6:30 PM, washer and dryer were used, and so on.
Now, there if there 1,000 people trying to use this laundry system, it wouldn't have taken 2,000 hours.
If we were to pipeline it, it would have taken 503 hours, because it would take us still three cycles to fill the pipeline, then everybody would be running four tasks, four tasks in four phases concurrently.
And finally, in the final three cycles, we would drain that pipeline and all 1,000 loads would be processed in roughly 500 hours.
Okay, so here are some of the key points to take away about pipelining laundry processing.
Pipelining doesn't help the latency of a single task, because a single task still takes two hours, no matter what. But it helps with the throughput of the entire workload.
The entire workload got done significantly faster — in this case, 2.3 times faster.
There are multiple tasks that are operating simultaneously or concurrently using different resources. Now, the potential speed-up equals to the number of pipe stages that can be simultaneously used.
In this case, there are four of them, so the theoretical speed up that, we can have is 4.
But we did not achieve the speed-up of four, we achieved the speed-up of 2.3 because we needed some time to fill the pipe and then drain the pipe.
If there were 1,000 tasks, that we're using the same pipeline, then we would have gotten much closer to the 4x of theoretical speed-up.
So that's one of the key ideas.
A few other takeaways here. Now, somebody decides to invest in improving the laundry system.
So supposedly they get a new washer that takes 20 minutes instead of 30 minutes.
And then new stashing system perhaps uses an elevator and it'll take 20 instead of 30 minutes. How much would that improve the whole operation of the laundry in that dorm.
So for example, if you had 1,000 people using that laundry, would it dramatically shave it instead of 500 hours? Would it take about 2/3 of 500 hours.
No.
Because the throughput of this whole system is set by the slowest tasks or the slowest resources that we have in the pipeline, this would shave off 10 minutes of the beginning and 10 minutes of the end.
The washer is going to take 10 minutes less, will be done in 20 minutes instead of 30. And stashing will be done in 20 minutes instead of 30.
So for four of us, instead of three and 1/2 hours, it would take three hours and 10 minutes.
But it would not change the time that it takes 1,000 people process their laundry. It would still be about 500 hours.
Why is that?
Because even if these tasks take 20 minutes in the beginning and the end, the time is set by the slowest resources that we have in here, which will be the washer and the folding station.
That's about it. So what we are going to do in the next segment, we are going to translate this to our RISC-V pipeline. 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.