Parallel implementation of BDD algorithms using a distributed shared memory
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 16-25
- https://doi.org/10.1109/hicss.1994.323189
Abstract
Binary Decision Diagrams (BDDs) are used extensively in VLSI CAD for verification, synthesis, logic minimization and testing. Parallel algorithms for Boolean Function Manipulation using BDDs have been proposed and implemented on a Connection Machine (CM-5). Abstractions have been developed to support the design of these algorithms using the message passing model of parallel programming. A Distributed Shared Memory (DSM) has been built for sharing date. Fine grained load balancing is achieved using a Distributed Stack. Experimental results are shown for the DSM and the BDD algorithms. These results demonstrate the feasibility of using parallel computing for irregular and memory intensive CAD applications such as the BDD algorithms. Improvements to the current implementation are identified for future work.Keywords
This publication has 18 references indexed in Scilit:
- Active Messages: A Mechanism for Integrated Communication and ComputationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Logic verification using binary decision diagrams in a logic synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Performance evaluation of the CM-5 interconnection networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Shared binary decision diagram with attributed edges for efficient Boolean function manipulationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An implementation of distributed shared memorySoftware: Practice and Experience, 1991
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Logic Minimization Algorithms for VLSI SynthesisPublished by Springer Nature ,1984
- Binary Decision DiagramsIEEE Transactions on Computers, 1978
- Representation of Switching Circuits by Binary-Decision ProgramsBell System Technical Journal, 1959