Remembrance of things past: locality and memory in BDDs

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: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 2: Pranav Ashar , Matthew Cheong, Efficient breadth-first manipulation of binary decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.622-627, November 06-10, 1994, San Jose, California, United States
• 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.
• 4: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 5: Masahiro Fujita , Yusuke Matsunaga , Taeko Kakuda, On variable ordering of binary decision diagrams for the application of multi-level logic synthesis, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 6: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 7: D. E. Long. Robdd package, 1993.
• 8: Hiroyuki Ochi , Koichi Yasuoka , Shuzo Yajima, Breadth-first manipulation of very large binary-decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.48-55, November 07-11, 1993, Santa Clara, California, United States
• 9: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 10: Jagesh V. Sanghavi , Rajeev K. Ranjan , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, High performance BDD package by exploiting memory hierarchy, Proceedings of the 33rd annual conference on Design automation, p.635-640, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240638]
• 11: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 12: F. Somenzi. CUDD: CU Decision Diagram Package. ftp://vlsi.colorado.e du / pub/.
• 13: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

  J. Computer Applications

General Terms:
Design, Measurement, Performance, Theory