Indexed by:
Abstract:
As a data structure used for representing and manipulating Boolean functions, BDDs (Binary Decision Diagrams) are commonly used in many fields such as model checking, system verification and so on. At the worst case, the space usage can reach exponential level; so many researchers have made a great deal of technical work on designing and implementing efficient BDD packages. Up to today, many efficient BDD packages have been implemented. For saving space and improving manipulating speed, all these packages limit the number of variables to 216. However, such a limitation also limits its applicability. In this paper, an efficient BDD package is proposed to break the limit of 216. This package not only adopts the technologies used in classical BDD package implementation but also introduce some new techniques, such as sub-allocation of memory and lightweight garbage collection. Because of such effective scheme, the number of variables which BDD package can deal with reaches 232. Compared with other BDD packages with variable number 216, this BDD package can be more extensively used. Experiments show that its performance is nearly as the same as that of the best publicly available BDD package CUDD.
Keyword:
Reprint Author's Address:
Email:
Source :
Chinese Journal of Computers
ISSN: 0254-4164
Year: 2014
Issue: 9
Volume: 37
Page: 2021-2026
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 9
Affiliated Colleges: