Power and Delay Optimized Graph Representation for Combinational Logic Circuits

Structural representation and technology mapping of a Boolean function is an important problem in the design of nonregenerative digital logic circuits (also called combinational logic circuits). Library aware function manipulation offers a solution to this problem. Compact multi-level representation of binary networks, based on simple circuit structures, such as AND-Inverter Graphs (AIG) [1] [5], NAND Graphs, OR-Inverter Graphs (OIG), AND-OR Graphs (AOG), AND-OR-Inverter Graphs (AOIG), AND-XORInverter Graphs, Reduced Boolean Circuits [8] does exist in literature. In this work, we discuss a novel and efficient graph realization for combinational logic circuits, represented using a NAND-NOR-Inverter Graph (NNIG), which is composed of only two-input NAND (NAND2), NOR (NOR2) and inverter (INV) cells. The networks are constructed on the basis of irredundant disjunctive and conjunctive normal forms, after factoring, comprising terms with minimum support. Construction of a NNIG for a non-regenerative function in normal form would be straightforward, whereas for the complementary phase, it would be developed by considering a virtual instance of the function. However, the choice of best NNIG for a given function would be based upon literal count, cell count and DAG node count of the implementation at the technology independent stage. In case of a tie, the final decision would be made after extracting the physical design parameters. We have considered AIG representation for reduced disjunctive normal form and the best of OIG/AOG/AOIG for the minimized conjunctive normal forms. This is necessitated due to the nature of certain functions, such as Achilles- heel functions. NNIGs are found to exhibit 3.97% lesser node count compared to AIGs and OIG/AOG/AOIGs; consume 23.74% and 10.79% lesser library cells than AIGs and OIG/AOG/AOIGs for the various samples considered. We compare the power efficiency and delay improvement achieved by optimal NNIGs over minimal AIGs and OIG/AOG/AOIGs for various case studies. In comparison with functionally equivalent, irredundant and compact AIGs, NNIGs report mean savings in power and delay of 43.71% and 25.85% respectively, after technology mapping with a 0.35 micron TSMC CMOS process. For a comparison with OIG/AOG/AOIGs, NNIGs demonstrate average savings in power and delay by 47.51% and 24.83%. With respect to device count needed for implementation with static CMOS logic style, NNIGs utilize 37.85% and 33.95% lesser transistors than their AIG and OIG/AOG/AOIG counterparts.

Authors:

• Padmanabhan Balasubramanian
• Karthik Anantha

Keywords:

• AND-Inverter Graph
• OR-Inverter Graph
• DirectedAcyclic Graph
• Low power design
• Delay optimization.

References:

[1] A. Mishchenko, and R.K. Brayton, "Scalable logic synthesis using a
simple circuit structure," Proc. of International Workshop on Logic
Synthesis, 2006, pp. 15-22.
[2] A. Mishchenko, S. Chatterjee, and R. Brayton, "DAG-Aware AIG
rewriting A fresh look at combinational logic synthesis," 43rd ACM/IEEE
Design Automation Conference, 2006, pp. 532-535.
[3] A. Mishchenko, S. Chatterjee, R. Brayton, and P. Pan, "Integrating logic
synthesis, technology mapping, and retiming," ERL Technical Report,
EECS Dept., UC Berkeley, April 2006.
[4] A. Mishchenko, and R.K. Brayton, "Scalable logic synthesis using a
simple circuit structure," Proc. of International Workshop on Logic
Synthesis, 2006, pp. 15-22.
[5] A. Mishchenko, S. Chatterjee, R. Jiang, and R.K. Brayton, "FRAIGs: A
unifying representation for logic synthesis and verification," ERL
Technical Report, UCB, March 2005.
[6] N. Een, and N. Sorensson, "An extensible SAT-solver," 6th International
Conference on Theory and Applications of Satisfiability Testing, 2003,
pp. 502-518.
[7] L. Hellerman, "A catalog of 3-variable OR-Inverter and AND-Inverter
logical circuits," IEEE Transactions on Electr. Comput. vol. 12, pp. 198-
223, 1963.
[8] P. Bjesse, and A. Boralv, "DAG-aware circuit compression for formal
verification," International Conference on Computer Aided Design,
pp. 42-49, 2004.
[9] G.L. Smith et al., "Boolean comparison of hardware and flowcharts,"
IBM Jour. of Research and Development, vol. 26(1), 1982, pp.106-116.
[10] A. Mishchenko, et al., "Using simulation and satisfiability to compute
flexibilities in Boolean networks," IEEE Trans. on CAD of Integrated
Circuits and Systems, vol. 25(5), May 2006, pp. 743-755.
[11] A. Mishchenko, Available: www.eecs.berkeley.edu/~alanmi/abc
[12] M. Morris Mano, Digital Design. New Jersey: Prentice Hall, 2002.
[13] P.C. McGeer, J.V. Sanghavi, R.K. Brayton, and A.L. Sangiovanni-
Vincentelli, "ESPRESSO-SIGNATURE: a new exact minizer for logic
functions," IEEE Trans. on VLSI Systems, vol. 1(4), pp. 432-440,
December 1993.
[14] Peter L. Hammer, and Alexander Kogan, "Horn functions and their
DNFs," Information Processing Letters, vol. 44(1), pp.23-29,
November 1992.