Thumbnail
Access Restriction
Subscribed

Author Minato, S. ♦ Ishihara, S.
Sponsorship EDAA
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Technology ♦ Engineering & allied operations ♦ Applied physics
Subject Keyword Binary decision diagrams ♦ Large-scale systems ♦ Packaging ♦ Boolean functions ♦ Data structures ♦ Acceleration ♦ Hard disks ♦ Logic ♦ Technological innovation ♦ Laboratories
Abstract We propose a new BDD manipulation method that never causes memory overflow or swap out. In our method, BDD data are accessed through the I/O stream ports. We can read unlimited length of BDD data streams using a limited size of the memory, and the result of BDD data streams are concurrently produced. Our streaming method features (1) a continuous trade-off between the memory usage and the streaming data length, (2) a valid partial result can be obtained before completing process, and (3) easily accelerated by pipelined multiprocessing. Experimental result shows that our new method is especially useful for the cases where conventional BDD packages are ineffective. For example, we succeeded in finding a number of solutions to a SAT problem using a commodity PC with a 64 MB memory, where the conventional method will require a 100 GB memory to compute it. BDD manipulation has been considered as an intensively memory-consuming procedure, but now we can also utilize the hard disk and network resources as well. Our method will lead a new style of BDD applications.
Description Author affiliation: NTT Network Innovation Labs., Yokosuka, Japan (Minato, S.)
ISBN 0769509932
ISSN 15301591
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-03-13
Publisher Place Germany
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 579.56 kB
Page Count 6
Starting Page 702
Ending Page 707


Source: IEEE Xplore Digital Library