Analysis of Effect of Pre-Logic Factoring on Cell Based Combinatorial Logic Synthesis

In this paper, an analysis is presented, which demonstrates the effect pre-logic factoring could have on an automated combinational logic synthesis process succeeding it. The impact of pre-logic factoring for some arbitrary combinatorial circuits synthesized within a FPGA based logic design environment has been analyzed previously. This paper explores a similar effect, but with the non-regenerative logic synthesized using elements of a commercial standard cell library. On an overall basis, the results obtained pertaining to the analysis on a variety of MCNC/IWLS combinational logic benchmark circuits indicate that pre-logic factoring has the potential to facilitate simultaneous power, delay and area optimized synthesis solutions in many cases.

Authors:

• Padmanabhan Balasubramanian
• Bashetty Raghavendra

Keywords:

• Algebraic factoring
• Combinational logic synthesis
• Standard cells
• Low power
• Delay optimization
• Area reduction.

References:

[1] R. Ashenhurst, "The decomposition of switching functions," Proc.
International Symposium on Switching Theory, 1959, pp. 74-116.
[2] R. Brayton and C. McMullen, "The decomposition and factorization of
Boolean expressions," Proc. International Symposium on Circuits and
Systems, 1982, pp. 49-54.
[3] R.K. Brayton, "Factoring logic functions," IBM Journal of Research and
Development, vol. 31, no. 2, March 1987, pp. 187-198.
[3] R. Rudell, "Logic Synthesis for VLSI Design", PhD thesis, University of
California, Berkeley, 1989.
[5] J. Vasudevamurthy and J. Rajski, "A method for concurrent
decomposition and factorization of Boolean expressions," Proc.
International Conf. on Computer-Aided Design, 1990, pp. 510-513.
[6] G. Caruso, "Near optimal factorization of Boolean functions," IEEE
Trans. on CAD, vol. 10, no. 8, August 1991, pp. 1072-1078.
[7] R.K. Brayton, G.D. Hachtel and A.L. Sangiovanni-Vincentelli,
"Multilevel logic synthesis," Proc. of the IEEE, vol. 78, no. 2, February
1990, pp. 264-300.
[8] S. Yang, "Logic synthesis and optimization benchmarks User guide
version 3.0," MCNC Research Triangle Park, NC, January 1991.
[9] K. McElvain, "IWLS -93 Benchmark set: version 4.0," distributed as
part of the MCNC International Workshop on Logic Synthesis, 1993.
[10] P. Balasubramanian and R.T. Naayagi, "Critical path delay and net delay
reduced tree structure for combinational logic circuits," International
Journal of Electronics, Circuits and Systems, vol. 1, no. 1, Winter 2007,
pp. 19-29.
[11] P. Balasubramanian and R. Arisaka, "A set theory based factoring
technique and its use for low power logic design," International Journal
of Electrical, Computer and Systems Engineering, vol. 1, no. 3, Summer
2007, pp. 188-198.
[12] R.K. Brayton, A.L. Sangiovanni-Vincentelli, C.T. McMullen and G.D.
Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer
Academic Publishers, Norwell, MA, USA, 1984.
[13] J. Cortadella, "Timing-driven logic bi-decomposition," IEEE Trans. on
Computer Aided Design of Integrated Circuits and Systems, vol. 22, no.
6, June 2003, pp. 675-685.
[14] P. Balasubramanian, R.T. Naayagi, A. Karthik and B. Raghavendra,
"Evaluation of logic network representations for Achilles heel Boolean
functions," International Journal of Computers, Systems and Signals,
vol. 9, no. 1, 2008, pp. 42-55.