An ordering heuristic for building binary decision diagrams from fault-trees
52
Citation
7
Reference
10
Related Paper
Citation Trend
Abstract:
Binary decision diagrams (BDD) have made a noticeable entry in the RAMS field. This kind of representation for Boolean functions makes possible the assessment of complex fault-trees, both qualitatively (minimal cutsets search) and quantitatively (exact calculation top event probability). Any Boolean function, and in particular any fault-tree, whether coherent or not, can be represented by a BDD. The BDD is a canonical representation of the function, as soon as one has chosen a variable (i.e., in the fault-tree case, basic event) ordering. Tools based on the use of BDDs, like METAPRIME, or ARALIA, can in some cases give more accurate results than conventional tools, while running 1000 times faster. EDF has investigated this kind of technology, and tested METAPRIME, ARALIA, and other tools based on BDDs, in the framework of cooperations with the BULL company and with the Bordeaux University. These tests have demonstrated that the size of the BDD, that has to be built thoroughly before any kind of assessment can begin, is dramatically sensitive to the ordering chosen for the variables. For a given fault-tree, this size may vary by several orders of magnitude. This can lead to excessive needs, both in terms of memory and CPU time. The problem of finding an optimal ordering being untractable for real applications, many heuristics have been proposed, in order to find acceptable orderings, at low cost (in terms of computing requirements).Keywords:
Binary decision diagram
Heuristics
Representation
Function representation
In binary decision diagram–based fault tree analysis, the size of binary decision diagram encoding fault trees heavily depends on the chosen ordering. Heuristics are often used to obtain good orderings. The most important heuristics are depth‐first leftmost (DFLM) and its variants weighting DFLM (WDFLM) and repeated‐event‐priority DFLM (RDFLM). Although having been used widely, their performance is still only vaguely understood, and not much formal work has been done. This article firstly identifies some basic requirements for a reliable benchmark and gives a benchmark generation method. Then, using the generated benchmark, the performance of DFLM and its variants is studied. Both the experimental results and some interesting findings for our research questions are proposed. This article also presents a new weighting DFLM (NWDFLM) heuristic and the underlying basic ideas and gives both the experimental results and conclusions on the performance comparison. As a final synthesis of all previous results, a practical suggestion of the order of heuristic selection to process a large fault tree is NWDFLM < WDFLM < RDFLM. Copyright © 2012 John Wiley & Sons, Ltd.
Benchmark (surveying)
Heuristics
Binary decision diagram
Cite
Citations (18)
Binary decision diagram
Binary Independence Model
Boolean algebra
Cite
Citations (1)
Binary decision diagram
Representation
Chain (unit)
Function representation
Cite
Citations (14)
Symbolic simulation via ordered binary decision diagrams (OBDDs) is becoming more feasible each year. These representations are often very efficient under an appropriate ordering of the variables of the functions represented. Recently, heuristics for ordering variables have been developed, but due to the nature of heuristics, no single heuristic always produces an appropriate ordering. The authors develop and analyze a technique for selecting the best of several candidate orderings. The ordering selection method is fast. Its ranking of an ordering is compared to the actual performance of an ordering during functionals (OBDD) calculations in circuits from the ISCAS85 combinational benchmarks. Compared to any previously published single ordering heuristic, the method allows OBDD calculations using less cumulative memory over all six circuits investigated, and also produces over an order of magnitude improvement for one or more of these circuits, over every single heuristic examined. >
Heuristics
Binary decision diagram
Cite
Citations (27)
We present a new technique for defining, analysing, and simplifying digital functions, through hand-calculations, easily demonstrable therefore in the classrooms. It can be extended to represent discrete systems beyond the Boolean logic. The method is graphical in nature and provides complete ‘‘implementation-free” description of the logical functions, similar to binary decision diagrams (BDDs) and Karnaugh-maps (K-maps). Transforming a function into the proposed representations (also the inverse) is a very intuitive process, easy enough that a person can hand-calculate these transformations. The algorithmic nature allows for its computing-based implementations. Because the proposed technique effectively transforms a function into a scatter plot, it is possible to represent multiple functions simultaneously. Usability of the method, therefore, is constrained neither by the number of inputs of the function nor by its outputs in theory. This, being a new paradigm, offers a lot of scope for further research. Here, we put forward a few of the strategies invented so far for using the proposed representation for simplifying the logic functions. Finally, we present extensions of the method: one that extends its applicability to multivalued discrete systems beyond Boolean functions and the other that represents the variants in terms of the coordinate system in use.
Binary decision diagram
Truth table
Representation
Function representation
Scope (computer science)
Combinational logic
Cite
Citations (1)
Binary decision diagram
Heuristics
Representation
Cite
Citations (2)
Chain reduction enables reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the others' ability to symbolically represent Boolean functions in compact form. For any Boolean function, its chain-reduced ZDD (CZDD) representation will be no larger than its ZDD representation, and at most twice the size of its BDD representation. The chain-reduced BDD (CBDD) of a function will be no larger than its BDD representation, and at most three times the size of its CZDD representation. Extensions to the standard algorithms for operating on BDDs and ZDDs enable them to operate on the chain-reduced versions. Experimental evaluations on representative benchmarks for encoding word lists, solving combinatorial problems, and operating on digital circuits indicate that chain reduction can provide significant benefits in terms of both memory and execution time.
Binary decision diagram
Representation
Chain (unit)
Function representation
Cite
Citations (0)
Binary decision diagram
Representation
Chain (unit)
Function representation
Cite
Citations (4)
Binary decision diagrams (BDD) have made a noticeable entry in the RAMS field. This kind of representation for Boolean functions makes possible the assessment of complex fault-trees, both qualitatively (minimal cutsets search) and quantitatively (exact calculation top event probability). Any Boolean function, and in particular any fault-tree, whether coherent or not, can be represented by a BDD. The BDD is a canonical representation of the function, as soon as one has chosen a variable (i.e., in the fault-tree case, basic event) ordering. Tools based on the use of BDDs, like METAPRIME, or ARALIA, can in some cases give more accurate results than conventional tools, while running 1000 times faster. EDF has investigated this kind of technology, and tested METAPRIME, ARALIA, and other tools based on BDDs, in the framework of cooperations with the BULL company and with the Bordeaux University. These tests have demonstrated that the size of the BDD, that has to be built thoroughly before any kind of assessment can begin, is dramatically sensitive to the ordering chosen for the variables. For a given fault-tree, this size may vary by several orders of magnitude. This can lead to excessive needs, both in terms of memory and CPU time. The problem of finding an optimal ordering being untractable for real applications, many heuristics have been proposed, in order to find acceptable orderings, at low cost (in terms of computing requirements).
Binary decision diagram
Heuristics
Representation
Function representation
Cite
Citations (52)