The optimization of kEP-SOPs: Computational complexity, approximability and experiments

ABSTRACT

We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NP^NP-hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis.

REFERENCES

• 1: Bernasconi, A., Ciriani, V., and Cordone, R. 2006. EXOR projected sum of products. In Proceedings of the 14th International Conference on Very Large Scale Integration.
• 2: Anna Bernasconi , Valentina Ciriani , Roberto Cordone, An approximation algorithm for fully testable kEP-SOP networks, Proceedings of the 17th ACM Great Lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy [doi>10.1145/1228784.1228883]
• 3: Anna Bernasconi , Valentina Ciriani , Rolf Drechsler , Tiziano Villa, Efficient minimization of fully testable 2-SPP networks, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 4: Bernasconi, A., Ciriani, V., Luccio, F., and Pagli, L. 2003. Three-Level logic minimization based on function regularities. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 22, 8, 1005--1016.
• 5: 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
• 6: Breuer, M. and Friedman, A. 1976. Diagnosis and Reliable Design of Digital Systems. Computer Science Press.
• 7: Caruso, G. 1991. Near optimal factorization of Boolean functions. IEEE Trans. Comput.-Aided Des. 10, 8, 1072--1078.
• 8: Ciriani, V., Bernasconi, A., and Drechsler, R. 2006. Testability of SPP three-level logic networks in static fault models. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 25, 10, 2241--2248.
• 9: Cordone, R., Ferrandi, F., Sciuto, D., and Wolfler Calvo, R. 2001. An efficient heuristic approach to solve the unate covering problem. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 20, 12 (Dec.), 1377--1388.
• 10: Olivier Coudert, Two-level logic minimization: an overview, Integration, the VLSI Journal, v.17 n.2, p.97-140, Oct. 1994 [doi>10.1016/0167-9260(94)00007-7 ]
• 11: Debatosh Debnath , Tsutomu Sasao, Multiple-Valued Minimization to Optimize PLAs with Output EXOR Gates, Proceedings of the Twenty Ninth IEEE International Symposium on Multiple-Valued Logic, p.99, May 20-22, 1999
• 12: Debnath, D. and Vranesic, Z. 2003. A fast algorithm for OR-AND-OR synthesis. IEEE Trans. Comput.-Aided Des. 22, 9, 1166--1176.
• 13: Drechsler, R., Shi, J., and Fey, G. 2004. Synthesis of fully testable circuits from BDDs. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 23, 3, 440--443.
• 14: Dubrova, E. and Ellervee, P. 1999. A fast algorithm for three-level logic optimization. In Proceedings of the International Workshop on Logic Synthesis, 251--254.
• 15: Dubrova, E., Miller, D., and Muzio, J. 1999. AOXMIN-MV: A heuristic algorithm for AND-OR-XOR minimization. In Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in Circuit Design, 37--54.
• 16: Masahiro Fujita , Yusuke Matsunaga , Maciej Ciesielski, Multi-level logic optimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Ishikawa, R., Hirayama, T., Koda, G., and Shimizu, K. 2004. New three-level boolean expression based on EXOR gates. IEICE Trans. Inf. Syst. 5, 1214--1222.
• 19: Ishikawa, R., Igarashi, T., Hirayama, T., and Shimizu, K. 2002. Pseudocube-Based expressions to enhance testability. In Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, vol. 2, 305--310.
• 20: Fabrizio Luccio , Linda Pagli, On a New Boolean Function with Applications, IEEE Transactions on Computers, v.48 n.3, p.296-310, March 1999 [doi>10.1109/12.754996 ]
• 21: Abdul A. Malik , David Harrison , Robert K. Brayton, Three-Level Decomposition with Application to PLDs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.628-633, October 14-16, 1991
• 22: McGeer, P., Sanghavi, J., Brayton, R., and Sangiovanni-Vincentelli, A. 1993. Espresso-Signature: A new exact minimizer for logic functions. IEEE Trans. VLSI 1, 4, 432--440.
• 23: Rudell, R. and Sangiovanni-Vincentelli, A. 1987. Multiple-valued minimization for PLA optimization. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 6, 727--750.
• 24: Sasao, T. 1995. A design method for AND-OR-EXOR three level networks. In Proceedings of the International Workshop on Logic Synthesis. 8, 11--8:20.
• 25: Tsutomu Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers, Norwell, MA, 1999
• 26: Sentovich, E., Singh, K., Lavagno, L., Moon, C., R. Murgai, A. S., Savoj, H., Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Tech. Rep. UCB-ERL M92-41. University of California at California.
• 27: Christopher Matthew Umans , Christos H. Papadimitriou, Approximability and completeness in the polynomial hierarchy, University of California, Berkeley, 2000
• 28: Umans, C., Villa, T., and Sangiovanni-Vincentelli, A. 2006. Complexity of two-level logic minimization. IEEE Trans. Comput.-Aided Des. 25, 7, 1230--1246.
• 29: Yang, S. 1991. Logic synthesis and optimization benchmarks user guide, version 3.0. Microelectronic Center.

INDEX TERMS

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

General Terms:
Experimentation, Theory, Verification

Keywords:
Automatic synthesis, approximation algorithm, multilevel logic synthesis, optimization, testing