A robust algorithm for approximate compatible observability don't care (CODC) computation

ABSTRACT

Compatible Observability Don't Cares (CODCs) are a powerful means to express the flexibility present at a node in a multi-level logic network. Despite their elegance, the applicability of CODCs has been hampered by their computational complexity. The CODC computation for a network involves several image computations, which require the construction of global BDDs of the circuit nodes. The size of BDDs of circuit nodes is unpredictable, and as a result, the CODC computation is not robust. In practice, CODCs cannot be computed for large circuits due to this limitation.In this paper, we present an algorithm to compute approximate CODCs (ACODCs). This algorithm allows us to compute compatible don't cares for significantly larger designs. Our ACODC algorithm is scalable in the sense that the user may trade off time and memory against the accuracy of the ACODCs computed. The ACODC is computed by considering a subnetwork rooted at the node of interest, up to a certain topological depth, and performing its don't care computation. We prove that the ACODC is an approximation of its CODC.We have proved the soundness of the approach, and performed extensive experiments to explore the trade-off between memory utilization, speed and accuracy. We show that even for small topological depths, the ACODC computation gives very good results. Our experiments demonstrate that our algorithm can compute ACODCs for circuits whose CODC computation has not been demonstrated to date. Also, for a set of benchmark circuits whose CODC computation yields an average 28% reduction in literals after optimization, our ACODC computation yields an average 22% literal reduction. Our algorithm has runtimes which are about 25x and memory utilization which is 33x better that of the CODC computation of SIS.

REFERENCES

• 1: R. K. Brayton, Compatible observability don't cares revisited, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 2: R. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang. Mis: A multiple-level logic optimization system. IEEE Trans. on CAD/ICAS, CAD-6(6):1062--1082, Nov 1987.
• 3: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 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: M. Damiani and G. D. Micheli. Observability don't care sets and boolean relations. In IEEE/ACM International Conference on Computer Aided Design, Nov 1990.
• 6: S. Dey, F. Brglez, and G. Kedem. Circuit partitioning and resynthesis. In Proceedings of the IEEE Custom Integrated Circuits Conference, pages 29.4/1--29.4/5, May 1990.
• 7: Soha Hassoun , Tsutomu Sasao, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
• 8: J. C. Limqueco and S. Muroga. SYLON-REDUCE: an MOS network optimization algorithms using permissible functions. In Proceedings, IEEE International Conference on Computer Design, pages 282--285, Sept 1990.
• 9: J. C. Limqueco and S. Muroga. Optimizing large networks by repeated local optimization using windowing scheme. In IEEE International Symposium on Circuits and Systems, ISCAS, volume 4, pages 1993--1996, May 1992.
• 10: S. Malik, A. R. Wang, R. K. Brayton, and A. Sangiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In IEEE International Conference on Computer-Aided Design, pages 6--9, November 1998.
• 11: P. C. McGeer and R. K. Brayton. The observability don't care set and its approximations. In IEEE International Conference on Computer Design, Sept. 1990.
• 12: Alan Mishchenko , Robert Brayton, Simplification of non-deterministic multi-valued networks, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.557-562, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774654]
• 13: Hamid Savoj , Robert K. Brayton, The use of observability and external don't cares for the simplification of multi-level networks, Proceedings of the 27th ACM/IEEE conference on Design automation, p.297-301, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123280]
• 14: H. Savoj, R. Brayton, and H. Touati. Extracting local don't cares for network optimization. In IEEE/ACM International Conference on Computer Aided Design, pages 514--517, Nov 1991.
• 15: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Technical Report UCB/ERL M92/41, Electronics Research Lab, Univ. of California, Berkeley, CA 94720, May 1992.
• 16: Ted Stanion , Carl Sechen, Maximum projections of don't care conditions in a Boolean network, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.674-679, November 07-11, 1993, Santa Clara, California, United States
• 17: H. Touati, H. Savoj, B. Lin, R. Brayton, and A. Sangiovanni-Vincentelli. Implicit state enumeration of finite state machines using BDDs. In IEEE International Conference on Computer-Aided Design, November 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
compatible observability don't cares (CODC), logic synthesis, multi-level logic optimization