Clone wiki

JDD / FAQ

JDD Frequently Asked Questions

This is a list of the JDD library Frequently Asked Questions (FAQ). It contains answers to some frequently asked questions about the JDD library.

Introduction (what is this all about?)

What is this?

This is a package for working with Binary Decision Diagrams (BDDs) and Zero-suppressed BDDs.

What is it good for?

BDDs are used to efficiently represent and manipulate functions that map a binary vector to a boolean value (i.e. f: 2^V -> {0,1}). This representation can be used to efficiently store huge sets/functions/relations in relatively small chunks of memory. It can be used in to solve large combinatorial and graph problems. There are many application from CAD to compiler optimization to Internet firewall technology.

I really like your work, can I donate some money?

go away, you are not funny!

Copyrights

Sounds good, can I use it in my project?

Yes

Can I use JDD in my commercial application?

Yes. But make sure you read the zlib license first.

Are there any patented algorithms used in JDD?

To best of knowledge, no

Performance

How fast is JDD Compared to other packages?

It is written in Java, so it is not as quiet as fast as the state-of-the-art packages. For certain problems, it is ranked in the top five [according to our benchmarks].

See also performance .

Why is JDD so slow on some benchmark problems??

JDD lacks dynamic variable re-ordering. Therefore, some benchmark problems that use a very bad initial variable ordering cannot complete in reasonable time.

What is dynamic variable re-ordering anyway??

The size of a BDD representing a boolean functions may differ drastically depending on the order in which the boolean variables are introduced in the BDD. There exists several algorithms to re-arrange the variable order on the fly to make the BDDs smaller.

Why doesn't JDD support dynamic variable re-ordering??

For some problems, given a good initial variable ordering, very very few problems benefit from dynamic variable re-ordering. In fact, as Bwolen Yang's PhD thesis showed, re-ordering often costs more than it gives back in terms of time (and space?). This is specially true for sequential problems, which is the main target of JDD. Beside, not including variable re-ordering made the JDD code less complex...

Why does JDD fail to allocate more memory even when large chunks are available?

This has to do with the heap-compacting algorithm of the Java virtual machine. JDD will however try to remedy this by compressing the memory into LZW chunks and then re-building everything.

Why is my BDD application so slow? I thought BDDs were very efficient?

There may be several reasons: bad variable ordering is the most possible. Maybe you are solving your problem in a wrong way? Maybe what you really need is a SAT-solver? Maybe the problem is intractable anyway? Check out Alan Hu's PhD thesis (Stanford) and Bwolen Po-Jen Yang's PhD thesis (CMU) for some basic guidelines on the subject.

For better performance with JDD, should I get a faster CPU, more cache or more RAM??

For model checking, get more RAM. For circuit verification get the CPU with the largest cache you can find on this planet. If you are doing many "small" bdd computations, get a faster CPU.

(this advice is very JDD specific and does not apply to BuDDy et al.)

Is the server java virtual machine is recommended to use with JDD?

The server JVM is a high performance virtual machines provided by SUN. The server JVM includes sophisticated JIT optimization, which promise performance equal or better that native C executable. It is primary used in high-end servers. You may use it by adding the -server switch to the java command line. Beware however that the complex structure of JDD makes it hard for the server JVM to analyze and generate efficient code. In general, the server JVM is slower on smaller example due to an overhead of 2-20s for JIT optimization. Consider for example the following mini-benchmark on the N queen example:

N           -client             -server
           (time in ms)       (time in ms)
-------------------------------------------
8            160                1540
9            770                6750
10           3840               7000
11           21500              23000
12  first at N=12 the server  JVM becomes more efficient

Also, the server JVM is slow the first time the code is run. For best performance, try to run multiple JDD application without invoking the "java" command more than once (start all your applications from a short java program instead of, say, a shell script).

Why is JDD so fast on the C6288 multiplier benchmark?

This is an example of a type of model where you cannot "cheat" by pre-computing a very good initial variable order and use that instead of the given variable ordering :)

Technical details

How many bytes does each BDD node occupy in JDD?

16 bytes in the node-table, in addition, about 8 bytes are required for each node in the hash-table. So the actual size is 24.

What kind of garbage collection is used in JDD?

Top-level reference counting + mark and sweep.

Does JDD use depth or breadth-first node traversal ??

Depth first (breadth first may be included in later versions)

What is the maximal number of nodes than can exists in JDD?

Theoretically, 2^31. However, since currently Java applications can at most allocate 3G bytes, and each node is about 24 bytes large, the correct number is about 80 million nodes [2^26] :( We are not sure if this differs on 64-bit architectures. If it does, then the limit is 2^31 nodes. It should be noted that the largest practical problem we have seen so far required about 10 million nodes, at worst.

A general guideline is that if you are above 3 million nodes, then you should either re-think your algorithm or use another technique than BDDs...

What is the maximal number of variables that can be used in JDD?

Again, 2^31 in theory and about 40 million in practice, which should still be enough for most people ;)

Developer stuff

How can I contribute to the JDD project?

There are several ways:

  • Join the development team and implement some fancy BDD algorithms.
  • Submit bug reports!
  • Write your own benchmark suite and send it to us
  • Find a nice way to solve some well known problem with BDDs
  • Donate us some books about algorithms and complexity ;)
  • ...

The very least thing you could do is to run the following commands and email the results to us:

java -cp jdd.jar jdd.util.jre.JRETest
java -cp jdd.jar jdd.examples.BDDQueens 8
java -cp jdd.jar jdd.examples.BDDQueens 10
java -cp jdd.jar jdd.examples.BDDQueens 12

What version of JDD am I running?

We use an increasing build number to indicate changing versions. see the jdd.Version.build field.

Features

The BDD library is extremely low-level, I need a more user-friendly API!

The core BDD library is low-level to give you complete control over each computation. We understand that programming at such a low level is error prone, you will simply have to write your own high-level wrappers.

NEW: The friendly people of the JavaBDD project have created a wrapper for JDD which allows you to use their high-level interface with JDD. Give it a try!

Complemented edges, please, please, please...

We are thinking about it... The performance results from CUDD are however not very encouraging, so we probably won't add CE BDDs to JDD.

I would like to see the algorithm "xyz" in the next version of JDD

Sure, but if it is too much work, we might send you the source code and ask you to implement it yourself :)

Common Problems (stuff that usually fill my mailbox)

How can I submit a bug?

Use the issue tracker...

I have an example of a problem on which JDD performs very poor, what should I do?

Send us the example and we will look at it. Either its a bug or a performance problem in JDD (or your problem is intractable by nature). Neither way, we will fix it till the next release.

My JDD application is very slow! In 99.99% of cases, it is your application that is trying to compute something that is really much harder than you think it is. It might also (but not very likely) be a JDK/JRE problem. Run the following commands and email us the output.

java -cp jdd.jar jdd.util.jre.JRETest
java -cp jdd.jar jdd.examples.BDDQueens 8
java -cp jdd.jar jdd.examples.BDDQueens 10

I can't get the DOT output working!

Dot is a third-party utility provided by AT&T research. Make sure you first download it and install it from http://www.research.att.com/sw/tools/graphviz/. If you still get errors like this:

java.io.IOException: CreateProcess: ...

Then probably dot is not in your path.

I want the source DOT file, but all I get is its picture...

By default, when you create a DOT file you will get a PNG-image. to get the source file instead, try this:

import jdd.util.*;
[...]
Dot.setRemoveDotFile(false);
Dot.setExecuteDot(false);
bddobject.printDot("filename.dot", somebdd);

Whats wrong with this code?

BDD bdd = new BDD();
[...]
int bdd1 = bdd.and(somevariable, anothervaribale);
in2 bdd2 = bdd.and(thirdvariable, andsoon);
int bdd3 = bdd.or( bdd1, bdd2);

This code is dead wrong!. Since you are not adding a ref-count to "bdd1", it may get garbage collected (for example, during the second "and") and then when you try the "or", "bdd1" is not a valid bdd anymore and the result of this operation is garbage. Do this instead:

int bdd1 = bdd.ref( bdd.and(somevariable, anothervaribale) );
int bdd2 = bdd.ref( bdd.and(thirdvariable, andsoon) );
int bdd3 = bdd.ref( bdd.or( bdd1, bdd2) ); // yes, this one too. you will need it later on, wont you?

bdd.deref(bdd2);
bdd.deref(bdd1);

One way to catch such problems is to use a "DebugBDD" object instead of "BDD". Beware however that it is very slow and might not catch all problems.

Whats wrong with this other code?

BDD bdd = new BDD();
[...]
int bdd1 = bdd.ref( bdd.and(somevariable, anothervaribale) );
in2 bdd2 = bdd.and(thirdvariable, andsoon);
int bdd3 = bdd.ref( bdd.or( bdd1, bdd2) );
bdd.deref(bdd3);

Nothing really. "bdd2" is not ref-counted, but nothing happens between the creation of "bdd2" and the call to "or" so "bdd2" cannot not be garbage collected. During the "or" itself, "bdd2" is protected from garbage collection by JDD.

Note however that "DebugBDD" will catch this as a possible error!.

Misc.

Can several BDD managers simultaneously exist in JDD?

Yes. In fact, it is easy to implement routines to even move BDD trees between different packages. You must now mix them, thought.

Are Z-BDDs better than BDDs?

Z-BDDs represent sparse sets more efficiently. They are probably more useful for representing things such as Petri nets and graphs.

What is the relation between JDD and BuDDy?

JDD uses the same internal structure as BuDDy. In fact, few operations are copy-pasted from the BuDDy source :)

What is the relation between JDD and CUDD? JDD and CUDD use the same hash functions, that is the only relation I can think of...

Updated