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 explore cache coherency, one of the hardest parts of putting together a system that has multicore, and each core has some number of caches, and the caches are either shared or not shared.
It's hard stuff. So from the point of view of an architect, we need to be thinking about how to keep the cache values coherent.
You saw the end of the last lecture with what happens when they have 20, and I want to write my 40, and now the wrong value happens. Caches should only make things faster.
They should never change the value. So caches — the same value that should return without caches and also same with multicore.
If you do it right, just adding more cores, adding some parallelism, shouldn't change the value, just give it to you faster.
So again, we just have — the same value should come out at the end of the day, just faster. So here's a model.
So the idea is when any processor has a cache miss or write, you have to notify the other processors. There's an interesting way.
We talked about the only way you can connect with other processors, other cores, is through memory. I can write your variable and wait for you to read it.
But there is a way to actually communicate with them that we're going to add, and we can ask them to do things. We can ask for their values in a certain block.
I can also ask them to invalidate a block, and the way you invalidate a block because you make it invalid. Very easy.
So we're going to add some communication between cores to be able to actually do some of the things we're going to do.
So if I'm only reading, and the model before from the last lecture — if we're only reading, other processes can have copies. We all have copies. That's fine.
We're just reading. It's just read-only memory. Fine, fine. On writes, you're going to imagine we have to invalidate the other copies.
And so we talked about it.
Some researchers came up with a way, a protocol that they called the snoopy protocol, to think about different ways to categorize each block in each core as one of several states.
And then depending on what you're doing, reading and writing, you change the values in those states, a kind of interesting way to think of that.
And the other cool thing is you can snoop across to ask what the values of their — here's an index. Here's a tag. Do you have the same one?
And if so, what's your state? And then do something. We can have that communication. And then I can say, please invalidate your copy if you have the same one.
So that's really neat, and we always have to check the tags to make sure it's the same guy. That's important. So how do we keep them coherent?
Each cache is going to — again, of each block, you going to keep track of some type of bits to keep a track of a state. We'll label these states.
Number 1, Shared. This is like reads, very easy. I have an up-to-date copy, so this is from the point of view of each core.
Each core has a — if you're Shared, it means that I have an updated copy of the data. Another cache may also have a copy. This is the easy case, Shared.
Everything's shared. Five people share, a hundred people share — all fine. Modified is different.
Modified says, from my point of view, it's modified — if my state is Modified, means that I have the up-to-date copy, so my cache has the up-to-date copy.
It's changed. It's dirty. And what dirty means is A, I'm using a write-back system, so the guy behind me, Sacramento, is out of date, and no other cache has a copy.
We don't mind. This is like vanilla write-back caches. A write-back cache says that I have the possibility that my value is out of date with memory. That's no trouble.
I can reads and writes.
I don't have go to memory, and only when I kick this guy out or I'm paged out or something, I need to then flush that back and push it back to memory.
So I only go to Sacramento when I need to. But the key here, Modified is, nobody else can have that, okay? So that's the idea. This is for a block-by-block basis.
There are two additional states for performance optimizations. We're going to add the idea of Exclusive.
And Exclusive says — it's similar to Modified, but Exclusive differs in that memory is up to date. So if I'm Exclusive, that means that nobody has — remember, Modified meant nobody has a copy.
Exclusive means nobody has a copy. But in the Exclusive case, memory is up to date. In the Modified, it is not up to date, okay? So this is great.
I know for my Exclusive, that means if the block's replaced, I don't have to write to memory, because I know that, in a way, my dirty bit is not flagged.
So it's only Exclusive, how to replace the dirty bit, in that sense of it. And that supplies data on a read.
If I'm making a read, obviously, I have a copy, so I can just read from that. Fine, okay? And memory's up to date, so I don't have to kick it out.
If I ever kick this block out, I don't need to go to memory. I like Exclusive as well. Owner. Owner's a little bit more complicated, so we'll spend some time talking about it.
Owner says, my copy is up to date. I'm the Owner. And what that means is other caches can have a copy, but I'm the Owner, and they have to be in a Shared state.
So when you have the Shared state, I have to be the Owner. So let's think about that.
What it means — here's the fun part, and I'll read this to make sure — there's a lot of details.
So I'm going to make sure I read them to make sure you understand all the pieces of this. So I'm one with several with a valid copy.
The other copies are shared, but I have the exclusive right. As the Owner, I have the exclusive — don't get this confused with the word "Exclusive."
I'm the only one who has a right to make changes to it. But how do I make those changes? This is the fun part. This is the optimization.
I make changes — let's say the value is 20. We all have 20. We're all good, but I'm the Owner. I want to make it to 40, okay?
One model, if I use this, I — and by the way, memory is consistent here. So we're not talking about memory being inconsistent.
So far, the only way memory is inconsistent is in the Modified state, okay? So I'm sorry. Memory might be inconsistent. I'll say this again.
Memory might be inconsistent. I'm the Owner. I ave the up-to-date copy. Memory might be inconsistent.
Okay, now, watch this. Other caches are shared, but I'm the Owner. I'm the one who owns really — since it's a memory spot.
And now if another copy — if I make a change — it was 20 for everybody, but I'm the Owner. I'm going to make it 40.
Really — but they're shared — what I could do is I could share my 40 with the other caches. So watch this. I push the 40 to my cache.
Now it's a 40. That's the right value. And I push it to the other caches via the interconnect. Now they all have 40.
Now, here's the catch — what happens if there's a core that never had it in their cache at all, and they go to read the value?
Remember, it's 40 in all the people who are using it. I'm the Owner, they're Shared, and they're all reading the 40 correctly. And I want to go grab the current value.
I'm not going to go to memory. First of all, I never go to memory if I can help it.
It would be great if, when I went to read this value, I could ask the other guys, do you have this block in your cache? And who is the Owner?
So I may ask, guys, hey, folks, could the Owner please tell me what the value of this — anybody have it?
So you can pass this to the other cores, and they say, the other caches say, hey, I'm the Owner — my cache, the Owner, yeah? I would say, I'm the Owner.
It is 40. And I'm basically passing the 40 to another core that never had it. Then they become Shared, and then they're fine. So this neat.
So look at this. So it says, Owner cache — the last line says, must — this the key here. "Owner cache lines must respond to a snoop request with data."
So that's the snoopy idea. I didn't have it. I want to read a value. It's a 40, but I don't know that.
My cache is empty. I ask, does anybody else have it? And the owned cache has to respond with the 40. I load the 40, put it in my guy.
I become another Shared family, okay? Another model is if I wanted to modify it, I could change it to the Modified state if I wanted to.
My cache line can be changed to the Modified state. Remember what Modified means. Modified means it's out of date, and nobody else has it, so they are all invalid.
So here, this line says, "The cache line may be changed to the Modified state after invalidating all Shared copies or changed to the Shared state by writing the modifications back to main memory."
So two ways to kind of get out of this — if I'm the Owner, other people have the 40. Memory is wrong. That's what we got.
I could either write my data all the way to memory, go to Sacramento, write the 40. Now that's consistent. All the 40's have it. They all have the 40's anyway.
That was fine. And now we're all Shared, so I go from Owner to being Shared again. Anybody else can now grab the Owner if they want to change it.
So I could do that. I could also decide — you had the 40's, but why not just invalidate — if I invalidate you, then I can now be changed to Modified.
Now, Modified means still inconsistent with memory. I've got a 40 memory of something else, but I'm Modified. I can invalidate them as well.
So there are two kind of options you can, as you're thinking about how to transition, there's a very complicated transition state diagram that talks about all these states and how you move for each of the states.
We don't teach it in 61C. We teach in our Architecture class. You'll learn about in other classes. You'll learn.
But there are ways to think about how you move from Owner to — how do you move from Owner to Shared? I just told you.
You can move from Owner to Shared by writing to main memory. Now that memory is consistent, and now it can be part of the Shared family.
Or how to move from Owner to Exclusive if I wanted to — by doing that, I would just invalidate the other copies, and now I'm the only exclusive one.
It's still not in main memory. It's still Modified. It's inconsistent with main memory, but I'm in the not Exclusive, but I'm in a Modified state.
So all those things — they're complicated, state transition diagram. Here's the picture. Here are all the valid pairings. This is me.
I'm on the left. I'm going to change pen really fast here. I'm on the left, and here's me, and here's all the others, others.
And so here's me. I can be in the Modified state. Remember the Modified state. And nobody else — there's no other states that can be — for them, they have to all be invalid.
Modified means nobody else in any other state. Modified means I have it. Everyone else doesn't have a copy at all of that block. We're talking about if a block — on a block level.
Or I could own it. I talked about before, if I own it, other people could be invalid. You can not have it at all. That's fine.
You never did anything. I'm a core that's asleep. Fine, you're invalid. I don't care about you.
Your cache is empty or cold. But other people could have a Shared version. They are all Shared while I'm Owned, okay? There's that one.
Or I have Exclusive rights, and then nobody else can have it. That's what Exclusive means.
Or, again, I could be the Shared copy, and somebody else is the Owner, or we could all just be doing reads, and I have a Shared copy, and you have a Shared copy too.
So that's it. Very simple case, but you can never have — for example, you can never have two people — actually, you can never have two Exclusives. You can never have two Owners.
You can never have to Modifieds. This is very clean. This is a very clean way of thinking about the states of the cache.
But in a clever way, the Owner is a very clever way that people could be, without having to go to Sacramento, be reading from me.
Very interesting to think about how this stupid protocol where you could be poking and talking to — like, Sacramento is far away, and we're talking.
It's almost like the teacher's at the front of the room, and we're kind of talking to the neighbors. Hey, do you want a piece of cache? Here's a value.
You're the owner? Do you have it? Yeah, let me grab it from you. You're the Owner.
I'm Shared. Okay, grab it now. The conversation's happening along in the back row as the memory is all in the front row as the instructor in some way.
So let's actually look at one of these models. So now let's go back in time. Now I've got two caches that, at memory location 1000, have a copy of the value 20.
And I want to write a 40. And I'm processor 0. It's not in my cache, so I check my interconnect network, and I decide to invalidate the other copies.
I invalidate their copies. And now I'm going to read the 40. I'm going to store the 40 in my cache, store it in memory, and we're all consistent.
So this is a way that we can make sure that we never have the problem where I wrote a 40, and you still keep your 20's, but I have a 40, and so two blocks are — you'll never have that case where two blocks don't have the same value ever.
If I'm going to do a write to a 40, I'm going to either invalidate them or grab Owner and pass my 40 to them and update them to 40.
But you're never going to have a kind of arresting photograph of the state where this guy thinks it's 1,040, and this one thinks it's 1,020. Never going to happen.
Either I'm writing a 40, and I invalidate all everybody else, and nobody else has it. And they just had copies anyway. That's fine. Caches are just copies.
They were just read-only copies, not written copies, not out of sync. They were synced with memory. That's fine.
Or I have a 40, and I'm going to pass the 40 to the other people over there.
Whether memory is inconsistent or consistent, it's all there, but the Owner's job is to finally connect with memory. If it gets kicked out, make sure to write that 40 eventually in memory.
That's the part that's interesting here. It's very fun and really interesting if you dig deeper into what the snoopy state diagram is and how you move from state to state.
Kind of fun. Now let's bring yourself a really big issue, and this is something that we're going to see often as we have more and more cores dealing with really big blocks.
So what's the problem here? This looks fine. I've got a block size of 32 bytes. No problem.
I've got two processors, two caches. And you can maybe already see there's an issue here. Processor 0 is reading and writing variable X that happens to live at address 4000.
Processor Y is reading/writing variable Y that happens to live at an address 4012. Well, X at 4000. Y is at 4012. These are independent.
These are totally independent. I'm reading/writing in here. You're reading/writing in there. Well, what's going to happen?
Can you already see what's going to happen?
Well, that block is going to ping-pong between those two caches, as each one thinks they're accessing the same information, and you want to make sure we don't have those issues.
And so only one person is going to own it, even though, in theory, you could build a system that both of them could write to just an area of it.
But because you only check at the block level, you can't have that. It'll just ping pong in and out, in and out, in and out from the two areas.
And each one thinks that I have it. No, you have it. No, I have it. No, you have it.
And this is a problem. So how do you prevent it? Let's see. How do we prevent it?
Well, one way to — I'm already — pause the video and think about it. Well, one way to reduce the possibility of it is if I have smaller block sizes.
The larger the block size, the more the chance of, I'm going to be writing to areas of the array, and multiple areas of the processor might do that.
You could also think from the programming standpoint — if you knew the size of the block, you could make sure, if you did this really well, that you never have a processor share any space at all on the same block line as anybody else.
Just make sure that you own this part of memory, and I'm down here, and you're down there, and you're down there, and you have that issue as well.
So let's think about how to resolve this. Let's think about — this is all review. Three C's. These were the three kind of misses you had with caches.
You have a compulsory miss. These are a cold-start miss. You've got a block never seen before. Everyone has to do this.
First access to the block, you got to take this. The solution for a cold-start miss is — for compulsory misses, you increase the block size.
Certainly have more penalty to go to Sacramento, but when you're there, now you're loading in more of it, and now you have less of memory.
The larger the block size, less of memory, from a block point of view, have to take that hit. I grabbed it, and I'll grab a huge block. That's great.
And while I was in Sacramento, I loaded — now all of those guys don't have to have compulsory misses because they're loaded in. So that's nice.
Capacity misses, which means not compulsory, but a capacity miss. Well, if I only had a larger cache, I wouldn't have that capacity. Well, make the cache larger.
Solution is make the cache larger, okay? Or a conflict miss. We saw that. So not compulsory or capacity, but a conflict miss.
The solution is, well, think about more associativity. We don't have a direct map or two way? Make it four way or make it fully associative, and think about that.
So either increase the cache size, increase associativity, or work on the replacement policy. Maybe look at the workload you have and be smarter about your replacement policy.
The fourth C — this is the fourth C. It's called a coherence miss. It means within one block, two different cores think that they have these variables that may be distinct are actually shared.
And so now you're going to have them loaded in and out — as we saw before, I have to invalid the other copies because I'm making a read and a write to this, and have to invalidate the other copies.
But, no, wait, the other guy isn't actually modifying that variable. I modified this part in the block. I'm modifying here. You're modifying there.
Sorry, the rules say that if I own this block, nobody else can have it so that we don't have the wrong copy, so I have to invalidate your copies, and so you're not having this ping-pong here.
So this is also known as a communication miss. This is really hard. It's really, really hard. And in some sense, coherence misses can dominate total misses overall with parallel programs.
That's really interesting. These three Cs — you thought that was the world.
I'm telling you, there's a fourth C, and I'm telling you, not only that, that the fourth C actually can be the biggest problem, the biggest number of misses in this case.
All done, last slide on thread-level parallelism. in conclusion, OpenMP is a beautiful parallel extension to C. There, okay, let's step back even farther, and this is off script.
You don't have to program in C. You can program a lot of other languages that may be easier or harder or more useful for your particular problem.
If you're living in C, OpenMP is a great solution to be able to bring parallelism to your C code. You've got these pragmas.
You've got private variables, reductions, parallel for — parallel for is just — will get you a long way, so play with that.
We know this is easy to learn, but not high level, so it can get you into trouble.
Thread-level parallelism, one of the issues as you're building a system for it, as you're one of the, now, architects below the hardware line, is dealing with cache coherency, coming up with protocols, ways you can have it.
I mentioned where there's a state diagram where you label every block with these tags and think about that, that you want to reduce this, that you want to — first of all, make sure that your system always works.
So cache coherency first. At the base level, make sure that your cache doesn't give the wrong value. That's part of the hard part of this. And false sharing is a concern.
The larger a block size, this sharing, these two variables, these two areas of memory, are not being shared across these two processors, across these two cores, these two threads working on these two cores.
But in fact, there is a false sharing that says, nope, sorry, it's the same block. It must be the same one. No, it's not! There at different areas.
Sorry, we don't have any hardware to solve them. So that's a problem, and that causes these coherence misses. That's it. Watch out for the block size for there.
We're done. We're done with thread-level parallelism. We will see you next lecture, where we talk about — drumroll please — [DRUMMING] warehouse-scale computing and MapReduce. 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.