IEICE TRANSACTIONS on Information
On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.9 pp.2234-2242
- Publication Date
- 2014/09/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2013LOP0011
- Type of Manuscript
- Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)
- Category
- Logic Design
Authors
Shinobu NAGAYAMA
Hiroshima City University
Tsutomu SASAO
Meiji University
Jon T. BUTLER
Naval Postgraduate School
Mitchell A. THORNTON
Southern Methodist University
Theodore W. MANIKAS
Southern Methodist University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, Mitchell A. THORNTON, Theodore W. MANIKAS, "On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 9, pp. 2234-2242, September 2014, doi: 10.1587/transinf.2013LOP0011.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2013LOP0011/_p
Copy
@ARTICLE{e97-d_9_2234,
author={Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, Mitchell A. THORNTON, Theodore W. MANIKAS, },
journal={IEICE TRANSACTIONS on Information},
title={On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems},
year={2014},
volume={E97-D},
number={9},
pages={2234-2242},
abstract={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.},
keywords={},
doi={10.1587/transinf.2013LOP0011},
ISSN={1745-1361},
month={September},}
Copy
TY - JOUR
TI - On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems
T2 - IEICE TRANSACTIONS on Information
SP - 2234
EP - 2242
AU - Shinobu NAGAYAMA
AU - Tsutomu SASAO
AU - Jon T. BUTLER
AU - Mitchell A. THORNTON
AU - Theodore W. MANIKAS
PY - 2014
DO - 10.1587/transinf.2013LOP0011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2014
AB - 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.
ER -
English
