《容错计算英文版课件：lec04-stspace》由会员分享，可在线阅读，更多相关《容错计算英文版课件：lec04-stspace（18页珍藏版）》请在金锄头文库上搜索。
1、Fault-Tolerant ComputingMotivation, Background, and ToolsOct. 20061State-Space ModelingAbout This PresentationEditionReleasedRevisedRevisedFirstOct. 2006This presentation has been prepared for the graduate course ECE 257A (Fault-Tolerant Computing) by Behrooz Parhami, Professor of Electrical and Com
2、puter 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. 20062State-Space ModelingState-Space ModelingOct. 20063State-Space ModelingOct.
3、 20064State-Space ModelingWhat Is State-Space Modeling?With respect to availability of resources and computational capabilities, a system can be viewed as being in one of several possible statesState transitions:System moves from one state to another as resource availability and computational power
4、change due to various eventsState-space modeling entails quantifying transition probabilities so as to determine the probability of the system being in each state; from this, we derive reliability, availability, safety, and other desired parametersThe number of states can be large, if we want to mak
5、e fine distinctions, or it can be relatively small if we lump similar states togetherGreatLousyGoodSo-so 0.860.080.040.02Oct. 20065State-Space ModelingMarkov ChainsRepresented by a state diagram with transition probabilities Sum of all transition probabilities out of each state is 1s(t + 1) = s(t) M
6、s(t + h) = s(t) M hThe state of the system is characterized by the vector (s0, s1, s2, s3)(1, 0, 0, 0) means that the system is in state 0(0.5, 0.5, 0, 0) means that the system is in state 0 or 1 with equal probs(0.25, 0.25, 0.25, 0.25) represents complete uncertainty03120.30.50.40.10.30.40.10.2Must
7、 sum to 1Transition matrix: M =0.3 0.4 0.3 00.5 0.4 0 0.1 0 0.2 0.7 0.10.4 0 0.3 0.3Example:(s0, s1, s2, s3) = (0.5, 0.5, 0, 0) M = (0.4, 0.4, 0.15, 0.05)(s0, s1, s2, s3) = (0.4, 0.4, 0.15, 0.05) M = (0.34, 0.365, 0.225, 0.07)Markov matrix(rows sum to 1)Self loops not shownOct. 20066State-Space Mode
8、lingMerging States in a Markov Modell m011110101All solid lines lDashed lines m1110101000000013l3 m2l2 ml1 m0Failed state if TMRSimpler equivalent model for 3-unit fail-soft systemWhether or not states are merged depends on the models semanticsThere are three identical units1 = Unit is up0 = Unit is
9、 downOct. 20067State-Space ModelingTwo-State Nonrepairable SystemsReliability as a function of time:R(t) = p1(t) = eltRate of change for the probability of being in state 1 is lp1 = lp1p1 + p0 = 110lThe label l on this transition means that over time dt, the transition will occur with probability ld
10、t (we are dealing with a continuous-time Markov model)p0 = 1 eltp1 = elt1TimeInitial condition: p1(0) = 1Oct. 20068State-Space Modelingk-out-of-n Nonrepairable Systemsnn 1 nln 2 (n1)lk k 1 kl0 pn = nlpnpn1 = nlpn (n 1)lpn1 .pk = (k + 1)lpk+1 klpkpn + pn1 + . . . + pk + pF = 1Fpn = enltp1 = ne(n1)lt(
11、1 elt).pk = ( )e(nk)lt(1 elt)kpF = 1 Sj=k to n pjnkInitial condition: pn(0) = 1In this case, we do not need to resort to more general method of solving linear differential equations (LaPlace transform, to be introduced later)The first equation is solvable directly, and each additional equation intro
12、duces only one new variableOct. 20069State-Space ModelingTwo-State Repairable SystemsAvailability as a function of time:A(t) = p1(t) = m/(l + m) + l/(l + m) e(l+m)tDerived in the next slideIn steady state (equilibrium), transitions into/out-of each state must “balance out” lp1 + mp0 = 0p1 + p0 = 110
13、lmThe label m on this transition means that over time dt, repair will occur with probability mdt (constant repair rate as well as constant failure rate)p1 = m/(l + m)p0 = l/(l + m)1Steady-state availabilityTimeOct. 200610State-Space ModelingSolving the State Differential Equations10lmTo solve linear
14、 differential equations with constant coefficients:1. Convert to algebraic equations using LaPlace transform2. Solve the algebraic equations3. Use inverse LaPlace transform to find original solutionsp1(t) = lp1(t) + mp0(t) p0(t) = mp0(t) + lp1(t)sP1(s) p1(0) = lP1(s) + mP0(s) sP0(s) p0(0) = mP0(s) +
15、 lP1(s)P1(s) = (s + m) / s2 + (l + m)sP0(s) = l / s2 + (l + m)s10p1(t) = m/(l + m) + l/(l + m) e(l+m)tp0(t) = l/(l + m) l/(l + m) e(l+m)tLaPlace Transform Tableh(t) H(s)kk/seat 1/(s + a)tn1eat/(n 1)!1/(s + a)nk h(t) k H(s)h(t) + g(t) H(s) + G(s)h(t) s H(s) h(0)Oct. 200611State-Space ModelingSystems
16、with Multiple Failure StatesSafety evaluation:Total risk of system is Sfailure states cj pjIn steady state (equilibrium), transitions into/out-of each state must “balance out”lp2 + mp1 + mp0 = 0mp1 + l1p2 = 0p2 + p1 + p0 = 1p2 = m/(l + m)p1 = l1/(l + m)p0 = l0/(l + m)Failure state j has a cost (pena
17、lty) cj associated with it l1m201l0 ml1 + l0 = l1Timep2(t)p1(t)p0(t)Oct. 200612State-Space ModelingSystems with Multiple Operational StatesPerformability evaluation:Performability = Soperational states bj pjl2p2 + m2p1 = 0l1p1 m1p0 = 0p2 + p1 + p0 = 1p2 = dp1 = dl2/m2p0 = dl1l2/(m1m2)Operational sta
18、te j has a benefit bj associated with it l2m1201l1 m2Let d = 1/1 + l2/m2 + l1l2/(m1m2)Example: l2 = 2l, l1 = l, m1 = m2 = m (single repairperson or facility), b2 = 2, b1 = 1, b0 = 0P = 2p2 + p1 = 2d + 2dl/m = 2(1 + l/m)/(1 +2 l/m + 2l2/m2)Oct. 200613State-Space ModelingTMR System with RepairMean tim
19、e to failure evaluation:See Siew92, pp. 335-336, for derivationMTTF = 5/(6l) + m/(6l2) = 5/(6l)(1 + 0.2m/l)3lp3 + mp2 = 0(m + 2l)p2 + 3lp3 = 0p3 + p2 + pF = 1Assume the voter is perfect Upon first module malfunction, we switch to duplex operation with comparison3l3F22l mSteady-state analysis of no u
20、sep3 = p2 = 0, pF = 1MTTF Comparisons (l = 106/hr, m = 0.1/hr)Nonredundant1/l1 M hrTMR5/(6l) 0.833 M hrTMR with repair5/(6l)(1 + 0.2m/l)16,668 M hrMTTF for TMRImprovementdue to repairImprovement factorOct. 200614State-Space ModelingFail-Soft System with Imperfect Coveragel2p2 + m2p1 = 0l2(1 c)p2 + l
21、1p1 m1p0 = 0p2 + p1 + p0 = 1p2 = qp1 = 2rqp0 = 2r(1 c + r)qIf malfunction of one unit goesundetected, the system failsl2cm1201l1 m2We solve this in the special case of l2 = 2l, l1 = l, m2 = m1 = m Let r = l/m and q = 1 / (1 + 4r 2cr + 2r2)We can also consider coverage for the repair directionl2(1 c)
22、Oct. 200615State-Space ModelingBirth-and-Death ProcessesSpecial case of Markov model with states appearing in a chain and transitions allowed only between adjacent statesThis model is used in queuing theory, where the customers arrival rate and providers service rate determine the queue size and wai
23、ting timeClosed-form expression for state probabilities can be found, assuming n + 1 states and s service providers (repair persons): M/M/s/n/n queuepj = (n j + 1) (l/m) pj1 / j for j = 1, 2, . . . , rpj = (n j + 1) (l/m) pj1 / r for j = r + 1, r + 2, . . . , n4lm013l m2l3lm242m2m3mm2m3m4mEquation f
24、or p0Siew92, p. 347Oct. 200616State-Space ModelingThe Dependability Modeling ProcessChoose modeling approach Combinational State-spaceSolve model Derive model parametersInterpret resultsValidate model and resultsConstruct modelIterate until results are satisfactoryOct. 200617State-Space ModelingSoft
25、ware Aids for Reliability ModelingRelex (company specializing in reliability engineering) Reliability block diagram: http:/ Markov: http:/ Iowa State University HIMAP: University of Virginia Galileo: http:/www.cs.virginia.edu/ftree/2003-redesign/pages/Software/index.html See Appendix D, pp. 504-518, of Shoo02 for more programsDept. of Mechanical Engineering, Univ. of Maryland: List of reliability engineering tools: http:/www.enre.umd.edu/tools.htm Oct. 200618State-Space Modeling
