Article

Free access

Remembrance of things past: locality and memory in BDDs

Authors:

Srilatha Manne,

Dirk Grunwald,

Fabio SomenziAuthors Info & Claims

DAC '97: Proceedings of the 34th annual Design Automation Conference

Pages 196 - 201

https://doi.org/10.1145/266021.266065

Published: 13 June 1997 Publication History

PDF eReader

Abstract

Binary Decision Diagrams (BDDs) are efficient at manipulating large sets in a compact manner. BDDs, however, are inefficient at utilizing the memory hierarchy ofthe computer. Recent work addresses this problem by manipulating the BDDsin breath-first manner (BFS). BFS processing is quite successful at reducing the number of page faults when the BDDs do not fit in the available physical memory. When pagingdoes not take place, it is much less clear which paradigmleads to the better performance. In this paper, we perform adetailed analysis of BFS and DFS packages using simulationand direct performance monitoring ofthe memory hierarchy.We show that there is very little difference in TLB and cachemiss rates for DFS and BFS paradigms. We also show thatdifferences in execution time between carefully tuned BFSand DFS implementations are primarily a function of thelossless computed table used in BFS implementations, andnot a function of memory locality. Furthermore, we presentimplementation changes to the the Cudd package that canimprove execution times by asmuch as 26% when the problem fits in main memory, and a factor of six when paging is involved.

References

[1]

A. Agarwal, J. Hennessy, and M. Horowitz. Cache performance of operating system and multiprocessing workloads. A CM Transactions on Computer Systems, 6(4):393-431, November 1988.

Digital Library

Google Scholar

[2]

P. Ashar and M. Cheong. Efficient breadth-first manipulation of binary decision diagrams. In Proceedings of the International Conference on Computer-Aided Design, pages 622-627, San Jose, CA, November 1994.

Digital Library

Google Scholar

[3]

R. K. Brayton et al. VIS: A system for verification and synthesis. Technical Report UCB/ERL M95/104, Electronics Research Lab, Univ. of California, December 1995.

Google Scholar

[4]

R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, C-35(8):677-691, August 1986.

Digital Library

Google Scholar

[5]

M. Fujita, Y. Matsunaga, and T. Kakuda. On variable ordering of binary decision diagrams for the application of multi-level logic synthesis. In Proceedings of the European Conference on Design Automation, pages 50-54, Amsterdam, February 1991.

Digital Library

Google Scholar

[6]

J. H. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, second edition, 1996.

Digital Library

Google Scholar

[7]

D. E. Long. Robdd package, 1993.

Google Scholar

[8]

H. Ochi, K. Yasuoka, and S. Yajima. Breadth-first manipulation of very large binary-decision diagrams. In Proceedings of the International Conference on Computer-Aided Design, pages 48- 55, Santa Clara, CA, November 1993.

Digital Library

Google Scholar

[9]

R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In Proceedings of the International Conference on Computer-Aided Design, pages 42-47, Santa Clara, CA, November 1993.

Digital Library

Google Scholar

[10]

J. V. Sanghavi, R. K. Ranjan, R. K. Brayton, and A. Sangiovanni-Vincentelli. High performance BDD package based on exploiting memory hierarchy. In Proceedings of the Design Automation Conference, Las Vegas, NV, June 1996. To appear.

Digital Library

Google Scholar

[11]

A. J. Smith. Cache memories. A CM Computing Surveys, 14(3):473-530, September 1982.

Digital Library

Google Scholar

[12]

F. Somenzi. CUDD: CU Decision Diagram Package. ftp://vlsi.colorado.e du / pub/.

Google Scholar

[13]

A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. In Proceedings of the A CM SIGPLAN '9~ Conference on Programming Language Design and Implementation. ACM, 1994.

Digital Library

Google Scholar

Cited By

View all

Sentovich E(2005)A brief study of BDD package performanceFormal Methods in Computer-Aided Design10.1007/BFb0031823(389-403)Online publication date: 25-Jun-2005
https://doi.org/10.1007/BFb0031823
Seidl MZorn B(2001)Implementing heap-object behavior prediction efficiently and effectivelySoftware—Practice & Experience10.1002/spe.37531:9(869-892)Online publication date: 25-Jul-2001
https://dl.acm.org/doi/10.1002/spe.375
Hu A(1997)Formal hardware verification with BDDs: an introduction1997 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, PACRIM. 10 Years Networking the Pacific Rim, 1987-199710.1109/PACRIM.1997.620351(677-682)Online publication date: 1997
https://doi.org/10.1109/PACRIM.1997.620351

Index Terms

Remembrance of things past: locality and memory in BDDs

Recommendations

Value‐aware cache replacement in edge networks for Internet of Things
Abstract
With the development of Internet of Things (IoT), massive amounts of data will be brought. By offloading caching from the cloud to the edge, edge caching technology represents a promising solution in the era of IoT to meet the delay requirements ...

We develop a new model of the network edge caching system that explores the impact of the user request behavior, file popularity, and file size on the edge caching system and user request latency. We propose a network edge cache decision strategy based on ...
The future is in the past: designing for exploratory search
IIIX '12: Proceedings of the 4th Information Interaction in Context Symposium

Exploratory search activities tend to span multiple sessions and involve finding, analyzing and evaluating information found through many queries. Typical search systems, on the other hand, are designed to support single query, precision-oriented search ...
Design and Optimization of Large Size and Low Overhead Off-Chip Caches

Large off-chip L3 caches can significantly improve the performance of memory-intensive applications. However, conventional L3 SRAM caches are facing two issues as those applications require increasingly large caches. First, an SRAM cache has a limited ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '97: Proceedings of the 34th annual Design Automation Conference

June 1997

788 pages

ISBN:0897919203

DOI:10.1145/266021

Chairmen:
Ellen J. Yoffa
IBM T. J. Watson Research Center, Yorktown Heights, NY
,
Giovanni De Micheli
Stanford Univ., Stanford, CA
,
Jan M. Rabaey
Univ. of California, Berkeley

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC97

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC97: The 34th Design Automation Conference

June 9 - 13, 1997

California, Anaheim, USA

Acceptance Rates

DAC '97 Paper Acceptance Rate 139 of 400 submissions, 35%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
39
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)5

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sentovich E(2005)A brief study of BDD package performanceFormal Methods in Computer-Aided Design10.1007/BFb0031823(389-403)Online publication date: 25-Jun-2005
https://doi.org/10.1007/BFb0031823
Seidl MZorn B(2001)Implementing heap-object behavior prediction efficiently and effectivelySoftware—Practice & Experience10.1002/spe.37531:9(869-892)Online publication date: 25-Jul-2001
https://dl.acm.org/doi/10.1002/spe.375
Hu A(1997)Formal hardware verification with BDDs: an introduction1997 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, PACRIM. 10 Years Networking the Pacific Rim, 1987-199710.1109/PACRIM.1997.620351(677-682)Online publication date: 1997
https://doi.org/10.1109/PACRIM.1997.620351

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Value‐aware cache replacement in edge networks for Internet of Things

The future is in the past: designing for exploratory search

Design and Optimization of Large Size and Low Overhead Off-Chip Caches