




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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 waiting 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 m2l3lm242m2m3mm2m3m4mEquat
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030中国现场护理测试(POCT)行业产业运行态势及投资规划深度研究报告
- 2025至2030中国玉米油行业发展趋势分析与未来投资战略咨询研究报告
- 家校联结科技铺路
- 智慧城市基础设施的智能化运维策略
- 智慧城市公共空间LED照明的智能化管理
- 从文化交流角度看篮球教育的国际化
- 教育游戏化设计原则与挑战共克
- 商业培训中LMS的效果评估与案例分享
- 增强教育行业的数据保护能力与技术创新研究
- 伦理引导下的教育技术创新与发展
- 金融学原理重点总结彭兴韵
- Cmk设备能力指数分析表
- J17J177 钢丝网架珍珠岩复合保温外墙板建筑构造
- 水泥检测培训试题(附答案)
- 译林版三年级英语上册《全册课件》ppt
- 高标准农田建设上图入库(技术培训)
- ma600学员座舱图册用户培训中心
- 城镇燃气场站经营企业安全生产标准化评分标准
- 液压过滤器的设计和制造
- 不动产登记实务PPT完整版
- 《义务教育英语课程标准(2022年版)》自测题、综合测试题、初中英语新课标过关抽测试卷及优秀答卷(共17套附答案)
评论
0/150
提交评论