Question of multithread usage of JDD

[Vinson Liu]

Dear developer, I am a student working on a projects which is very demanding on performance, using this JDD library. I would like to run multithreads to compute BDDs using the BDD class in JDD, but I found that the BDDs(the integer identifiers actually) generated by different BDD instances could't do boolean operations with each other, while multiple threads accessing the single same BDD instance will cause synchronization problems (adding synchronized lock makes performance no better than using single thread). So I wonder if you can give me some pointers on computing BDDs with multithreads so that I can gain benefits from parallelism? Many Thanks.

[Arash Vahidi (private)]

A BDD context in JDD (or any other library I know of) is not thread-safe by design. You can use different contexts for each thread but as you pointed out that will give you BDDs with conflicting internal labeling (i.e. they belong to different node-tables) and as such cannot participate in operations.

In theory, you could move BDDs between context (JDD does not implement this although it should be fairly trivial) but that might not not gain you much in performance.

I am not aware of any working parallel BDD libraries, but a quick search came up with some interesting publications:

• B. Yang, Y.-A. Chen, R. Bryant, and D. O'Hallaron. Space- and Time-Efficient BDD Construction via Working Set Control. In Proc. of Asia andSouth Pacific Design Automation Conference (ASPDAC '98), pages 423-432.Yokohama, Japan. February, 1998.
• B. Yang and D.R. O'Hallaron. Parallel breadth-first BDDconstruction. In Ninth ACM SIGPLAN Symposium on Principles and Practiceof Parallel Programming, pages 145-156, June 1997.
• Kimura, Shinji & M. Clarke, Edmund. (1990). A parallel algorithm for constructing binary decision diagrams. Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors. 220 - 223. 10.1109/ICCD.1990.130209.
• Yuxiong He, Multicore-enabling a Binary Decision Diagram algorithm
• N. Velev, Miroslav & Gao, Ping. (2014). Efficient parallel GPU algorithms for BDD manipulation. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC. 750-755. 10.1109/ASPDAC.2014.6742980.