Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCB2006-10-24John Lazzaro (www.cs.berkeley.edu/~lazzaro)CS 152 Computer Architecture and EngineeringLecture 16 – Error Correcting Codeswww-inst.eecs.berkeley.edu/~cs152/TAs: Udam Saini and Jue SunCS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBF05 TA Notes: Final Project CheckofThe SyncMeisters had everything working besides the test file hammer. However, hammer is the hardest test, so in a sense, their project was a bug or two away from working.Writing back to the regfile when a stall occurs on the cache just before or after needing to write seems to mess up their processor. The other tests worked fine on board.UC Regents Fall 2006 © UCBCS 152 L16: Error Correcting CodesWhen cache bugs make it to product ...(Testing our financial trading system), we found a case where our software would get a bad calculation. Once a week or so.Eventually, the problem turned out to be a failure in a CPU cache line refresh. This was a hardware design fault in the PC.The test suite included running the code for two weeks at maximum update rate without error, so this bug was found.Eric UlevikUC Regents Fall 2006 © UCBCS 152 L16: Error Correcting CodesToday: Computing in an imperfect worldDetecting and correcting RAM bit errorsReplacing lost network packets, recovering from disk drive failureDetecting arbitrary bit errors in network packetsCS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBDRAM Challenge: Cosmic Rays ...VddBit Line+++++++Word Linep-oxiden+n+oxide------Cosmic ray hit.Cell capacitor holds 25,000 electrons (or less). Cosmic rays that constantly bombard us can release the charge!CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBCan this happen in SRAM?Gnd Vdd Vdd Gnd Gnd Cosmic ray discharges CVdd -> Gnd.A race: Can P1 restore middle node to Vdd before P2 flips other node?P1P2CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBPractical efect of a cosmic ray ...ADDIU R1, R0, 7SW R1, 100(R0)Address 100: 0b00...0111Address 100: 0b00...0011Cosmic ray hit.LW R1, 100(R0)After LW, R1 holds 3 but it should hold 7.Bit flips on memory holding instructions are bad too!CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBTo “detect” errors -- add ‘P’, a parity bitAddress 100: 0b00...0011 1Cosmic ray hit.Extra “parity” bit for every word. Not seen by software. Hardware computes it on every write, so that the number of 1’s in every 33 bit word is even (even parity). On a read, count the number of 1s. If odd, a bit flipped.Address 100: 0b00...0111 1PSo, halt the program and reboot? Application may know if this bit matters, but there’s no API to ask it ... Does this work if two bits flip? If three?CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBError Correction: Hamming Codes ...Richard Hamming.Computing pioneer.Famous quote:“Computers are not for numbers. Computers are for understanding.”CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBTrick: Compute parity of subsets of bitsP₂P₁P₀Add 3 parity bits.???Each parity bit computed on a subset of bitsP₀ = D₃ xor D₁ xor D₀ = 0 xor 1 xor 0 = 1 P₁ = D₃ xor D₂ xor D₀ = 0 xor 1 xor 0 = 1P₂ = D₃ xor D₂ xor D₁ = 0 xor 1 xor 1 = 00 Consider 4 bit words.1 0 1D₃D₂D₁D₀D₃D₂D₁P₂D₀P₁P₀Use this word bit arrangement0 11 0 0 1 1“Just believe” for now, we will justify later ...CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBCase #1: No cosmic ray hitsD₃D₂D₁P₂D₀P₁P₀On readout we compute:P₀ xor D₃ xor D₁ xor D₀ = 1 xor 0 xor 1 xor 0 = 0 = C0P₁ xor D₃ xor D₂ xor D₀ = 1 xor 0 xor 1 xor 0 = 0 = C1P₂ xor D₃ xor D₂ xor D₁ = 0 xor 0 xor 1 xor 1 = 0 = C₂ 0 11 0 0 1 1We write:D₃D₂D₁P₂D₀P₁P₀0 11 0 0 1 1Later, we read:If C₂C₁C₀ = 0no errors No errors ... but how do we know that? These equations come from how we computedP₀ = D₃ xor D₁ xor D₀ = 0 xor 1 xor 0 = 1 P₁ = D₃ xor D₂ xor D₀ = 0 xor 1 xor 0 = 1P₂ = D₃ xor D₂ xor D₁ = 0 xor 1 xor 1 = 0P₂P₁P₀CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBCase #2: A cosmic ray hits ...Cosmic ray hit D1. But how do we know that?D₃D₂D₁P₂D₀P₁P₀0 11 0 0 1 1We write:D₃D₂D₁P₂D₀P₁P₀0 01 0 0 1 1Later, we read:C₂C₁C₀ = b101 = 5What does “5” mean?0 01 0 0 1 1The position of the flipped bit!To repair, just flip it back ...D₃D₂D₁P₂D₀P₁P₀1436 57 2Note: we number the least significant bit with 1, not 0! 0 is reserved for “no errors”.On readout we compute:P₀ xor D₃ xor D₁ xor D₀ = 1 xor 0 xor 0 xor 0 = 1 = C0P₁ xor D₃ xor D₂ xor D₀ = 1 xor 0 xor 1 xor 0 = 0 = C1P₂ xor D₃ xor D₂ xor D₁ = 0 xor 0 xor 1 xor 0 = 1 = C₂CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBWhy did we choose “3” parity bits?0 Consider 4 bit words.P₂P₁P₀Observation: The C₂C₁C₀ bits need to encode the “no error” condition, plus a number for each bit (both data and parity bits)Add 3 parity bits.???1 0 1D₃D₂D₁D₀For “p” parity bits and “d” data bits:d + p + 1 <= 2pA Ci inC₂C₁C₀ exists for each Pi.CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBWhy did we arrange bits as we did?Consider 4 bit words.P₂P₁P₀Add 3 parity bits.How do we re-arrange bits?D₃D₂D₁D₀Start by numbering, 1 to 7.14 36 57 2D₃D₂D₁P₂D₀P₁P₀With this order, an odd parity means an error in 1,3,5, or 7.So, P0 is the right parity bit to use:C₂C₁C₀D₃D₂D₁P₂D₀P₁P₀An odd parity means a mistake must be in 2, 3, 6, or 7 -- the four numbers possible if C1 = 1!D₃D₂D₁P₂D₀P₁P₀Etc ... each bit narrows down the suspect bits, until it is certain.D₃D₂D₁P₂D₀P₁P₀A Ci inC₂C₁C₀ exists for each Pi.CS 152 L16: Error Correcting Codes UC Regents Fall 2006 © UCBConsider 4 bit words.P₂P₁P₀Add 3 parity bits.P₀ = D₃ xor D₁ xor D₀ P₁ = D₃ xor D₂ xor D₀ P₂ = D₃ xor D₂ xor D₁D₃D₂D₁D₀It takes 3 bit flips to move from one legal number to another (for all 16 numbers)If only one bit flips, we can always figure out the
View Full Document
Unlocking...