# An Efficient Polarity Optimization Approach for Fixed Polarity Reed-Muller Logic Circuits Based on Novel Binary Differential Evolution Algorithm

Zhenxue He, Guangjun Qin, Limin Xiao, Fei Gu, Zhisheng Huo, Li Ruan, Haitao Wang, Longbing Zhang, Jianbin Liu, Shaobo Liu, et al.

<figure><img src="image_1.png" /></figure>

## To cite this version:

Zhenxue He, Guangjun Qin, Limin Xiao, Fei Gu, Zhisheng Huo, et al., An Efficient Polarity Optimization Approach for Fixed Polarity Reed-Muller Logic Circuits Based on Novel Binary Differential Evolution Algorithm. 14th IFIP International Conference on Network and Parallel Computing (NPC), Oct 2017, Hefei, China. pp.118-121, 10.1007/978-3-319-68210-5_11. hal-01705436

HAL Id: hal-01705436

https://inria.hal.science/hal-01705436

Submitted on 9 Feb 2018

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Efficient Polarity Optimization Approach for Fixed Polarity Reed-Muller Logic Circuits Based on Novel Binary Differential Evolution Algorithm

Zhenxue He¹,², Guangjun Qin³, Limin Xiao¹,², Fei Gu², Zhisheng Huo¹,², Li Ruan¹,², Haitao Wang⁴, Longbing Zhang⁵, Jianbin Liu⁴, Shaobo Liu⁴, and Xiang Wang³

¹ State Key Laboratory of Software Development Environment, Beihang University, 100191 Beijing, China

² School of Computer Science and Engineering, Beihang University, 100191 Beijing, China

³ School of Electronic and Information Engineering, Beihang University, 100191 Beijing, China

⁴ Space Star Technology Co., Ltd, 100086 Beijing, China

⁵ State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, 100190 Beijing, China
{hezhenxue, xiaolm}@buaa.edu.cn

**Abstract.** The bottleneck of integrated circuit design could potentially be alleviated by using Reed-Muller (RM) logic circuits due to their remarkable superiority in power, area and testability. In this paper, we propose a Novel Binary Differential Evolution (DE) algorithm (NBDE) to solve the discrete binary-encoded combination optimization problem. Moreover, based on the NBDE, we propose an Efficient Polarity Optimization Approach (EPOA) for Fixed Polarity RM (FPRM) logic circuits, which uses the NBDE to search the best polarity under a performance constraint. To the best of our knowledge, we are the first to use DE to optimize RM circuits. The experimental results on 24 MCNC benchmark circuits show the effectiveness and superiority of EPOA.

## 1 Introduction

Traditional IC design based on the Boolean logic is facing serious power, area and delay challenges. Plenty of studies (e.g., [1-4]) demonstrate that compared with the circuits implemented by Boolean logic, the circuits implemented by RM logic are capable of achieving lower power and area. However, the existing polarity optimization approaches, which are based on GA or its variants, have a low convergence speed or are easily trapped into the local optimal solution [5-6].

In this paper, we propose a binary version of the Differential Evolution (DE) algorithm according to the polarity characteristic of FPRM logic circuits, called Novel Binary Differential Evolution algorithm (NBDE), to find the optimal solution in binary optimization space. Moreover, based on the NBDE, we propose an Efficient Polarity Optimization Approach (EPOA) for FPRM logic circuits, which uses the NBDE to search the best polarity.
# 2 An Efficient Polarity Optimization Approach for FPRM Logic Circuits

To enhance the global convergence ability, we introduce the elitism strategy to the NBDE. In addition, we propose a binary random mutation operator to increase the population diversity and improve the global searching ability.

## 2.1 Population Initialization

Firstly, a random number $r$ is generated in [0,1]. Then, the $j$-th element of $i$-th individual $x_{ij}$ is set to 1 (which represents polarity 1) if $r$ is less than 1/2; otherwise, $x_{ij}$ is set to 0 (which represents polarity 0).

## 2.2 Mutation Operator

To avoid the premature convergence and increase the population diversity, we propose a binary random mutation operator, which is represented as follows:

$$v_{i,j} = \begin{cases} x_{i,j} + (-1)^{n_{i,j}} \cdot |x_{r_{2,j},j} - x_{r_{3,j},j}|, & \text{rand} \ge 0.5 \\ x_{best,j} + (-1)^{n_{best,j}} \cdot |x_{r_{2,j},j} - x_{r_{3,j},j}|, & \text{rand} < 0.5 \end{cases} \quad (1)$$

where $v_{i,j}$ represents the $j$-th element of mutation vector $v_i$, $r_{2,j}, r_{3,j} \in \{1, 2, ..., NP\}$ and $r_{2,j} \neq r_{3,j} \neq i$. $x_{best}$ is the optimal individual in current population, and $rand$ is a random number in [0,1].

Since the polarity of FPRM expression is taken as 0 or 1, the absolute value of difference vector is only 0 or 1 and the mutated variable is still 0-1 variable. Therefore, the mutation operator satisfies the closure. Moreover, whether one dimension variable can be mutated or not depends on the difference vector. Specifically, the $x_{i,j}$ or $x_{best,j}$ can be mutated (from 0 to 1 or from 1 to 0) when $|x_{r_{2,j}} - x_{r_{3,j}}| = 1$, which could increase the population diversity, improve the global searching ability and prevent the algorithm trapping into the local optimal solution. In addition, the probability of $x_{r_{2,j}}$ is equal to $x_{r_{3,j}}$ is increasing along with the population evolution. The $x_{i,j}$ or $x_{best,j}$ remain the same when $|x_{r_{2,j}} - x_{r_{3,j}}| = 0$, which could accelerate the convergence speed.

# 3 Experiments Results

The EPOA has been implemented in C and compiled by the GNU C complier. The results were obtained by using a PC with Intel Core i7 3.40GHz with 4G RAM under Linux. In this paper, we set the logic minimization as the polarity optimization goal to validate the effectiveness of the EPOA.

We compared the EPOA with the GA based Polarity Optimization approach (GAPO) [7] and Whole Annealing GA based Polarity Optimization approach (WAGAPO) [8] on 24 randomly selected MCNC benchmark circuits. Moreover, we
ran the GAPO, WAGAPO and EPOA 10 times on each circuit to reduce the impact of randomness on the results. The population size is set to 100, and termination criterion is that there is no improvement on the optimal solution in population over 10 iterations.

The comparison of GAPO, WAGAPO and EPOA on the average number of iterations and run time (in CPU seconds) over 10 independent runs are listed in Table 1. Columns 9 and 10 denote the percentage of the number of iterations and run time saved by EPOA compared to GAPO. Columns 11 and 12 denote the percentage of the number of iterations and run time saved by EPOA compared to WAGAPO.

<table><caption>**Table 1.** Comparison of GAPO, WAGAPO and EPOA on the average number of iterations and run time</caption><thead><tr><th rowspan="2">Name</th><th rowspan="2">Input</th><th colspan="2">GAPO</th><th colspan="2">WAGAPO</th><th colspan="2">EPOA</th><th colspan="2">Save1(%)</th><th colspan="2">Save2(%)</th></tr><tr><th>iter</th><th>time(s)</th><th>iter</th><th>time(s)</th><th>iter</th><th>time(s)</th><th>iter</th><th>time(s)</th><th>iter</th><th>time(s)</th></tr></thead><tbody><tr><td>b3</td><td>3</td><td>1</td><td>0.20</td><td>1</td><td>0.18</td><td>1</td><td>0.03</td><td>0.00</td><td>85.00</td><td>0.00</td><td>83.33</td></tr><tr><td>xor3</td><td>3</td><td>1</td><td>0.19</td><td>1</td><td>0.18</td><td>1</td><td>0.05</td><td>0.00</td><td>73.68</td><td>0.00</td><td>72.22</td></tr><tr><td>bw</td><td>5</td><td>6</td><td>0.96</td><td>3</td><td>0.42</td><td>1</td><td>0.06</td><td>83.33</td><td>93.75</td><td>66.67</td><td>85.71</td></tr><tr><td>xor5</td><td>5</td><td>8</td><td>0.82</td><td>4</td><td>0.57</td><td>1</td><td>0.05</td><td>87.50</td><td>93.90</td><td>75.00</td><td>91.23</td></tr><tr><td>m1</td><td>6</td><td>12</td><td>1.18</td><td>4</td><td>0.61</td><td>1</td><td>0.06</td><td>91.67</td><td>94.92</td><td>75.00</td><td>90.16</td></tr><tr><td>Z5xp1</td><td>7</td><td>12</td><td>1.22</td><td>5</td><td>0.63</td><td>1</td><td>0.06</td><td>91.67</td><td>95.08</td><td>80.00</td><td>90.48</td></tr><tr><td>lin</td><td>7</td><td>14</td><td>7.34</td><td>6</td><td>3.70</td><td>1</td><td>0.14</td><td>92.86</td><td>98.09</td><td>83.33</td><td>96.22</td></tr><tr><td>ex5</td><td>8</td><td>15</td><td>2.85</td><td>8</td><td>1.44</td><td>2</td><td>0.37</td><td>86.67</td><td>87.02</td><td>75.00</td><td>74.31</td></tr><tr><td>m3</td><td>8</td><td>14</td><td>2.21</td><td>6</td><td>1.28</td><td>3</td><td>0.55</td><td>78.57</td><td>75.11</td><td>50.00</td><td>57.03</td></tr><tr><td>rd84</td><td>8</td><td>22</td><td>14.92</td><td>7</td><td>5.62</td><td>4</td><td>0.62</td><td>81.82</td><td>95.84</td><td>42.86</td><td>88.97</td></tr><tr><td>1020</td><td>10</td><td>24</td><td>23.03</td><td>9</td><td>7.76</td><td>6</td><td>4.60</td><td>75.00</td><td>80.03</td><td>33.33</td><td>40.72</td></tr><tr><td>ex1010</td><td>10</td><td>20</td><td>15.78</td><td>12</td><td>6.14</td><td>7</td><td>4.81</td><td>65.00</td><td>69.52</td><td>41.67</td><td>21.66</td></tr><tr><td>br1</td><td>12</td><td>31</td><td>17.02</td><td>16</td><td>9.37</td><td>8</td><td>3.44</td><td>74.19</td><td>79.79</td><td>50.00</td><td>63.29</td></tr><tr><td>14_4color</td><td>14</td><td>55</td><td>30.08</td><td>23</td><td>15.26</td><td>10</td><td>7.05</td><td>81.82</td><td>76.56</td><td>56.52</td><td>53.80</td></tr><tr><td>table3</td><td>14</td><td>70</td><td>37.40</td><td>27</td><td>18.70</td><td>18</td><td>11.62</td><td>74.29</td><td>68.93</td><td>33.33</td><td>37.86</td></tr><tr><td>dk48</td><td>15</td><td>62</td><td>36.32</td><td>26</td><td>16.43</td><td>20</td><td>9.59</td><td>67.74</td><td>73.60</td><td>23.08</td><td>41.63</td></tr><tr><td>alcom</td><td>16</td><td>69</td><td>67.85</td><td>31</td><td>34.41</td><td>23</td><td>17.53</td><td>66.67</td><td>74.16</td><td>25.81</td><td>49.06</td></tr><tr><td>table5</td><td>17</td><td>81</td><td>84.99</td><td>52</td><td>52.90</td><td>31</td><td>22.42</td><td>61.73</td><td>73.62</td><td>40.38</td><td>57.62</td></tr><tr><td>src1</td><td>18</td><td>73</td><td>173.55</td><td>37</td><td>139.34</td><td>29</td><td>54.63</td><td>60.27</td><td>68.52</td><td>21.62</td><td>60.79</td></tr><tr><td>in2</td><td>19</td><td>84</td><td>158.64</td><td>41</td><td>127.88</td><td>33</td><td>32.26</td><td>60.71</td><td>79.66</td><td>19.51</td><td>74.77</td></tr><tr><td>mark1</td><td>20</td><td>127</td><td>240.91</td><td>40</td><td>195.61</td><td>30</td><td>60.75</td><td>76.38</td><td>74.78</td><td>25.00</td><td>68.94</td></tr><tr><td>mux</td><td>21</td><td>95</td><td>226.33</td><td>34</td><td>174.26</td><td>27</td><td>68.90</td><td>71.58</td><td>69.56</td><td>20.59</td><td>60.46</td></tr><tr><td>duke2</td><td>22</td><td>116</td><td>262.72</td><td>45</td><td>223.15</td><td>34</td><td>75.18</td><td>70.69</td><td>71.38</td><td>24.44</td><td>66.31</td></tr><tr><td>cordic</td><td>23</td><td>145</td><td>318.05</td><td>67</td><td>257.18</td><td>42</td><td>95.84</td><td>71.03</td><td>69.87</td><td>37.31</td><td>62.73</td></tr></tbody></table>

Compared with the GAPO, the greatest improvement in the number of iterations and run time, which were made by EPOA, are 92.86% and 98.09%, respectively.
Moreover, compared with the WAGAPO, the greatest improvement in the number of iterations and run time, which were made by EPOA, are 83.33% and 96.22%, respectively.

## 4 Conclusion

In this paper, we propose a novel binary DE algorithm, called NBDE, which can solve the binary-encoded combination optimization problem. Additionally, based on the NBDE, we propose a polarity optimization approach, called EPOA, which uses the NBDE to search the best polarity of FPRM logic circuits. The experimental results over MCNC benchmark circuits show that the EPOA performs better than, or at least comparable to, the existing GA or its variants based polarity optimization approaches in terms of solution accuracy and convergence speed.

**Acknowledgments.** This work is supported by the National Natural Science Foundation of China (Nos. 61370059 and 61232009), Beijing Natural Science Foundation (No. 4152030), Fundamental Research Funds for the Central Universities (YWF-14-JSJXY-14), the fund of the State Key Laboratory of Computer Architecture (CARCH201507), the State Administration of Science Technology and Industry for National Defense, the major projects of high resolution earth observation system (Y20A-E03), and the fund of the State Key Laboratory of Software Development Environment (SKLSDE-2016ZX-15).

## References

1. He, Z X., Xiao, L M., Ruan, L.: A Power and Area Optimization Approach for Mixed Polarity Reed-Muller Expressions for Incompletely Specified Boolean Functions. Journal of Computer Science and Technology, vol.32, no.2, (2017) 297-311

2. Ma, X J., Li, Q Y., Zhang, J L., Xia, Y S.: Power Optimization Technique Based on Dual-logic Diagram Expression at Gate Level. Journal of Computer-Aided Design & Computer Graphics, vol.29, no.3, (2017) 509-518

3. He, Z X., Xiao, L M., Gu F.: An Efficient and Fast Polarity Optimization Approach for Mixed Polarity Reed-Muller Logic Circuits. Frontiers of Computer Science, (2017) 1-15

4. Rahaman, H., Mathew, J., Pradhan, D K.: Secure Testable S-box Architecture for Cryptographic Hardware Implementation. Computer Journal, vol.53, no.5, (2010) 581-591

5. Wang, P J., Wang, D S., Jiang, Z D.: Area and Power Optimization of ISFPRM Circuits Based on PSGA Algorithm. ACTA ELECTRONICA SINICA, vol.41, no.8, (2013) 1542-1548

6. He, Z X., Xiao, L M., Zhang L B.: EMA-FPRMs: An efficient minimization algorithm for fixed polarity Reed-Muller expressions. International Conference on Field-Programmable Technology, (2016) 253-256

7. Sun, F., Wang, P J., Yu, H Z.: Ternary FPRM Circuit Area Optimization Based on Genetic Algorithm. Journal of Shandong University (Natural Science), vol.48, no.5, (2013) 51-56

8. Yang, M., Almaini, A.E.A.: Optimization of Mixed Polarity Reed-Muller Functions Based on Whole Annealing Genetic Algorithm. Journal of Fudan University (Natural Science), vol.52, no.3, (2013) 303-308