容错计算英文版课件：lec07-masking

1、Fault-Tolerant ComputingDealing with Low-Level ImpairmentsOct. 20061Fault MaskingAbout This PresentationEditionReleasedRevisedRevisedFirstOct. 2006This presentation has been prepared for the graduate course ECE 257A (Fault-Tolerant Computing) by Behrooz Parhami, Professor of Electrical and Computer

2、Engineering at University of California, Santa Barbara. The material contained herein can be used freely in classroom teaching or any other educational setting. Unauthorized uses are prohibited. Behrooz ParhamiOct. 20062Fault MaskingFault MaskingOct. 20063Fault MaskingOct. 20064Fault MaskingMultilev

3、el ModelComponentLogicServiceResultInformationSystemLegend:ToleranceEntryLast lectureTodayOct. 20065Fault MaskingHandling FaultsRepairDiscardAbortPreventRemoveExposeMaskAvoidTolerateFaultQuality AssuranceTestingDynamic RedundancyStatic Redundancy Full? Full? MonitorTest Yes Yes NoNoPerfectFixedResto

4、redUnaffectedInjuredScreenedFailed-safeDegradedFailed DetectMiss DetectMissC o m p o n e n t o r S y s t e m S t a t eReconfigureOct. 20066Fault MaskingSome Options for Fault Tolerance1. Detect and replace Dynamic redundancy (cold/hot standby) Detection via - coding, watchdog timer, self-checking -

5、duplication (pair-and-spares)2. Mask Static redundancy May revert to simplex instead of duplex Design challenges include - synchronization for voting - voting on imprecise results3. Mask, diagnose, and reconfigure Hybrid redundancy Fault masked at output, but diagnosed - e.g., via comparison with vo

6、ter output Faulty circuit is replaced by spare Becomes static upon spare exhaustionV231 VoterD21 Detector SpareVS2314Switch-voter SpareOct. 20067Fault MaskingComparing Fault Tolerance SchemesAdvantagesDrawbacksLess powerCoverage factor (cold standby)Long lifeTolerance latency (just add spares)Immedi

7、ate maskingPower/area penalty High safetyVoter critical Immediate maskingPower/area penaltyLong life andSwitch-voter critical high safety V231 VoterD21 Detector SpareVS2314Switch-voter SpareOct. 20068Fault MaskingInherent Fault Masking in Logic Circuits0 1 fault in b is critical b c a d f g eh z1000

8、0010 00 1 fault in c or d is not critical (it is masked)1 0 fault in a or h is not critical (it is masked)Even nonredundant circuits have some masking capabilityIs there a way to exploit the inherent masking capabilities of logic gates to achieve fault tolerance?Oct. 20069Fault MaskingInterwoven Red

9、undant LogicLet x1, x2, x3, and x4 be 4 copies of the signal x1 0 b c a d f g eh z1 0a1a2b1b2a1a2b1b2a3a4b3b4a3a4b3b4e1e2e3e4f1f2f3f4e1e4f1f41 0 change is critical for AND, subcritical for OR0 1 change is critical for OR, subcritical for ANDTo mask h critical faults: Number of gates multiplied by (h

10、 + 1)2 Gate inputs multiplied by h + 1For h = 1, the scheme is known as Quadded logicAlternating layers of ANDs and ORs can mask each others critical faults1111Oct. 200610Fault MaskingInterwoven Logic for NanoelectronicsHalf-adder implemented in quadded logicFrom: /iel5/54/32070/01492293.pdf IEEE D&

11、TJuly-Aug. 2005pp. 328-339 b c a s b a c sOct. 200611Fault MaskingHighly Reliable Logic with “Crummy” RelaysMoore & Shannon, 1956a: prob contact made | energizedc: prob contact made | not energized“Make” contact(normally open)a c“Break” contact(normally closed)a 0 Rm 1/2V231 VoterRRm1.00.01.00.50.00

12、.5 TMR better Simplex betterRlt00.51.0ln 20.0 TMR SimplexMTTF: TMR 5l/6 Simplex lR = 3Rm2 2Rm3 Rm? RIFTMR/Simplex = (1 Rm)/(1 R) = 1/1 Rm(2Rm 1)Oct. 200613Fault MaskingTMR with Imperfect VoterCondition on the voter reliabilityRv 1 / 3Rm 2Rm2V231 Voter TMR betterRvRm0.51.00.8850.950.750.560.94 Simple

13、x betterCondition on the module reliability3 9 8/Rv4 3 + 9 8/Rv4 Rm dRvmin/ dRm = (3 + 4Rm) / (3Rm 2Rm2)2Example: Rv = 0.95 requires that0.56 Rm Rm ? Oct. 200614Fault MaskingTMR with Compensating FaultsV231 VoterExample: Rm = 0.998, p0 = p1 = 0.001 R = 0.999,984 + 0.000,006 = 0.999,990 Basic TMR Com

14、pensationRIFTMR/Simplex = 0.002 / 0.000,016 = 125RIFCompen/TMR = 0.000,016 / 0.000,010 = 1.6Rm = 1 p0 p1 (0- and 1-fault probabilities)R = (3Rm2 2Rm3) + 6p0p1RmOct. 200615Fault MaskingImplementing a Bit-VoterTMR bit-voting: y = x1x2 x2x3 x3x1 (carry output of a single-bit full-adder)What about 5MR,

15、7MR?V231 Bit-voterx1x2x3 yOther designs are also possible Arithmetic: add the bits, compare to threshold Mux-based Selection-based (majority of bit values is their median)3-out-of-5 voter built of 2-input gatesTwo mux-based designs for a 3-out-of-5 bit-voterGate-level design quickly explodes in size

16、Oct. 200616Fault MaskingComplexity of Different Bit-Voter DesignsCost of majority bit-voters as a function of the number n of inputsOct. 200617Fault MaskingVoting at the Word LevelUsing bit-by-bit voting may be dangerousOne might think that in this example, any of the module outputs could be correct

17、, so that producing 1 0 at the output isnt all that wrongx1 = 0 0 x2 = 1 0 x3 = 1 1y = 1 0However, with bit-by-bit voting, the output may be different from all inputsx1 = 0 0 0 x2 = 1 0 1x3 = 1 1 0y = 1 0 0Design of bit- and word-voting networks discussed in:Parhami, B., “Voting Networks,” IEEE TR,

18、Aug. 1991Oct. 200618Fault MaskingSome Simple Voter DesignsIf in the case of 3-way disagreement any of the inputs can be chosen, then a simple design is possibleOne can perform pseudo voting that yields the median of 3 analog signals (Dennis, N.G., Microelectronics and Reliability, Aug. 1974)Median a

19、nd mean voting are also possible with digital signalsThis design can be readily generalized to a larger number of inputs231x1x2x3 y Compare01DisagreeOct. 200619Fault MaskingSwitch for Standby RedundancyStandby redundancy requires an n-to-1 switch to select the output of the currently active moduleTh

20、e detectors use various info to deduce fault conditions- Error coding- Reasonableness checks- Watchdog timerD21 Detector SpareD21 SparesD3D n-to-1 switchOnce a fault has been detected, the switch reconfigures the system by flagging the faulty unit and activating next spare in sequenceIf we use an n-to-2 switch and compare the two selected outputs, the configuration is known as “pair-and-spares”Oct. 200620Fault MaskingSwitch for Hybrid RedundancyHybrid redundancy with n active and s spare modules requires an (n + s)-to-n switch to select the outputs of the active modulesSelf-p