We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 32 Issue 2
March  2017
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Zhen-Xue He, Li-Min Xiao, Li Ruan, Fei Gu, Zhi-Sheng Huo, Guang-Jun Qin, Ming-Fa Zhu, Long-Bing Zhang, Rui Liu, Xiang Wang. A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean Functions[J]. Journal of Computer Science and Technology, 2017, 32(2): 297-311. DOI: 10.1007/s11390-017-1723-1
Citation: Zhen-Xue He, Li-Min Xiao, Li Ruan, Fei Gu, Zhi-Sheng Huo, Guang-Jun Qin, Ming-Fa Zhu, Long-Bing Zhang, Rui Liu, Xiang Wang. A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean Functions[J]. Journal of Computer Science and Technology, 2017, 32(2): 297-311. DOI: 10.1007/s11390-017-1723-1
shu

A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean Functions

  • 1 State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China;
    2 School of Computer Science and Engineering, Beihang University, Beijing 100191, China;
    3 School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
    4 State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China;
    5 University of Chinese Academy of Sciences, Beijing 100049, China;
    6 National Engineering Research Center for Science and Technology Resources Sharing Service, Beihang University Beijing 100191, China

Funds: This work is supported by the National Natural Science Foundation of China under Grant Nos. 60973106, 61370059, 61232009, and 81571142, Beijing Natural Science Foundation under Grant No. 4152030, the Fundamental Research Funds for the Central Universities of China under Grant Nos. YWF-15-GJSYS-085 and YWF-14-JSJXY-14, the Fund of the State Key Laboratory of Computer Architecture of China under Grant No. CARCH201507, the Open Project Program of National Engineering Research Center for Science and Technology Resources Sharing Service (Beihang University), and the Fund of the State Key Laboratory of Software Development Environment of China under Grant No. SKLSDE-2016ZX-15.
More Information
  • Author Bio:

    Zhen-Xue He is a Ph.D. candidate in the School of Computer Science and Engineering, Beihang University, Beijing. He received his M.S. degree in computer application technology from Northwest Normal University, Lanzhou, in 2014. His research interests include electronic design automation, low power design and artificial intelligence.

  • Corresponding author:

    Li-Min Xiao E-mail: xiaolm@buaa.edu.cn

  • Received Date: December 18, 2015
  • Revised Date: January 03, 2017
  • Published Date: March 04, 2017
    Abstract
  • The power and area optimization of Reed-Muller (RM) circuits has been widely concerned. However, almost none of the exiting power and area optimization approaches can obtain all the Pareto optimal solutions of the original problem and are efficient enough. Moreover, they have not considered the don't care terms, which makes the circuit performance unable to be further optimized. In this paper, we propose a power and area optimization approach of mixed polarity RM expression (MPRM) for incompletely specified Boolean functions based on Non-Dominated Sorting Genetic Algorithm II (NSGA-II). Firstly, the incompletely specified Boolean function is transformed into zero polarity incompletely specified MPRM (ISMPRM) by using a novel ISMPRM acquisition algorithm. Secondly, the polarity and allocation of don't care terms of ISMPRM is encoded as chromosome. Lastly, the Pareto optimal solutions are obtained by using NSGA-II, in which MPRM corresponding to the given chromosome is obtained by using a chromosome conversion algorithm. The results on incompletely specified Boolean functions and MCNC benchmark circuits show that a significant power and area improvement can be made compared with the existing power and area optimization approaches of RM circuits.
    • FullText(HTML)
    • References (32)
  • [1]
    Wang P J, Li K P, Zhang H H. PMGA and its application in area and power optimization for ternary FPRM circuit. Journal of Semiconductors, 2016, 37(1):015007.
    [2]
    Xiao L M, He Z X, Ruan L, Zhang R, Xia T S, Wang X. Optimization of best polarity searching for mixed polarity Reed-Muller logic circuit. In Proc. the 28th IEEE International System-on-Chip Conference, Sept. 2015, pp.275-280.
    [3]
    Wang X, Lu Y, Zhang Y, Zhao Z X, Xia T S et al. Probabilistic modeling during power estimation for mixed polarity Reed-Muller logic circuits. In Proc. IEEE International Conference on Green Computing and Communications, Aug. 2013, pp.1414-1418.
    [4]
    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. (in Chinese)
    [5]
    Bu D L, Jiang J H. Dual logic based polarity conversion and optimization of mixed polarity RM circuits. Acta Electronica Sinica, 2015, 43(1):79-85. (in Chinese)
    [6]
    Wang P J, Wang Z H, Xu R, Jiang Z D, Wang D S. Conversion algorithm for MPRM expansion. Journal of Semiconductors, 2014, 35(3):035007.
    [7]
    Wang Y H, Wang L Y, Xia Y S. A fast Reed-Muller fixed polarity conversion algorithm for large circuits. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(11):2091-2098. (in Chinese)
    [8]
    Fu Q, Wang P J, Tong N, Wang M B, Zhang H H. Multistrategy discrete particle swarm optimization. Acta Electronica Sinica, 2016, 44(5):1202-1207. (in Chinese)
    [9]
    Vijayakumari C K, Mythili P, James R K, Akhil K S. Optimal design of combinational logic circuits using genetic algorithm and Reed-Muller universal logic modules. In Proc. International Conference on Embedded Systems, July 2014.
    [10]
    Li K P, Wang P J, Zhang H H. The search of the best power of ternary FPRM circuit based on simulated annealing genetic algorithm. Journal of Zhejiang University (Science Edition), 2016, 43(2):190-199. (in Chinese)
    [11]
    Das A, Pradhan S N. Shared Reed-Muller decision diagram based thermal-aware AND-XOR decomposition of logic circuits. VLSI Design, 2016:Article ID3191286.
    [12]
    Zhang Q W, Wang P J, Hu J. Exact minimization of ESOP expressions based on hierarchical hypercube. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(1):172-179. (in Chinese)
    [13]
    Wang X, Lu Y, Zhang Y, Zhao Z X, Xia T S et al. Power optimization in logic synthesis for mixed polarity Reed-Muller logic circuits. The Computer Journal, 2015, 58(6):1307-1313.
    [14]
    Das A, Pradhan S N. Thermal aware FPRM based ANDXOR network synthesis of logic circuits. In Proc. the 2nd International Conference on Recent Trends in Information Systems, Sept. 2015, pp.497-502.
    [15]
    Kim I Y, de Weck O L. Adaptive weighted-sum method for bi-objective optimization:Pareto front generation. Structural and Multidisciplinary Optimization, 2005, 29(2):149-158.
    [16]
    Debnath D, Sasao T. Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functions. In Proc. Asia and South Pacific Design Automation Conference, Jan. 2000, pp.247-252.
    [17]
    Habib M K. A new approach to generate fixed-polarity Reed-Muller expansions for completely and incompletely specified functions. Int. J. Electronics, 2002, 89(11):845-876.
    [18]
    Deb K, Agarwal S, Pratap A, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
    [19]
    Zhang H H, Wang P J. Polarity optimization of XNOR/OR circuit area and power based on weighted sum method. In Proc. the 9th IEEE International Conference on ASIC, Oct. 2011, pp.341-344.
    [20]
    Wang P J, Wang D S, Jiang Z D, Zhang H H. Area and power optimization of ISFPRM circuits based on PSGA algorithm. Acta Electronica Sinica, 2013, 41(8):1542-1548. (in Chinese)
    [21]
    Chaudhury S, Chattopadhyay S. Fixed polarity Reed-Muller network synthesis and its application in ANDOR/XOR-based circuit realization with area-power tradeoff. IETE Journal of Research, 2008, 54(5):353-363.
    [22]
    Wu W J, Wang P J, Zhang X Y, Wang L L et al. Search for the best polarity of multi-output RM circuits based on QGA. In Proc. the 2nd International Symposium on Intelligent Information Technology Application, Dec. 2008, pp.279-282.
    [23]
    Xia Y, Ali B, Almaini A E A. Area and power optimization of FPRM function based circuits. In Proc. International Symposium on Circuits and Systems, May 2003, pp.329-332.
    [24]
    Wang D S, Wang P J. Algorithm about minimization of MPRM expansions including don't care terms. Journal of Zhejiang University (Science Edition), 2014, 41(1):38-42. (in Chinese)
    [25]
    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. (in Chinese)
    [26]
    Al Jassani B A, Urquhart N, Almaini A E A. Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. In Proc. the 3rd International Conference on Signals, Circuits and Systems, Nov. 2009.
    [27]
    Debatosh D, Tsutomu S. Exact minimization of FPRMs for incompletely specified functions by using MTBDDs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer, 2005, 88-A(12):3332-3341.
    [28]
    Wang D S, Wang P J. Power optimization of incompletely specified fixed polarity Reed-Muller circuits. In Proc. the 11th International Conference on Solid-State and Integrated Circuit Technique, Oct.29-Nov.1, 2012.
    [29]
    Almaini A E A, Mckenzie L. Tabular techniques for generating kronecker expansions. IEE Proceedings-Computers and Digital Techniques, 1996, 143(4):205-212.
    [30]
    Xia Y S, Wu X W, Almaini A E A. Power minimization of FPRM functions based on polarity conversion. Journal of Computer Science and Technology, 2003, 18(3):325-331.
    [31]
    Pradhan S N, Chattopadhyay S. AND-XOR network synthesis with area-power trade-off. In Proc. the 3rd International Conference on Industrial and Information Systems, Dec. 2008.
    [32]
    Chu Z F, Xia Y S, Wang L Y. Cell mapping for nanohybrid circuit architecture using genetic algorithm. Journal of Computer Science and Technology, 2012, 27(1):113-120.
    • Relative Articles

  • Related Articles

    [1]Fabio Caffaro, Giuseppe Rizzo. Knowledge-Enhanced Conversational Agents[J]. Journal of Computer Science and Technology, 2024, 39(3): 585-609. DOI: 10.1007/s11390-024-2883-4
    [2]Ze-Lin Zhao, Di Huang, Xiao-Xing Ma. TOAST: Automated Testing of Object Transformers in Dynamic Software Updates[J]. Journal of Computer Science and Technology, 2022, 37(1): 50-66. DOI: 10.1007/s11390-021-1693-1
    [3]Wei-Bei Fan, Jian-Xi Fan, Cheng-Kuan Lin, Yan Wang, Yue-Juan Han, Ru-Chuan Wang. Optimally Embedding 3-Ary n-Cubes into Grids[J]. Journal of Computer Science and Technology, 2019, 34(2): 372-387. DOI: 10.1007/s11390-019-1893-0
    [4]Fang-Fang Dong, Zhen Liu. A New Gradient Fidelity Term for Avoiding Staircasing Effect[J]. Journal of Computer Science and Technology, 2009, 24(6): 1162-1170.
    [5]Wei Wang, Yu Hu, Yin-He Han, Xiao-Wei Li, You-Sheng Zhang. Leakage Current Optimization Techniques During Test Based on Don t Care Bits Assignment[J]. Journal of Computer Science and Technology, 2007, 22(5): 673-680.
    [6]Yin-Shui Xia, Lun-Yao Wang, Zong-Gang Zhou, Xi-En Ye, Jian-Ping Hu, A E A Almaini. Novel Synthesis and Optimization of Multi-Level Mixed Polarity Reed-Muller Functions[J]. Journal of Computer Science and Technology, 2005, 20(6): 895-900.
    [7]XIA YinShui, WU XunWei, A. E. A. Almaini. Power Minimization of FPRM Functions Based on Polarity Conversion[J]. Journal of Computer Science and Technology, 2003, 18(3).
    [8]Gao Qingshi, Liu Zhiyong. K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations[J]. Journal of Computer Science and Technology, 1995, 10(5): 417-424.
    [9]Zhang Xubo. Some Results on the Confluence Property of Combined Term Rewriting Systems[J]. Journal of Computer Science and Technology, 1991, 6(3): 291-295.
    [10]Zhang Xing er, Zhu Xiaojun, Li Jianxin, Dong Jianning. Source-to-Source Conversion Based on Formal Definition[J]. Journal of Computer Science and Technology, 1991, 6(2): 178-184.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (34) PDF downloads (1098) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return