Power and Delay Optimized Graph Representation for Combinational Logic Circuits

Authors: Padmanabhan Balasubramanian, Karthik Anantha

Abstract:

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.

Keywords: AND-Inverter Graph, OR-Inverter Graph, DirectedAcyclic Graph, Low power design, Delay optimization.

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

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.