On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems

スポンサーリンク

概要

• 論文の詳細を見る

• In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times.

• The Institute of Electronics, Information and Communication Engineersの論文

著者

• Butler Jon

  Department Of Electrical And Computer Engineering Naval Postgraduate School

• Sasao Tsutomu

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

• Nagayama Shinobu

  Department Of Computer And Network Engineering Hiroshima City University

• THORNTON Mitchell

  Department of Computer Science and Engineering, Southern Methodist University

• MANIKAS Theodore

  Department of Computer Science and Engineering, Southern Methodist University

関連論文

• Compact Numerical Function Generators Based on Quadratic Approximation : Architecture and Synthesis Method(Circuit Synthesis,VLSI Design and CAD Algorithms)
• Bi-Partition of Shared Binary Decision Diagrams(Special Section on VLSI Design and CAD Algorithms)
• Time-Division Multiplexing Realizations of Multiple-Output Functions Based on Shared Multi-Terminal Multiple-Valued Decision Diagrams (Special Issue on Multiple-Valued Logic and Its Applications)
• Design Method for Numerical Function Generators Using Recursive Segmentation and EVBDDs(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
• Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs(Logic Synthesis, VLSI Design and CAD Algorithms)
• A New Equivalence Relation of Logic Functions and Its Application in the Design of AND-OR-EXOR Networks(Discrete Mathematics and Its Applications)
• BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
• A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
• Efficient Computation of Canonical Form under Variable Permutation and Negation for Boolean Matching in Large Libraries(Logic Synthesis,VLSI Design and CAD Algorithms)
• A Parallel Branching Program Machine for Sequential Circuits : Implementation and Evaluation
• A Realization of Multiple-Output Functions by a Look-Up Table Ring(Logic Synthesis)(VLSI Design and CAD Algorithms)
• Design Methods of Radix Converters Using Arithmetic Decompositions(Computer Components)
• Area-Time Complexities of Multi-Valued Decision Diagrams(Discrete Mathematics and Its Applications)
• Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions (Special Section on VLSI Design and CAD Algorithms)
• Compact Representations of Logic Functions Using Heterogeneous MDDs(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
• A PC-Based Logic Simulator Using a Look-Up Table Cascade Emulator(Simulation and Verification,VLSI Design and CAD Algorithms)
• A Design Algorithm for Sequential Circuits Using LUT Rings(Logic Synthesis, VLSI Design and CAD Algorithms)
• Fast Boolean Matching under Permutation by Efficient Computation of Canonical Form(Logic Synthesis)(VLSI Design and CAD Algorithms)
• Output Phase Optimization for AND-OR-EXOR PLAs with Decoders and Its Application to Design of Adders(Digital Circuits and Computer Arithmetic, Recent Advances in Circuits and Systems-Part 1)
• A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton
• A Virus Scanning Engine Using an MPU and an IGU Based on Row-Shift Decomposition
• On the Numbers of Products in Prefix SOPs for Interval Functions
• On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems

もっと見る 閉じる

スポンサーリンク