An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits
Zhenxue HE1,2, Limin XIAO1,2(), Fei GU2, Tongsheng XIA3, Shubin SU2,5, Zhisheng HUO1,2, Rong ZHANG3, Longbing ZHANG4, Li RUAN1,2, Xiang WANG3()
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. National Engineering Research Center for Science & Technology Resources Sharing Service, Beijing 100191, China
Although the genetic algorithm has been widely used in the polarity optimization of mixed polarity Reed- Muller (MPRM) logic circuits, few studies have taken into account the polarity conversion sequence. In order to improve the efficiency of polarity optimization of MPRM logic circuits, we propose an efficient and fast polarity optimization approach (FPOA) considering the polarity conversion sequence. The main idea behind the FPOA is that, firstly, the best polarity conversion sequence of the polarity set waiting for evaluation is obtained by using the proposed hybrid genetic algorithm (HGA); secondly, each of polarity in the polarity set is converted according to the best polarity conversion sequence obtained by HGA. Our proposed FPOA is implemented in C and a comparative analysis has been presented for MCNC benchmark circuits. The experimental results show that for the circuits with more variables, the FPOA is highly effective in improving the efficiency of polarity optimization of MPRM logic circuits compared with the traditional polarity optimization approach which neglects the polarity conversion sequence and the improved polarity optimization approach with heuristic technique.
LiangH, XiaY S, QianL B, Huang C L. Low power 3-input AND/XOR gate design. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(5): 940–945
2
WangX, LuY, ZhangY. Probabilistic modeling during power estimation for mixed polarity Reed-Muller logic circuits. In: Proceedings of IEEE International Conference on Green Computing and Communications. 2013, 1414–1418 https://doi.org/10.1109/greencom-ithings-cpscom.2013.247
BuD L, JiangJ 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 Information Technology and Artificial Intelligence Conference. 2014, 228–232 https://doi.org/10.1109/itaic.2014.7065040
5
GeethaV, Devarajan N, NeelakantanP 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 https://doi.org/10.3844/jcssp.2011.744.748
6
YuH Z, JiangZ D, WangP J. 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
7
LiX W, XiaY S, WangL Y. An improved tabular-technique for mixpolarity. Journal of Ningbo University (NSEE), 2015, 28(1): 42–46
8
LiH, WangP J, DaiJ. Area minimization of MPRM circuits. In: Proceedings of the 8th International Conference on ASIC. 2009, 521–524
9
AlmainiA E A, McKenzie L. Tabular techniques for generating kronecker expansions. IEE Proceedings — Computers and Digital Techniques, 1996, 143(4): 205–212 https://doi.org/10.1049/ip-cdt:19960564
10
WangL, Almaini A E A. Exact minimisation of large multiple output FPRM functions. Computers and Digital Techniques, 2002, 149(5): 203–212 https://doi.org/10.1049/ip-cdt:20020674
11
BeckerB, Drechsler R. OFDD based minimization of fixed polarity Reed-Muller expressions using hybrid genetic algorithms. In: Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers and Processors. 1994, 106–110 https://doi.org/10.1109/iccd.1994.331866
12
PurwarS. An efficient method of computing generalized Reed-Muller expansions from binary decision diagram. IEEE Transactions on Computers, 1991, 40(11): 1298–1301 https://doi.org/10.1109/12.102837
13
SunF, WangP J, YuH Z. Ternary FPRM circuit area optimization based on genetic algorithm. Journal of Shandong University (Natural Science), 2013, 48(5): 51–56
14
BuD L, JiangJ H. Dual logic based polarity conversion and optimization of mixed polarity RM circuits. Acta Electronica Sinica, 2015, 43(1): 79–85
15
MudaliarD N, ModiN K. Unraveling travelling salesman problem by genetic algorithm using m-crossover operator. In: Proceedings of the International Conference on Signal Processing, Image Processing and Pattern Recognition (ICSIPR). 2013, 127–130 https://doi.org/10.1109/icsipr.2013.6497974
16
ThomsonP, MillerJ F. Optimisation techniques based on the use of genetic algorithms (Gas) for logic implementation on FPGAs. In: Proceedings of IEE Colloquium on Software Support and CAD Techniques for FPGAs. 1994
17
DrechslerR, BeckerB, GockelN. A genetic algorithm for the construction of small and highly testable OKFDD-circuits. In: Proceedings of the 1st Annual Conference on Genetic Programming. 1996, 473–478
18
CongJ, DingY Z. Combinational logic synthesis for LUT based field programmable gate arrays.ACM Transactions on Design Automation of Electronic Systems, 1996, 1(2): 145–204 https://doi.org/10.1145/233539.233540
WangP J, LiH, WangZ H. MPRM expressions minimization based on simulated annealing genetic algorithm. In: Proceedings of the International Conference on Intelligent Systems and Knowledge Engineering (ISKE). 2010, 261–265 https://doi.org/10.1109/iske.2010.5680868
21
JassaniA, Urquhart N, AlmainiA E A . Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. In: Proceedings of the 3rd International Conference on Signals, Circuits and Systems. 2009, 1–6 https://doi.org/10.1109/icscs.2009.5412318
22
YangM, XuH Y, AlmainiA E A . Optimization of mixed polarity Reed-Muller functions using genetic algorithm. In: Proceedings of the 3rd International Conference on Computer Research and Development (ICCRD). 2011, 293–296 https://doi.org/10.1109/iccrd.2011.5764198
23
SunF, WangP J, YuH Z. Best polarity searching for ternary FPRM logic circuit area based on whole annealing genetic algorithm. In: Proceedings of the 10th IEEE International Conference on ASIC (ASICON). 2013, 1–4
24
DrechslerR, BeckerB, DrechslerN. Genetic algorithm for minimisation of fixed polarity Reed-Muller expressions. Computers and Digital Techniques, 2000, 147(5): 349–353 https://doi.org/10.1049/ip-cdt:20000743
25
WuW J, WangP J, ZhangX Y.Notice of retraction search for the best polarity of fixed polarity Reed-Muller expression base on QGA. In: Proceedings of the 11th IEEE International Conference on Communication Technology. 2008, 343–346
26
DaiJ, ZhangH H. A novel quantum genetic algorithm for area optimization of FPRM circuits. In: Proceedings of the 3rd International Symposium on Intelligent Information Technology Application. 2009, 408–411 https://doi.org/10.1109/iita.2009.454
27
WangP J, LiH, WangZ H. MPRM expressions minimization based on simulated annealing genetic algorithm. In: Proceedings of the International Conference on Intelligent Systems and Knowledge Engineering. 2010, 261–265 https://doi.org/10.1109/iske.2010.5680868
28
ChaudhuryS, Chattopadhyay S. Output phase assignment for area and power optimization in multi-level multi-output combinational logic circuits. In: Proceedings of the Annual IEEE India Conference. 2006, 1–4 https://doi.org/10.1109/INDCON.2006.302786
29
AlmainiA E A, Mckenzie L. Tabular techniques for generating Kronecker expansions. Computers and Digital Techniques, 1996, 143(4): 205–212 https://doi.org/10.1049/ip-cdt:19960564
30
ZhangH H, WangP J, GuX S. Best polarity searching of FPRM circuits with heuristic technique. Journal of Circuits and Systems, 2009, 14(6): 24–28
31
NguyenH D, Yoshihara I, YamamoriK , YasunagaM. Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on Systems, Man, and Cybernetics, 2007, 37(1): 92–99 https://doi.org/10.1109/TSMCB.2006.880136
32
WangX, LuY, ZhangY. Power optimization in logic synthesis for mixed polarity Reed-Muller logic circuits. The Computer Journal, 2015, 58(6): 1307–1313 https://doi.org/10.1093/comjnl/bxu072
