research-article

Index-Resilient Zero-Suppressed BDDs: Definition and Operations

Authors:

Anna Bernasconi,

Valentina CirianiAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 21, Issue 4

Article No.: 72, Pages 1 - 27

https://doi.org/10.1145/2905363

Published: 18 May 2016 Publication History

Abstract

Zero-Suppressed Binary Decision Diagrams (ZDDs) are widely used data structures for representing and handling combination sets and Boolean functions. In particular, ZDDs are commonly used in CAD for the synthesis and verification of integrated circuits. The purpose of this article is to design an error-resilient version of this data structure: a self-repairing ZDD. More precisely, we design a new ZDD canonical form, called index-resilient reduced ZDD, such that a faulty index can be reconstructed in time O(k), where k is the number of nodes with a corrupted index. Moreover, we propose new versions of the standard algorithms for ZDD manipulation and construction that are error resilient during their execution and produce an index-resilient ZDD as output. The experimental results validate the proposed approach.

References

[1]

S. Akers. 1978. Binary decision diagrams. IEEE Transactions on Computers 27, 6 (1978).

Digital Library

[2]

Y. Aumann and M. A. Bender. 1996. Fault tolerant data structures. In Proceedings of the 37th Annual Sympo sium on Foundations of Computer Science (FOCS). Burlington, Vermont, USA, 580--589.

Digital Library

[3]

Bernd Becker, Rolf Drechsler, and Michael Theobald. 1997. On the expressive power of OKFDDs. Formal Methods in System Design 11, 1 (1997), 5--21.

Digital Library

[4]

Anna Bernasconi and Valentina Ciriani. 2014. Zero-suppressed binary decision diagrams resilient to index faults. In Proceedings of the 8th IFIP TC1/WG 2.2 International Conference on Theoretical Computer Science (TCS 2014), Rome, Italy, September 1--3, 2014. 1--12.

[5]

Anna Bernasconi, Valentina Ciriani, and Lorenzo Lago. 2013. Error resilient OBDDs. In Proceedings of the IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Karlovy Vary, Czech Republic, 246--249.

[6]

Anna Bernasconi, Valentina Ciriani, and Lorenzo Lago. 2015. On the error resilience of ordered binary decision diagrams. Theoretical Computer Science 595 (2015), 11--33.

Digital Library

[7]

R. Bryant. 1986. Graph based algorithm for boolean function manipulation. IEEE Transactions on Computers (1986).

Digital Library

[8]

R. Drechsler. 1998. Verifying integrity of decision diagrams. In Proceedings of the 17th International Conference on Computer Safety, Reliability and Security (SAFECOMP'98). Heidelberg, Germany, 380--389.

Digital Library

[9]

R. Ebendt, G. Fey, and R. Drechsler. 2005. Advanced BDD Optimization. Springer US.

[10]

I. Finocchi, F. Grandoni, and G. Italiano. 2005. Designing reliable algorithms in unreliable memories. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Palma de Mallorca, Spain, 1--8.

Digital Library

[11]

I. Finocchi, F. Grandoni, and G. Italiano. 2007. Designing reliable algorithms in unreliable memories. Computer Science Review 1, 2 (2007), 77--87.

Digital Library

[12]

Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. 2009. Optimal resilient sorting and searching in the presence of memory faults. Theoretical Computer Science 410, 44 (2009), 4457--4470.

Digital Library

[13]

I. Finocchi and G. Italiano. 2008. Sorting and searching in faulty memories. Algorithmica (2008).

[14]

G. Italiano. 2010. Resilient algorithms and data structures. In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC 2010). Rome, Italy, 13--24.

Digital Library

[15]

B. Jacob, S. Ng, and D. Wang. 2008. Cache, DRAM, Disk. Morgan Kaufmann.

[16]

U. Kebschull and W. Rosenstiel. 1993. Efficient graph-based computation and manipulation of functional decision diagrams. In Proceedings of the 4th European Conference on Design Automation, 1993, with the European Event in ASIC Design. 278--282.

[17]

D. Knuth. 2009. The Art of Computer Programming Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional.

Digital Library

[18]

Heh-Tyan Liaw and Chen-Shang Lin. 1992. On the OBDD-representation of general boolean functions. IEEE Transactions on Computers (1992).

Digital Library

[19]

S. Minato. 1993. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the ACM/IEEE 30th Design Automation Conference (DAC). 272--277.

Digital Library

[20]

S. Minato. 2010. Data mining using binary decision diagrams. In Progress in Representation of Discrete Functions. Morgan & Claypool, Chapter 5, 97--109.

[21]

S. Minato. 2013. Techniques of BDD/ZDD: brief history and recent activity. IEICE Transactions 96-D, 7 (2013), 1419--1429.

[22]

S. Minato and I. Kimihito. 2007. Symmetric item set mining method using zero-suppressed BDDs and application to biological data. Information and Media Technologies 2, 1 (2007), 300--308.

[23]

Alan Mishchenko. 2001. An introduction to zero-suppressed binary decision diagrams. In Proceedings of the 12th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning.

[24]

José Ignacio Requeno and José Manuel Colom. 2012. Compact representation of biological sequences using set decision diagrams. In Proceedings of the 6th International Conference on Practical Applications of Computational Biology & Bioinformatics, Miguel P. Rocha, Nicholas Luscombe, Florentino Fdez-Riverola, and Juan M. Corchado Rodrguez (Eds.). Advances in Intelligent and Soft Computing, Vol. 154. Springer Berlin Heidelberg, 231--239.

[25]

T. Sasao and J. Butler. 2014. Applications of Zero-Suppressed Decision Diagrams. Morgan & Claypool. 123 pages.

[26]

D. J. Taylor. 1990. Error models for robust storage structures. In Proceedings of the 20th International Symposium on Fault-Tolerant Computing.

[27]

S. Yang. 1991. Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. User guide. Microelectronic Center.

[28]

Sungroh Yoon, Christine Nardini, Luca Benini, and Giovanni De Micheli. 2005. Discovering coherent biclusters from gene expression data using zero-suppressed binary decision diagrams. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2, 4 (Oct. 2005), 339--354.

Digital Library

Cited By

Lembachar YRusich RNeamtiu ICiardo G(2022)Bddl: A Type System for Binary Decision DiagramsTests and Proofs10.1007/978-3-031-09827-7_3(31-47)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-09827-7_3
Bernasconi ACiriani VFrontini LLiberali VTrucco GVilla T(2018)Enhancing logic synthesis of switching lattices by generalized Shannon decomposition methodsMicroprocessors & Microsystems10.1016/j.micpro.2017.12.00356:C(193-203)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.micpro.2017.12.003

Index Terms

Index-Resilient Zero-Suppressed BDDs: Definition and Operations
1. Hardware
  1. Robustness
    1. Fault tolerance
2. Networks
  1. Network properties
    1. Network reliability
      1. Error detection and error correction

Recommendations

Chain Reduction for Binary and Zero-Suppressed Decision Diagrams
Abstract
Chain reduction enables reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the other’s ability to symbolically represent Boolean functions in compact form. For any Boolean ...
Partially-shared zero-suppressed multi-terminal BDDs: concept, algorithms and applications

Multi-Terminal Binary Decision Diagrams (MTBDDs) are a well accepted technique for the state graph (SG) based quantitative analysis of large and complex systems specified by means of high-level model description techniques. However, this type of ...
The Theory of Zero-Suppressed BDDs and the Number of Knight‘s Tours

Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato [14–17] who presents applications for cube set representations, fault simulation, timing analysis and the n-queens problem. Here the structural properties of ZBDDs are worked ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 21, Issue 4

September 2016

423 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2939671

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 18 May 2016

Accepted: 01 March 2016

Revised: 01 February 2016

Received: 01 October 2015

Published in TODAES Volume 21, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

“AMANDA” Algorithmics for MAssive and Networked DAta
Italian Ministry of Education, University, and Research (MIUR)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
128
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lembachar YRusich RNeamtiu ICiardo G(2022)Bddl: A Type System for Binary Decision DiagramsTests and Proofs10.1007/978-3-031-09827-7_3(31-47)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-09827-7_3
Bernasconi ACiriani VFrontini LLiberali VTrucco GVilla T(2018)Enhancing logic synthesis of switching lattices by generalized Shannon decomposition methodsMicroprocessors & Microsystems10.1016/j.micpro.2017.12.00356:C(193-203)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.micpro.2017.12.003

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents