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: Hello, and welcome back to our module 1, Dependability.
So we have defined metrics for measuring dependability. And along the way also, we defined how we measure reliability and availability.
So before trying to add redundancy, let's try to first figure out how we can detect whether we have an error or some kind of a fault in the system that we need to react to.
So let's get into that.
Errors in compute systems can happen anywhere. We can have an error in our ALU, we can have an error in our register file.
But most likely, it's going to be somewhere in the memory system. And it'll be in the RAM, in particular.
So what we plan to do now is to add a little bit of redundancy, some redundant bits that are going to enable us to detect that an error happened in a particular word in the memory.
So we are going to do that by introducing so-called error detection, and a little bit later, correction codes. So why is it most likely that we are going to see an error in memory?
Well, the reason is that we have so many memory cells out there, and they're tiny.
So when we look at DRAM, DRAM is essentially — in the essence, every bit is a tiny little capacitor that stores a little bit of a charge.
And if that charge that is stored in the DRAM cell gets disturbed, we may think that we have written a 0 into a cell, but we will read a 1.
Why would that happen?
It can happen because of disturbances in the power supply, or may happen because a particle in the form of a cosmic ray, a cosmic particle, struck that particular location and flipped the bit, essentially charged that capacitor by enough
to change the value that corresponds to a 0 to something that corresponds to a 1. That is a particular type of an error. That is called a soft error.
There is really nothing wrong physically with the memory, just error happened while the data was sitting in there. So when we execute things, they're going to be working just fine.
As opposed to those, there are hard errors. A bit cell or word in the memory or an entire chip can fail.
And those are so-called hard failures or hard errors.
And in there, we need to use a different kind of redundancy to repair that.
We can repair memory chips inside — that's outside the scope of this course, but we can replace a faulty chip or a faulty disk drive in a compute system.
We'll talk a little bit more about that a bit later.
The way how we guard against soft errors is by using so-called Error Detection and Error Correction Codes, or EDCs and ECCs for short.
We can't guard, really, by shielding our compute system somehow.
I mean, some of these cosmic particles can travel through the Earth, so there is a pretty low chance that we can guard our systems by some other way.
So they're going to hit us no matter what. I mean, they're hitting us and they're hitting me as I'm speaking right now.
And now there may be a chance that they're going to flip the bit.
So the idea here is to add a little bit of redundancy in our memory systems to tell us if a particle strike or supply disturbance has altered some bits.
So these extra bits, as opposed to just replicating the entire words, present a lost lot less overhead, a lot less redundancy, but give us a good enough protection.
So the way how it also works is that we take our regular results of computation, before storing them, we manipulate them into some kind of a code space, and that code space as the redundancy.
So if a fault changes this valid code into an invalid one, we can detect that, because that code word does not exist in our code set.
I'm talking a lot about a lot about hypothetical stuff. Let's get into more practical things.
But before we get into real practical examples, let's first introduce something important that is often used for understanding these codes, which is so-called the Hamming distance.
It is named after Richard Hamming, one of the computing pioneers who worked at Bell Labs for a long time and then later moved to academia.
He made some pioneering contributions for 2-error and correction detection. He did win a Turing Award.
Hamming distance is essentially a difference in the number of bits between two binary numbers, but when looked bit by bit. Here is an example.
Let's say that we have one word that is p, the other word that is q, and we would like to find out how different they are in terms of bits.
So the word p is 011011 and q is 001111. We compare them bit by bit and find out how many of them are different.
So in the most significant bit, both of them have 0's. The next significant bit is different. It's this 1 versus a 0. So we have a distance of 1 so far.
The next bits are 1's. And that's the same, so we don't have to keep track of that.
The fourth more significant bit in the word p is a 0, in the word q is 1. So the Hamming distance is 2.
And the two least significant bits are both 1's, so we don't increase this Hamming distance counter. So the distance between the words p and q is 2. Let's do another example.
If p is the same as what we had before, 011011, and q is a bit different, 110001, what is the difference between p and q? Well, let's just compare them.
At the most significant bit position, we have a distance, so 1. Then the same, different one versus 0 in the third position. This one is the same.
The fifth bit position is different, so we get 3. And the final bit is the same. So the distance between p and q is 3.
So let's see how can we utilize this. When we work with our binary numbers, our results of computations are just binary words. And the Hamming distance between them is 1, right?
We use a binary representation that doesn't have much, or any, redundancy there, and because we want to efficiently use our compute hardware.
What are we trying to do here is to not completely utilize all of our storage to store just different binary numbers.
We would like to store the code words that are sufficiently different from each other such that they have, say, a Hamming distance of 2.
So what happens if the words have a Hamming distance of 2 and if there is a single-bit error? Well, we started with a legal code word that corresponds to our code space.
And the particle struck a bit, and the bit flipped. So the new word, since it has a distance of 1 from the valid code word, is an invalid code word.
And we can detect that we had an error. So let's see a practical example how to do that. This is a lot of complexity.
But the first practical example is something that is very commonly used, and it's very simple. It is adding the parity bit. So in our computation, we come up with a binary word.
And for that value of a binary word, what we do before writing into the memory, we add a parity bit.
So we add a little tag in the form of an extra bit that forces the word to be stored in the memory to have even parity.
So if you are working, for example, with 8-bit words in this example — and the exact same thing applies for 32-bit words — how would we find out how many 1's do we have in this word?
Well, we'll just pass it through and aim to input XOR gate. And that XOR gate is going to produce our parity bit.
What we do then, we take all these nine bits — eight bits that is our data value, and the parity bit — and store them all together in the memory.
We need to have a little wider memory for that and, that's the reason why in some of these different DRAM DIMMs, we have nine chips, one of those source the parity.
Okay. Now, when we read that back, we would like to check if our data is correct. So we will read all nine bits and try to find out the parity is even.
How we're going to do that? Well, we'll pass it again through an XOR gate, this time an XOR with eight inputs. And we're going to get the check bit and the output.
The check bit, if the value is 0, then there is an even number of 1's at its input. So the word is valid. If it is a 1, we have an error.
So what do we do with that error? Well, that's a perfect reason to throw an exception and have operating system handle it.
Okay, one thing that you can come into yourself — and we're going to walk through that a little bit later — is since we are storing essentially redundant numbers here, we can convince ourselves in the minimum Hamming distance of a parity code is 2.
We have to have two bits in error in order to flip from one valid code word to another valid code word.
So we detect that this code word is not valid by checking the parity bit. Now, we have limited ability for checking errors, right?
We will be able only to check if we have one bit in error or, actually, three bits or five bits in error if an odd number of bits is in error.
If we flip two bits simultaneously, we will not detect that.
But in general, just a single parity bit is good enough, because memory systems are designed in a way that when hit by a particle, generally, just one bit will flip.
Here is a simple example of how we add parity bits. So we start with the data word 0101 0101, 8-bit data word.
So we inspect that word by using XOR gate, and we find out that we already have even parity. So our added parity bit should be a 0.
So we are adding a 0 and taking this 9-bit word to store into the memory, so our parity here is going to be even.
If you have a different data word here, 0101 0111, that one has five ones.
So in order to keep the parity even, we are going to add a 1 as a parity bit.
So the 9-bit word that is written in memory is going to have an even number of 1's.
Now, when we read this, let's take a look at this first word that we have stored in the memory. We now read it out from the memory.
If we read it the way it is, with an even number of 1's, then the parity is even. So there is no error.
On the other hand, if there is a bit flip — in this case, there is a bit flip in the most significant memory location — we count the number of 1's — 1, 2, 3, 4, 5 — therefore, we have a non-parity.
The output of that XOR is a one. Therefore, there is an error. What do we do at that point? We throw an exception.
And another quick question that you may ask yourself, so what happens if there is an error in the parity rate if all these 8 bits from our original word are correct?
Just the last bit is our parity bit, got flipped from 0 to 1. Well, we are still going to detect an error. We don't know where that error is.
So in some sense, the parity bit is protected. But, on the other hand, there would have been no error if we didn't have a parity bit. So we just live with that.
We're going to talk about error correction after a quick break. 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.