Parallel implementation of BDD algorithms using a distributed shared memory

Yegnashankar Parasuram, Edward Stabler, Shiu Kai Chin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

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 data. 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.

Original languageEnglish (US)
Title of host publicationProceedings of the Hawaii International Conference on System Sciences
EditorsJay F. Nunamaker, Ralph H.Jr. Sprague
PublisherIEEE Computer Society
Pages16-25
Number of pages10
ISBN (Print)0818650508
StatePublished - Jan 1 1994
EventProceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5) - Wailea, HI, USA
Duration: Jan 4 1994Jan 7 1994

Publication series

NameProceedings of the Hawaii International Conference on System Sciences
Volume1
ISSN (Print)1060-3425

Other

OtherProceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5)
CityWailea, HI, USA
Period1/4/941/7/94

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel implementation of BDD algorithms using a distributed shared memory'. Together they form a unique fingerprint.

Cite this