YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 38.3 - Dependability- Parity, ECC, RAID: Error Detection

[CS61C FA20] Lecture 38.3 - Dependability- Parity, ECC, RAID: Error Detection — Transcript

by CS 61C Departmental · 2,147 words · 364 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:04[Music]
0:09hello
0:10and welcome back to our module on
0:12dependability so we have defined
0:15metrics for measuring dependability and
0:18along the way also we define how we
0:20measure reliability and availability so
0:24before trying to add redundancy let's
0:27try to first
0:28figure out how we can detect
0:31whether we have an error or some kind of
0:34fault in a system
0:36that we need to react to
0:41so let's get into that
0:46errors in compute systems can happen
0:49anywhere i mean we can have an error in
0:51our alu we can have an error in our
0:53register file but most likely it's going
0:55to be somewhere in the memory system
0:57and it will be in dram in particular so
1:00what
1:00we plan to do now is to add a little bit
1:04of redundancy some redundant bits that
1:06are going to
1:06enable us to detect that an error
1:09happened
1:10in a particular
1:14word in the memory so we are going to do
1:17that
1:18by introducing so-called error detection
1:20and a little bit later correction codes
1:23so you know why do we see why is it most
1:26likely that we're going to see
1:28an error in memory well the reason is
1:31that we have so many memory cells out
1:33there
1:34and they're tiny so when we look at dram
1:37dram is essentially
1:39in in the essence every bit is a tiny
1:41little capacitor that stores a little
1:43bit of a charge
1:44and if that charge that is stored in the
1:47dram cell gets disturbed
1:49we may think that we have written a 0
1:52into a cell but we will
1:53read a1 why would that happen it can
1:56happen because of a disturbance is in a
1:58power supply
1:59or may happen because a particle
2:04in the form of a cosmic ray um
2:08cosmic particle struck that particular
2:11location
2:11and flipped a bit essentially charge
2:14that capacitor
2:15by enough that to change the value
2:18that corresponds to a zero to something
2:20that corresponds to a1
2:22that is a particular type of an error
2:24that is called the soft error
2:25there is really nothing wrong physically
2:27with a memory
2:28just error happened while the data was
2:32sitting in there so when we re-execute
2:35things
2:36they're going to be working just fine
2:39as opposed to those there are hard
2:41errors uh
2:43a bit cell or
2:47word in the memory or an
2:50entire chip can fail and those are
2:53so-called
2:54hard failures or hard errors
2:59and in there we need to use a different
3:01kind of redundancy to repair that
3:03we can repair memory chips inside that's
3:07outside the scope of this
3:09course but you know we can
3:12replace a faulty chip or a faulty
3:16disk drive in a compute system we'll
3:18talk a little bit more about that
3:20a bit later um the way how we
3:24guard against soft errors
3:28is by using so-called error detection
3:30and error correction
3:32codes or edc's and eccs for short
3:35we can't guard really by shielding our
3:38compute system somehow i mean
3:40some of these cosmic particles can
3:42travel through
3:43the earth so you know there is a pretty
3:46low chance that we can guard
3:47uh our systems by some other way
3:50so they're gonna hit us no matter what i
3:53mean they're hitting us
3:54they're hitting me as i'm speaking right
3:56now um
3:58and there there may be a chance that
4:00they're going to flip the bit
4:01so the idea here is to add a little bit
4:04of redundancy
4:06in our memory systems to tell us if a
4:09particle strike
4:10or supply disturbance has altered some
4:13bits
4:16so these extra bits as opposed to just
4:19replicating the entire words
4:21present a lot less overhead a lot less
4:23redundancy
4:24but protect you know give us a
4:28[Music]
4:29good enough protection so
4:33the way how it also works is that
4:37we stake our
4:42regular results of computation before
4:44storing them
4:45we manipulate them into some kind of
4:48a code space and that code space as the
4:50redundancy
4:52so if a fault charges uh changes this
4:56valid code into an invalid one we can
4:59detect that because
5:00that codeword does not exist in our code
5:04set
5:04i'm talking a lot about you know a lot
5:07about
5:08kind of hypothetical stuff let's get
5:10into more practical things but before we
5:12get into real practical examples
5:14let's first introduce something
5:16important that is often
5:17used for understanding these codes which
5:20is uh
5:21so-called the hamming distance it is
5:23named after richard hamming one of the
5:25computing pioneers who
5:26worked at bell labs for a long time and
5:28then later moved to academia
5:30he made some pioneering contributions
5:33for
5:34uh terror correction and detection and
5:36he did win a touring award
5:41hamming distance is essentially
5:44a difference in the number of bits
5:47between
5:48two binary numbers but when looked bit
5:51by bit you know here is an example
5:53let's call let's say that we have one
5:54word that is p the other word that is q
5:57and we would like to find out how
5:58different they are in terms of bits
6:01so the word p is 0 1 1
6:050 1 1 and q is 0 0 1 1 1
6:081. we compare them bit by bit
6:12and find out how many of them are
6:14different so
6:16in the most significant bit both of them
6:18have zeros the next significant bit
6:21are is different it is one versus a zero
6:24so we have
6:25a distance of one so far the next bit
6:28bits are once and we just
6:31um you know that's the same so we don't
6:34have to
6:34keep track of that the fourth more
6:37significant bit in the word p
6:39is a zero the word q is one so the
6:42hamming distance
6:43is two and the two least significant
6:47bits are both ones
6:48so we don't increase this hamming
6:50distance counter so the distance between
6:52words p and q is two
6:55let's do another example if p is the
6:58same as what we had before
7:00zero one one 1 1 and q is a bit
7:02different
7:031 1 0 0 0 1 what is the difference
7:06between p and q well
7:08let's just compare them at the most
7:09significant bit position we have a diff
7:11distance so 1 then same
7:15this different one versus zero in the
7:17third bit position
7:19this one is the same the fifth bit
7:22position is different so we got three
7:24and the final bit is the same so the
7:26distance between p and q
7:27is three
7:34so let's see how can we utilize this
7:39when we work with our binary numbers our
7:41results of computations are
7:43just binary words and the hamming
7:45distance between them
7:47is one right we use a binary
7:49representation that
7:50doesn't have much or any redundancy
7:53there and because we want to
7:56efficiently use our compute hardware
8:03what are we trying to do here is
8:06to not completely utilize
8:10all of our storage to
8:14store just different binary numbers we
8:16would like to store the code words
8:18these are sufficiently different from
8:20each other such that
8:22they have say a hamming distance of two
8:25so what happens
8:26if the words have a hamming distance of
8:29two
8:30and if there is a single bit error
8:33well we started with a legal code word
8:37that corresponds to our code space and
8:40the
8:40particle struck a bit and that bit
8:42flipped
8:45so the new word since it has a distance
8:47of one from the
8:49valid code word is an invalid code word
8:53and we can detect that we had an error
8:57so let's see a practical example how to
8:59do that this is a lot of
9:01complexity but the first practical
9:03example is something that is very
9:04commonly used and it's very simple
9:06it is adding the parity bit
9:10so in our computation we come up with a
9:12binary word
9:14and for that value of a binary word
9:18what we do before writing into the
9:20memory we add
9:22a parity bit so we add a little tag in
9:25the form of an extra bit
9:27that forces the word to be stored in the
9:30memory
9:31to have even parity
9:36um so if we are working for example with
9:398-bit words
9:40in this example and exact same thing
9:42applies for 32-bit words
9:44how would we find out how many
9:48ones that we have in this world well
9:50we'll just pass it through
9:51and ain't input xor gate and that xor
9:54gate is going to produce our
9:56parity bit what we do then we
10:00take all these nine bits eight bits that
10:02is
10:03our data value and the parity bit and
10:06store them all
10:07together in the memory we need to have
10:10a little wider memory for that and
10:13that's the reason
10:14why in some of these drum dimms we have
10:17nine chips one of those stores the
10:20parity
10:22okay now when we read that back we would
10:25like to check
10:26if our data is correct
10:29so we will read all nine bits
10:33and try to find out if the parity is
10:36even
10:36uh how we're going to do that well we'll
10:38pass it again
10:40through an xor gate this time and
10:42exergate with eight inputs
10:44and we're going to get the check bit at
10:46the output the check bit
10:48if the value is 0
10:51then there is an even number of ones
10:54at its input so the word is valid
10:58if it is a 1 we have an error so what do
11:01we do with that
11:02error well that's a
11:05perfect reason to draw an exception and
11:08have operating system handle it
11:12okay one thing that you can convince
11:15yourself and
11:16we're going to walk through that a
11:17little bit later is
11:19since we are storing essentially
11:26redundant numbers here we can convince
11:28ourselves that the minimum hamming
11:29distance
11:30of a parity code is two we have to have
11:33two bits in error in order to flip from
11:35one valid code word
11:36to another valid code word so
11:39we detect that this codeword is not
11:42valid
11:42by um checking the parity bit
11:46now we have limited
11:49ability for checking errors right we
11:52will be able only to
11:53check if we have one bit in error
11:57or actually three bits or five bits in
12:01error
12:02if an odd number of bits is in error if
12:04we have
12:05if we flip two bits simultaneously we
12:07will not detect that
12:08so but in general just a single parity
12:11bit
12:12is good enough because you know memory
12:15systems are generally
12:16are designed in a way that when hit by a
12:19particle
12:20generally just one bit will flip
12:26here is a simple example of how we add
12:29parity bits
12:30so we start with the data word 0 1 0 1
12:340 1 0 1 8 bit data world
12:38so we inspect that word by using xor
12:41gate and we find out that we already
12:43have even parity so our
12:45added parity bit should be a0 so we are
12:48adding a 0 and taking
12:50this 9 bit word to store into the memory
12:54so our parity here is going to be even
12:56if you have a different
12:58data work here 0 1 0 1 0 1 1
13:011 that one has 5
13:04once so in order to keep the parity
13:08even we are going to add a 1 as a parity
13:12bit
13:13so the word 9-bit word that is written
13:15in memory is going to have an
13:17even number of months now when we read
13:20this
13:20let's take a look at this first word
13:22that we have stored in memory we now
13:24read it out from the memory
13:25if we read it the way it is
13:29with an even number of ones then the
13:32parity is even
13:34so there is no error on the other hand
13:36if there is a bit flip in this case
13:38there is a
13:39bit flip in the most significant memory
13:42bit location we count the number of ones
13:44one two three four
13:45five therefore we have an odd parity
13:49output of that xor is a one there are
13:52four there is an error
13:53what do we do at that point we draw an
14:00exception
14:02and another quick question that you may
14:05ask yourself
14:06so what happens if there is an error in
14:07the periodic if all these eight bits
14:09from our original word
14:11are correct just the last bit
14:15is our parity bit got flipped from zero
14:17to one well we're still going to detect
14:19an error we don't know where that
14:20error is um so in once in some sense the
14:23parity bit is protected but on the other
14:25hand
14:26um you know there would have been no
14:28error if we didn't have a period of it
14:29so
14:31we just look at that we're going to talk
14:33about
14:34error correction after a quick break see
14:37you then

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 38.3 - Dependability- Parity, ECC, RAID: Error Detection by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,147 words across 364 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.