Efficient Fault Tree Analysis of Complex Fault Tolerant Multiple-Phased Systems

作     者：莫毓昌 刘宏伟 杨孝宗 

作者机构：Department of Computer Science and TechnologyHarbin Institute of Technology 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2007年第12卷第S1期

页      面：122-127页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：the National Natural Science Foundation of China (No. 60503015) 

主　　题：fault tolerant system reliability analysis fault tree analysis multiple-phased system variable or-dering heuristic 

摘      要：Fault tolerant multiple phased systems (FTMPS), i.e., systems whose critical components are independently replicated and whose operational life can be partitioned in a set of disjoint periods, are called phases . Because of their deployment in critical applications, their reliability analysis is a task of primary relevance to validate the designs. Fault tree analysis based on binary decision diagram (BDD) is one of the most commonly used techniques for FTMPS reliability analysis. To utilize the technique the fault tree structure of FTMPS needs to be converted into the corresponding BDD format. Our research work shows that the system BDD generation algorithms presented in the literature are too inefficient to be used for industrial complex FTPMS because of the problems, such as variable ordering and combination of large BDDs. This paper presents a more efficient approach consisting of a flatting pre-processing technique, a proved efficient ordering heuristic and a bottom-up generation algorithm. The approach tries to combine share-variable BDDs by complex combination operation firstly and then combine no-share-variable BDDs using simple combination operation, thus to alvoid the intensive computations caused by large BDD combination operations. An example FTMPS is analyzed to illustrate the advantages of our approach.