Who are the variables in your neighborhood

ABSTRACT

Dynamic reordering techniques have had considerable success in reducing the impact of the initial variable order on the size of decision diagrams. Sifting, in particular, has emerged as a very good compromise between low CPU time requirements and high quality of results. Sifting, however, has the absolute position of a variable as the primary objective, and only considers the relative positions of groups of variables indirectly. In this paper we propose an extension to sifting that may move groups of variables simultaneously to produce better results. Variables are aggregated by checking whether they have a strong affinity to their neighbors. (Hence the title.) Our experiments show an average improvement in size of 11%. This improvement, coupled with the greater robustness of the algorithm, more than offsets the modest increase in CPU time that is sometimes incurred.

REFERENCES

• 1: R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
• 2: B. Bollig, M. LSbbing, and I. Wegener. Simulated annealing to improve variable orderings for OBDDs. Presented at IWLS, Granlibakken, CA, May 1995.
• 3: Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
• 4: Randy E. Bryant , Yirng Chen, Verification of Arithmetic Functions with Binary Moment Diagrams, Carnegie Mellon University, Pittsburgh, PA, 1994
• 5: 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]
• 6: M. Fujita, H. Fujisawa, and N. Kawato. Evaluation and improvements of boolean comparison method based on binary decision diagrams. In Proc. ICCAD, pages 2-5, Nov. 1988.
• 7: 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
• 8: N. Ishiura, H. Sawada, and S. Yajima. Minimization of binary decision diagrams based on exchanges of variables. In Proc. ICCAD, pages 472-475, Santa Clara, CA, Nov. 1991.
• 9: Y.-T. Lai , S. Sastry, Edge-valued binary decision diagrams for multi-level hierarchical verification, Proceedings of the 29th ACM/IEEE conference on Design automation, p.608-613, June 08-12, 1992, Anaheim, California, United States
• 10: S. Malik, A. Wang, R. Brayton, and A. Sangiovanni- Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In Proc. ICCAD, pages 6-9, Santa Clara, CA, Nov. 1988.
• 11: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• 12: D. MSller, P. Molitor, and R. Drechsler. Symmetry based variable ordering for ROBDDs. In IFIP Workshop on Logic and Architecture Synthesis, Grenoble, Dec. 1994.
• 13: Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States
• 14: 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
• 15: S. Yang. Logic synthesis and optimization benchmarks user guide version 3.0. Technical report, MCNC, Research Triangle Park, NC, Jan. 1991.
• 16: H. Cho, G. D. Hachtel, E. Macii, M. Poncino, K. Ravi, and F. Somenzi, "Approximate finite state machine traversal: Extensions and new results." Presented at IWLS95, Lake Tahoe, CA., May 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Measurement, Performance, Theory