Dassault Aviation have developed a reliability workbench based on the high-level formal description language AltaRica. The workbench includes a compiler of AltaRica models into fault trees. The fault trees generated for the largest industrial systems involve up to a thousand basic events and several dozen thousand gates; moreover, they are non-coherent. The assessment of such large formulae is challenging, even for binary decision diagrams, the state-of-the-art data structure to encode and to manipulate Boolean functions. This article describes the various heuristics and strategies that were used to make the assessment tractable.
VeselyW. E.GoldbergF. F.RobertN. H.HaaslD. F.Fault tree handbook. Technical Report NUREG 0492, 1981, US Nuclear Regulatory Commission.
2.
ArnoldA.GriffaultA.PointG.RauzyA.The altarica language and its semanticsFundamenta Informaticae, 2000, 34, 109–124.
3.
RauzyA.Mode automata and their compilation into fault treesReliability Engng Syst. Safety, 2002, 78 (1), 1–12.
4.
BryantR.Graph based algorithms for Boolean function manipulationIEEE Trans. Comput., 1986, 35 (8), 677–691.
5.
BraceK.RudellR.BryantR.Efficient implementation of a BDD package. In Proceedings of the 27th ACM/IEEE Design Automation Conference, 1990, IEEE 0738, pp. 40–45.
6.
CoudertO.MadreJ.-C.Fault tree analysis: 1020 prime implicants and beyond. In Proceedings of the Annual Reliability and Maintainability Symposium, ARMS'93, Atlanta, North Carolina, January 1993.
7.
RauzyA.New algorithms for fault trees analysisReliability Engng Syst. Safety, 1993, 59 (2), 203–211.
8.
FriedmanS. J.SupowitK. J.Finding the optimal variable ordering for binary decision diagramsIEEE Trans. Comput., 1990, 39 (5), 710–713.
9.
BolligB.WegenerI.Improving the variable ordering of OBDDs is NP-completeIEEE Trans. Software Engng, 1996, 45 (9), 993–1001.
10.
AloulF. A.MarkovI. L.SakallahK. A.FORCE: a fast and easy-to-implement variable-ordering heuristic. In Proceedings of the 13th ACM Great Lakes Symposium onVLSI, GLVLSI'03, Washington, DC, 2003.
11.
FujitaM.FujisawaH.KawatoN.Evaluation and improvements of Boolean comparison method based on binary decision diagrams. In Proceedings of IEEE International Conference onComputer Aided Design, ICCAD'88, 1988, pp. 2–5.
12.
ReayK. A.AndrewsJ. D.A fault tree analysis strategy using binary decision diagramsReliability Engng Syst. Safety, 2002, 78 (1), 45–56.
RauzyA.Mathematical foundation of minimal cutsetsIEEE Trans. Reliability, 2001, 50 (4), 389–396.
15.
BoiteauM.DutuitY.RauzyA.SignoretJ.-P.The AltaRica data-flow language in use: assessment of production availability of a multistates systemReliability Engng Syst. Safety, 2006, 91, 747–755.
16.
BieberP.BougnolCh.CastelCh.HeckmannJ. P.KehrenCh.MetgeS.SeguinCh.Safety assessment with altarica - lessons learnt based on two aircraft system studies. In 18th IFIP World Computer Congress, Topical Day onNew Methods for Avionics Certification, Toulouse, France, 26–26 August 2004 (IFIP).
17.
MaraninchiF.RémondY.Mode-automata: about modes and states for reactive systems In European Symposium On Programming, Lisbon, Portugal, March 1998 (Springer Verlag, Heidelberg).
RauzyA.ChâteletE.DutuitY.BérenguerC.A practical comparison of methods to assess sum-of-productsReliability Engng Syst. Safety, 2003, 79, 33–42.
21.
MinatoS.-I.Binary decision diagrams and applications to VLSI CAD, 1996 (Kluwer Academic Publishers).
22.
CamarinopoulosL.YlleraJ.An improved topdown algorithm combined with modularization as highly efficient method for fault tree analysisReliability Engng Syst. Safety, 1985, 11, 93–108.
23.
NiemeläI.On simplification of large fault treesReliability Engng Syst. Safety, 1994, 44, 135–138.
24.
MinatoS.IshiuraN.YajimaS.Shared binary decision diagrams with attributed edges for efficient Boolean function manipulation. In Proceedings of the 27th ACM/IEEE Design Automation Conference, DAC'90 (Ed. ClaesenL. J. M.), June 1990, pp. 52–57.
25.
RudellR.Dynamic variable ordering for ordered binary decision diagrams. In Proceedings of the IEEE International Conference onComputer Aided Design, ICCAD'93, November 1993, pp. 42–47.
26.
PandaS.SomenziF.Who are the variables in your neighborhood. In Proceedings of the IEEE International Conference onComputer Aided Design, ICCAD'95, 1995, pp. 74–77.
27.
FujiiH.OotomoG.HoriC.Interleaved based variables ordering methods for ordered binary decision diagrams. In Proceedings of the IEEE International Conference onComputer Aided Design, ICCAD'93, November 1993, pp. 38–41.
28.
BouissouM.BruyèreF.RauzyA.BDD based fault-tree processing: a comparison of variable ordering heuristics. In Proceedings of European Safety and Reliability Association Conference, ESREL'97, (Ed. Guedes SoaresC.), vol. 3, 1997, pp. 2045–2052.
29.
DucampF.PlanchonS.RauzyA.ThomasP.Handling very large event trees by means of binary decision diagrams. In Proceedings of the International Conference onProbabilistic Safety Assessment and Management, PSAM'5, (Eds KondoS.FurutaK.), 2000, pp. 1447–1452 (Universal Academy Press, Tokyo).
30.
HortonS. B.Optimal linear arrangement problem: algorithms and approximation, PhD Thesis, Georgia Institute of Technology, May, 1997.
31.
RossD. E.ButlerK. M.KapurR.MercerM. R.Fast functional evaluation of candidate OBDD variable orderings. In Proceedings of the Second ACM/IEEE European Design Automation Conference, ECAD'91, February 1991, pp. 4–10.
