A Set Theory Based Factoring Technique and Its Use for Low Power Logic Design

Authors: Padmanabhan Balasubramanian, Ryuta Arisaka

Abstract:

Factoring Boolean functions is one of the basic operations in algorithmic logic synthesis. A novel algebraic factorization heuristic for single-output combinatorial logic functions is presented in this paper and is developed based on the set theory paradigm. The impact of factoring is analyzed mainly from a low power design perspective for standard cell based digital designs in this paper. The physical implementation of a number of MCNC/IWLS combinational benchmark functions and sub-functions are compared before and after factoring, based on a simple technology mapping procedure utilizing only standard gate primitives (readily available as standard cells in a technology library) and not cells corresponding to optimized complex logic. The power results were obtained at the gate-level by means of an industry-standard power analysis tool from Synopsys, targeting a 130nm (0.13μm) UMC CMOS library, for the typical case. The wire-loads were inserted automatically and the simulations were performed with maximum input activity. The gate-level simulations demonstrate the advantage of the proposed factoring technique in comparison with other existing methods from a low power perspective, for arbitrary examples. Though the benchmarks experimentation reports mixed results, the mean savings in total power and dynamic power for the factored solution over a non-factored solution were 6.11% and 5.85% respectively. In terms of leakage power, the average savings for the factored forms was significant to the tune of 23.48%. The factored solution is expected to better its non-factored counterpart in terms of the power-delay product as it is well-known that factoring, in general, yields a delay-efficient multi-level solution.

Keywords: Factorization, Set theory, Logic function, Standardcell based design, Low power.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071492

References:

[1] R.K. Brayton, G.D. Hachtel, C.T. McMullen, and A.L. Sangiovanni- Vincentelli, Logic minimization algorithms for VLSI synthesis, Kluwer Academic publishers, Boston, 1984.
[2] Sasan Iman, and Massoud Pedram, Logic synthesis for low power VLSI designs, New York, Springer Publishing, 1998.
[3] Farzad Nekoogar, and Faranak Nekoogar, From ASICs to SOCs: A Practical Approach, Prentice-Hall, 2003.
[4] T. Kuroda, "Low power high speed CMOS VLSI design," Proc. IEEE International Conf. on Computer Design, pp. 310-315, 2002.
[5] Semiconductor Industry Association's International Technology Roadmap on Semiconductors, Available: http://www.siaonline. org/backgrounders_itrs.cfm
[6] A.P. Chandrakasan, S. Sheng, and R.W. Broderson, "Low power CMOS digital design," IEEE Journal of Solid State Circuits, vol. 27(4), pp. 473-484, April 1992.
[7] K. McElvain, "IWLS '93 Benchmark Set: Version 4.0," distributed as part of the MCNC International Workshop on Logic Synthesis, Benchmark distribution, May 1993.
[8] S. Yang, "Logic synthesis and optimization benchmarks User Guide version 3.0," MCNC Research Triangle Park, NC, January 1991.
[9] R.K. Brayton, G.D. Hachtel, and A.L. Sangiovanni-Vincentelli, "Multilevel logic synthesis," Proceedings of the IEEE, vol. 78(2), pp. 264-300, February 1990.
[10] R.K. Brayton, and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. IEEE International Symposium on Circuits and Systems, pp. 49-54, 1982.
[11] R.K. Brayton, "Factoring logic functions," IBM Journal of Research and Development, vol. 31(2), pp. 187-198, March 1987.
[12] T. Stanion, and C. Sechen, "Boolean division and factorization using binary decision diagrams," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 13(9), pp. 1179-1184, September 1994.
[13] S.C. Chang, and D.I. Cheng, "Efficient Boolean division and substitution using redundancy addition and removing," IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 18(8), pp. 1096-1106, August 1999.
[14] 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," Electronics Research Laboratory Memorandum No. UCB/ERL/ M92/41, University of California, Berkeley, May 1992.
[15] R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A.R. Wang, "MIS: A Multiple-level logic optimization system," IEEE Trans. on CAD, vol. 6(6), pp. 1062-1081, November 1987.
[16] K. Keutzer, "DAGON: Technology binding and local optimization by DAG matching," Proc. 24th ACM/IEEE Design Automation Conference, pp. 341-347, 1987.
[17] G. Merrett, and B. Al-Hashimi, "Leakage power analysis and comparison of deep submicron logic gates," Proc. PATMOS, Lecture Notes in Computer Science, Springer, vol. 3254, pp. 198-207, 2004.
[18] T. Sakurai, and A.R. Newton, "A simple MOSFET model for circuit analysis," IEEE Trans. on Electron Devices, vol. 38(4), pp.887-893, April 1991.
[19] B. Sheu, D.L. Scharfetter, P.K. Ko, and M.C. Jeng, "BSIM: Berkeley Short-Channel IGFET Model for MOS transistors," IEEE Journal of Solid State Circuits, vol. 22(4), pp. 558-566, Aug. 1987.
[20] R.X. Gu, and M.I. Elmasry, "Power dissipation analysis and optimization of deep submicron CMOS digital circuits," IEEE Journal of Solid State Circuits, vol. 31(5), pp. 707-713, May 1996.
[21] R. Rudell, "Logic synthesis for VLSI design," PhD thesis, University of California, Berkeley, 1989.
[22] G. Caruso, "Near optimal factorization of Boolean functions," IEEE Trans. on CAD, vol. 10(8), pp. 1072-1078, August 1991.