Reversible logic synthesis algorithmbased on cooperative multi-objective differential evolution
-
摘要: 可逆逻辑电路可避免因信息丢失而产生的热耗散，从而有望解决集成电路热耗问题. 将可逆逻辑电路设计问题抽象为带有强约束的多目标优化问题，提出以协同多目标差分进化算法为核心的可逆逻辑综合方法. 该方法基于种群自适应调节的差分进化算法，结合协同进化的多种群策略优化多目标，经种群选择及自适应调节策略和Paroto最优评估评价更新候选个体. 通过求解经典电路测试集，验证了所提方法的可行性及有效性. 与经典及基于启发式算法的可逆逻辑综合方法相比，该方法生成的电路性能更优.Abstract: Reversible logic circuits can avoid thermal dissipation due to information loss so that it is possible to solve the thermal dissipation problem of integrated circuits. As reversible logic circuit synthesis problem was modeled as a multi-objective optimization problem, a reversible logic synthesis method was proposed based on a cooperative multi-objective differential evolution algorithm. Differential evolution algorithm with self-adaptive population resizing mechanism (SapsDE) was adopted as the basis and combined with the co-evolution algorithm based multiple population strategy for multiple objectives. Meanwhile, the population updating scheme and the fitness evaluation strategy based on Pareto-optimal were employed to update the candidate individuals. The synthesis method tested on a suite of benchmark functions is feasible and effective. Compared with classical and heuristic synthesis methods, the circuits generated by the proposed synthesis method have better performance.
-
Key words:
- reversible logic circuit /
- differential evolution (DE) /
- co-evolution /
- multi-objective
-
图 2 本研究算法法实现的部分可逆逻辑电路
Figure 2. Part of reversible logic circuits implemented by proposed method
表 1 试验参数设定
Table 1. Experimental parameters
参数 设定值 ${{\rm{st}}}_{{\rm{max}}}$ 3 种群规模下界值 200 种群规模调整因子 1 表越界及停滞临界变量R 4 最大进化代数 500 初始种群规模 500 
下载: 导出CSV
表 2 各算法试验结果比较
Table 2. Comparison of results by algorithms
测试电路 本研究算法 文献[9]算法 文献[10]算法 文献[11]算法 文献[12]算法 NGO NG CQC NGO NG CQC NGO NG CQC NGO NG CQC NGO NG CQC ham3 0 5 7 0 5 7 0 5 9 — 5 9 — 5 9 f1 0 4 8 — — — 0 4 16 — 4 8 — 4 16 f2 0 3 5 — — — 0 3 7 — 3 7 — 3 7 f3 0 3 7 — — — 0 3 15 — 3 7 — 3 15 3_17 0 6 12 0 6 12 0 6 14 — 6 14 — 6 14 rd32 2 4 8 — — — 2 4 8 — — — — — — Xor5 4 4 4 — — — 4 4 4 — — — — — — 4mod5 4 5 7 4 8 24 4 5 13 — 5 13 — 5 55 rd53 5 12 36 4 12 132 4 13 116 — — — — — — ham7 0 25 47 0 23 81 0 24 68 — — — — — — 注：f1、f2和f3分别为测试电路(1 0 3 2 5 7 4 6)、(7 0 1 2 3 4 5 6)、(0 1 2 3 4 6 5 7)；“—”为对应结果缺失.
下载: 导出CSV
-
[1] LANDAUER R. Irreversibility and heat generation in the computing process[J] . IBM Journal of Research and Development,1961,5(3):183 − 191. doi: 10.1147/rd.53.0183 [2] STORME L, DE A, JACOBS G. Group theoretical aspects of reversible logic gates[J] . Journal of Universal Computer Science,1999,5(5):307 − 321. [3] SAMRIN S, PATIL, R, ITAGI S, et al. Design of logic gates using reversible gates with reduced quantum cost[J] . Global Transitions Proceedings,2022,3(1):136 − 141. doi: 10.1016/j.gltp.2022.04.011 [4] 吴钰, 张莹, 王伦耀, 等. 一种可逆有限状态机的电路设计[J] . 电子学报,2020,48(11):2226 − 2232. doi: 10.3969/j.issn.0372-2112.2020.11.019 [5] KEMTOPF P, PERKOWSK M, PODLASKI K. Synthesis of reversible circuits: A view on the state-of-the-art [C]//Proceedings of the 12th IEEE International Conference on Nanotechnology (IEEE-NANO). Birmingham: IEEE, 2012: 1-6. [6] DRECHSLER R, FINDER A, WILLE R. Improving esop-based synthesis of reversible logic using evolutionary algorithms[C]//Proceedings of European Conference on the Applications of Evolutionary Computation. Berlin: Springer, 2011: 151-161. [7] 胡江, 张巧文, 王阳. 基于改进遗传算法的量子可逆电路综合[J] . 量子电子学报,2017,34(2):196 − 202. [8] WANG X, ZHAO S G. Differential evolution algorithm with self-adaptive population resizing mechanism[J] . Mathematical Problems in Engineering,2013,2013:419372 − 85. doi: 10.1155/2013/419372 [9] MASLOV D, DUECK G, MILLER D. Toffoli network synthesis with templates[J] . IEEE Transon Circuits and Systems,2005,24(6):807 − 817. doi: 10.1109/TCAD.2005.847911 [10] GUPTA P, AGRAWAL A, JHA J N. An algorithm for synthesis of reversible logic circuits[J] . IEEE Transactions on CAD,2006,25(11):807 − 816. doi: 10.1109/TCAD.2006.871622 [11] DATTA K, RATHI G, SENGUPTA I, et al. Synthesis of reversible circuits using heuristic search method[C]//Proceedings of the 25th International Conference on VLSI Design. Hyderabad: IEEE, 2012: 328−333. [12] DATTA K, SENGUPTA I, RAHAMAN H. Reversible circuit synthesis using evolutionary algorithm [C]//Proceedings of the 5th International Conference on Computers and Devices for Communication(CODEC). Kolkata: IEEE, 2012: 1−4. -
下载:
点击查看大图
图(2) / 表(2)
计量
- 文章访问数: 122
- HTML全文浏览量: 77
- PDF下载量: 35
- 被引次数: 0
