EDOA: an efficient delay optimization approach for mixed-polarity Reed-Muller logic circuits under the unit delay model

Abstract

Delay optimization has recently attracted significant attention. However, few studies have focused on the delay optimization of mixed-polarity Reed-Muller (MPRM) logic circuits. In this paper, we propose an efficient delay optimization approach (EDOA) for MPRM logic circuits under the unit delay model, which can derive an optimal MPRM logic circuit with minimum delay. First, the simplest MPRM expression with the fewest number of product terms is obtained using a novel Reed-Muller expression simplification approach (RMESA) considering don’t-care terms. Second, a minimum delay decomposition approach based on a Huffman tree construction algorithm is utilized on the simplestMPRM expression. Experimental results on MCNC benchmark circuits demonstrate that compared to the Berkeley SIS 1.2 and ABC, the EDOA can significantly reduce delay for most circuits. Furthermore, for a few circuits, while reducing delay, the EDOA incurs an area penalty.

Keywords

delay optimization / mixed-polarity Reed-Muller logic circuits / unit delay model / don’t-care terms / Huffman tree construction algorithm

References

[1] Wang X, Lu Y, Zhang Y. Power optimization in logic synthesis for mixed polarity Reed-Muller logic circuits. The Computer Journal, 2015, 58(6): 1307–1313

[2] Liang H, Xia Y S, Qian L B, Huang C L. Low power 3-input AND/XOR gate design. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(5): 940–945

[3] He Z X, Xiao L M, Gu F, Xia T S, Su S B, Huo Z S, Zhang R, Zhang L B, Ruan L, Wang X. An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits. Frontiers of Computer Science, 2017, 11(4): 728–742

[4] Wang P J, Wang Z H, Xu R. Conversion algorithm for MPRM expansion. Journals of Semiconductors, 2014, 35(3): 150–155

[5] Bu D L, Jiang J H. An efficient optimization algorithm for multi-output MPRM circuits with very large number of input variables. In: Proceedings of the 7th IEEE Joint International Conference on Information Technology and Artificial Intelligence. 2014, 228–232

[6] Geetha V, Devarajan N, Neelakantan P N. OR-Bridging fault analysis and diagnosis for exclusive-OR sum of products Reed-Muller canonical circuits. Journal of Computer Science, 2011, 7(5): 744–748

[7] Yang M, Tong J R, Lai J M. Optimisation of fixed polarity canonical or-coincidence expansions. Journal of Computers, 2013, 8(10): 2520–2526

[8] Laskar N M, Sen R, Paul P K, Bbishnab K L. A survey on VLSI floorplanning: its representation and modern approaches of optimization. In: Proceedings of International Conference on Innovations in Information Embedded and Communication Systems. 2015, 1–9

[9] Prakash A, Lal R K. PSO: an approach to multiobjective VLSI partitioning. In: Proceedings of International Conference on Innovations in Information, Embedded and Communication System. 2015, 1–7

[10] Jang I, Kim J, Kim S Y. Accurate delay models of CMOS CML circuits for design optimization. Analog Integrated Circuits and Signal Processing, 2015, 82(1): 297–307

[11] Severens B, Vansteenkiste E, Heyse K, Stroobandt D. Estimating circuit delays in FPGAs after technology mapping. In: Proceedings of International Conference on Field Programmable Logic and Applications. 2015, 1–4

[12] Liu Y F, Shelar R S, Hu J. Simultaneous technology mapping and placement for delay minimization. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 2011, 30(3): 416–426

[13] Almaini A E A. Electronic Logic Systems. New York: Prentice-Hall, 1994

[14] Yang M, Almaini A E A, Wang P J. FPGA placement optimization by two-step unified genetic algorithm and simulated annealing algorithm. Journal of Electronics, 2006, 23(4): 632–636

[15] Yu H Z, Jiang Z D, Wang P J, Li K P. GA-DTPSO algorithm and its application in area optimization of mixed polarity XNOR/OR circuits. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(5): 946–952

[16] Liang H, Xia Y S, Wang S H, Qian L B. A novel low power threeinput OR/XNOR gate design. Journal of Low Power Electronics, 2014, 10(3): 342–346

[17] Tan E C, Chia C Y, Wong K K. Reed-Muller versus traditional Boolean circuit implementation. In: Proceedings of IEEE Region International Conference on Microelectronics and VLSI. 1995, 175–178

[18] Shahana T K, James R K, Jacob K P, Sasi S. Automated synthesis of delay-reduced Reed-Muller universal logic module. In: Proceedings of NORCHIP Conference. 2005, 90–93

[19] Vijayakumari C K, Mythili P, James R K, Kumar S A. Optimal design of combinational logic circuits using genetic algorithm and Reed- Muller universal logic modules. In: Proceedings of International Conference on Embedded Systems. 2014, 1–6

[20] Wang P J, Wang Z H. Delay and area optimization for FPRM circuits by FDDs. Journal of Xidian University, 2013, 40(1): 135–140

[21] Wang Z H, Wang P J, Yu H Z, Zhang H H. Delay and area optimization for FPRM circuits based on PSO algorithm. Journal of Circuits and Systems, 2012, 17(5): 75–80

[22] Wang P J, Wang Z H, Chen Y W, Li H. Searching the best polarity for fixed polarity Reed-Muller circuits based on delay model. Journal of Zhejiang University (Engineering Science), 2013, 47(2): 361–367

[23] Sampson M, Kalathas M, Voudouris D, Papakonstantinou G. Exact ESOP expansion for incompletely specified functions. Integration, 2012, 45(2): 197–204

[24] Jassani B A, Almaini A E A, Urquhart N. Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. In: Proceedings of International Conference on Signals, Circuits and Systems. 2009, 1–6

[25] DEBNATH D, SASAO T. Exact minimization of FPRMs for incompletely specified functions by using MTBDDs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer, 2005, 88(12): 3332–3341

[26] Wang D S, Wang P J, Sun F, Yu H Z. Fixed-polarity conversions for logic functions include don’t care terms. Journal of Circuits and Systems, 2013, 18(1): 117–121

[27] Wang D S, Wang P J. Algorithms about minimization of MPRM expansions including don’t care terms. Journal of Zhejiang University (Science Edition), 2014, 41(1): 38–43

[28] Fujita M, Murgai R. Delay estimation and optimization of logic circuits: a survey. In: Proceedings of Asia and South Pacific Design Automation Conference. 1997, 25–30

[29] Zhang X L, Zuo G C, Yang J. Solving travelling salesman problem by genetic algorithm with heuristic mutation strategy. Computer Applications and Software, 2010, 27(3): 237–240

[30] Varma D, Trachtenberg E A. Computation of Reed-Muller expansions of incompletely specified Boolean functions from reduced representations. IEE Proceedings E (Computer and Digital Techniques), 1991, 138(2): 85–92

[31] Almaini A E A, Mckenzie L. Tabular techniques for generating kronecker expansions. IEE Proceedings — Computers and Digital Techniques, 1996, 143(4): 205–212

[32] Yang M, Xu H Y, Almaini A E A. Optimization of mixed polarity Reed- Muller functions using genetic algorithm. In: Proceedings of International Conference on Computer Research and Development. 2011, 293–296

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature