收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址: