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
-
改进的制造工艺已实现了原子级尺寸水平的晶体二极管，出现电子间量子效应，这必将导致经典物理失效. 此外，电路规模及集成度的不断提高，使其能耗越来越多，导致芯片过热而影响性能，制约电路集成度的进一步提高. 由Landauer定律[1]可知，集成电路的能耗分为两部分：一部分是由材料的非理性特性引起的，改进制造工艺可以降低；另一部分来自操作过程中遗失的信息，由丢失的信息量决定，即不可逆操作而产生的耗能.
可逆逻辑电路因可逆的逻辑操作，可用于量子逻辑综合，同时又避免了信息的丢失[2-3]，成为解决第二部分耗能的途径. 可逆逻辑综合方法的研究有益于超功耗集成电路及量子计算等领域的发展，已成为全球性研究热点[3-4]. 在电路测试、容错设计等方面，可逆逻辑综合已有相关研究，但如何寻到最优或次优设计电路仍颇具挑战[5]. 利用进化算法求解可逆逻辑综合问题取得了初步成果[6-7]，但多以实现电路功能为目标，电路的实用性不易保证. 为提高电路的实用性，在保证其功能的前提下，以减少垃圾输出、可逆逻辑门数以及量子代价为目标，提出基于协同多目标差分进化算法的可逆逻辑综合方法.
1. 可逆逻辑电路基础
1.1 可逆逻辑门库
可逆逻辑门是组成可逆逻辑电路的基础单元. 任意功能的可逆逻辑电路都可以分解为若干不同的可逆逻辑门，所以进行可逆逻辑电路设计的第一步就是构建门器件库. NOT门、CNOT门和3比特Toffoli门即可组成完备的门库，实现任意可逆逻辑函数. 可逆逻辑综合的优化目标是采用最少的门，以更低的量子代价实现预定功能. 可逆逻辑电路量子代价可以等效为其各组成可逆逻辑门量子代价之和. 综合考虑门库的完备性及量子代价，选取NOT门、CNOT门、Toffoli门、Copy门、和Peres门组成门库.
1.2 门级阵列结构模型及编码
门级阵列结构模型是可逆逻辑电路门级进化设计的专用模型，包含m × n个可逆逻辑门级单元，是一种布线通道阵列，如图1所示. 图中：m为输出/输入线位，输入和输出组合一一对应，确保无扇出禁反馈；n为门级联数. 为实现最优或次优的功能电路，需合理设置这两个参数，否则会对电路规模和门耗等指标产生不利影响. 另外，每个门级单元有T个功能组态（由研究目标设定），门间连接为“有轨级联”.
该模型作为进化个体，对其采用网表级二进制编码方式. 从左到右，对每个门级单元GN排序，其序号设为N（N为整数，
N∈[1,n] ），编码为[RTWN, CWN, EWN].对于门级单元GN：RTWN为当前功能组态；CWN对应控制线位；EWN为受控制线位. 具体表示为：
CWN=[CW1N,CW2N,⋯,CWpN,⋯,CWpmaxN] （1⩽p⩽Pmax ），EWN=[EW1N,EW2N,⋯,EWqN,⋯,EWqmaxN] （1⩽q⩽qmax ）. 其中：CWpN 为门级单元第p个控制线对应的阵列输入线位的序号；EWqN 为所在门级单元第q个被控线对应于阵列中输入线位的序号；Pmax和qmax 分别为门级单元的最大控制线位数和最大被控线位数.对于电路中有些输入为逻辑常量的情况，将这部分常量输入编码为
[CI1,CI2,⋯,CIcn] ；CI cn取值为0或1；cn为常量输入个数.整个可逆逻辑电路的编码按照所有门级单元在阵列模型中的位置将其串联起来，表示为
[CI1,CI2,⋯,CIcn] [RTW1 , CW1 , EW1]···[RTWn , CWn , EWn]，亦为所算法中候选解的表达形式.2. 可逆逻辑综合方法
2.1 适应度函数
可逆逻辑电路设计首先要确保实现预定功能，其次需考虑门数、垃圾输出以及量子代价等指标. 本研究以功能误差、可逆逻辑门数、垃圾输出位和量子代价为目标，分别设置4个适应度函数
fit1 、fit2 、fit3 和fit4 ，对所有适应度函数归一化处理后，可表示为fit1=FIO/TIO (1) fit2=NG/n (2) fit3=GO/m (3) fit4=CQC/(n×GQC) (4) 式中：FIO、TIO、NG、
n 、GO、m 、CQC和GQC分别为错误的输入输出组合数、输入输出组合总数、已用门数、总的门级单元数、垃圾输出数、输入输出总线数、电路量子代价和门单元的最大量子代价. 可逆逻辑电路的设计目标是使4个适应度函数最小化.2.2 协同多目标差分进化算法
差分进化算法是一种简单高效的启发算法，一般针对单目标连续优化问题. 可逆逻辑电路综合属于离散的多目标优化问题. 为求解该类问题，需要改进现有差分进化算法. 自适应种群调整的差分进化（SapsDE）算法[8]在搜索求解的过程中自适应动态调整变异尺度因子、交叉变异概率因子和种群大小等3个主要参数，减少了参数设置对算法效率和效果的不利影响；同时采用两种DE变异策略，可在不同的优化阶段使用不同变异策略，收敛速度较快且求解精度较高. 以此算法为基础，借鉴协同进化思想，采取多种群分工协作处理多目标，提出协同多目标差分进化算法，过程如下.
第一步：初始化. G=0（G为迭代次数），随机生成初始种群，包含N个个体.
第二步：个体适应度评估. 对初始种群内个体离散化处理编码，生成种群PG，并且计算个体对应的子目标适应度函数值.
第三步：建立亚种群. 将种群PG中个体随机分散到4个亚种群PGi（i=0,1,2,3,4）中，每个亚种群对应一个子目标.
第四步：个体进化. 分别对第i个亚种群PGi中个体独立按照SapsDE算法进化指定代数
stmax .第五步：协同进化生成新种群. 将所有亚种群个体返回生成种群PG*，并补全各个体对应的剩余子目标适应度函数值，合并PG和PG*.
第六步：更新种群. 对合并后的种群进行基于拥挤度和分层排序的修剪，得到N个个体的新种群，同时按照SapsDE算法调整种群规模.
第七步：判断是否结束进化.
G=G+stmax ，如果满足终止条件，结束进化；否则，回到第三步，重复执行以上步骤.2.3 修复与化简
种群差分进化时会出现可逆逻辑门线位序号重复使用的情况，比如某线位同时被作为控制线和被控线. 此时，使用前位修复机制来消除该线位复用误差. 规定EWN优先级大于CWN，即EWN中受控线位不变，改变CWN中复用的控制线. 如果线位复用发生在EWN或CWN内部时，则以线位位置前后为序，改变复用线位中位于后面的线位，逐位改变至消除复用.
另外，算法生成的可逆逻辑电路可能会出现冗余门单元，需要利用基于规则的部分变换方法消减：一是消减偶数多个的连续级联且EWN和CWN均一一对应的可逆逻辑门单元；二是消减仅影响电路垃圾输出的可逆逻辑门单元，在算法收敛时，去除未使用的常量输入线和门单元.
2.4 可逆逻辑综合方法的实现
将协同多目标差分进化计算移植到可逆逻辑电路设计领域，形成可逆逻辑综合方法. 通过将逻辑综合问题抽象为带约束的多目标优化问题，利用提出的基于Pareto最优的离散协同多目标差分进化算法对问题进行求解，得到预设功能电路. 具体过程如下：
1）构建完备的可逆逻辑门库；
2）完成门阵列计算模型初始化，确定模型参数；
3）将可逆逻辑综合问题抽象为符合门阵列模型的多目标优化问题，以候选可逆逻辑电路为进化个体，采用二进制编码，以协同多目标差分进化算法为内核，进行电路进化——生成新的子代个体，再进一步修复和化简候选电路个体，生成新的种群；个体适应度评估时，将满足预定功能（即
fit1=0 ）的电路个体存入电路可行解集合C；4）输出优化所得Pareto非占优解集和电路可行解集C中满足预定功能的电路（即其功能误差为0的可逆逻辑电路）.
3. 试验结果与分析
为验证所提方法的有效性，选取可逆逻辑电路测试函数集进行试验分析. 该方法基于以SapsDE为内核的多目标优化算法，故变异比例因子、交叉概率因子均按SapsDE算法设置，其他参数设置见表1. 特别地，对于rd53和ham7电路，算法的最大进化代数增至 2000 ，初始种群规模设为2000 .
表 1 试验参数设定Table 1. Experimental parameters参数 设定值 stmax 3 种群规模下界值 200 种群规模调整因子 1 表越界及停滞临界变量R 4 最大进化代数 500 初始种群规模 500 为验证所提方法的性能，将其针对可逆逻辑电路测试函数集的测试结果，分别与经典可逆逻辑综合方法[9-10]和基于启发式算法的可逆逻辑综合方法[11-12]的优化结果进行对比分析. 采用门数NG、垃圾位NGO和量子代价CQC三个指标描述所设计可逆电路的性能. 比较结果见表2.
表 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)；“—”为对应结果缺失. 本研究算法所获可逆逻辑电路具有一定的优势，证实了所提方法的可行性与有效性. 从三个性能指标上分析，在垃圾位数和门数相同的情况下，本算法获得了更低量子代价的ham3、(1 0 3 2 5 7 4 6)、(7 0 1 2 3 4 5 6)、(0 1 2 3 4 6 5 7)和3_17电路，所得电路结构更简单. 对于4mod5、rd53、ham7三个测试电路，各算法结果在性能指标上各有优劣，总体来讲，本算法所得电路仍具备较小的量子代价，相较表现更优.
以ham3、3_17和ham7三个测试电路为例，结果如图2所示. 本研究算法获得可逆逻辑电路结构简单，性能较为优越.
图 2 本研究算法法实现的部分可逆逻辑电路Figure 2. Part of reversible logic circuits implemented by proposed method4. 结 语
基于协同多目标差分进化算法的可逆逻辑综合方法在进行可逆逻辑电路设计时行之有效且性能优越. 试验结果及分析表明，在人为干预较少的情况下，该方法不仅可以高效地求解预设功能的可逆逻辑电路，而且在一定程度上实现了电路的优化设计. 由于与传统电路设计差别较大，可逆逻辑电路设计缺乏先验知识，进化设计这种不依赖经验的全局优化设计方法，在可逆逻辑综合方面具有较明显的优势和应用前景.
-
图 2 本研究算法法实现的部分可逆逻辑电路
Figure 2. Part of reversible logic circuits implemented by proposed method
表 1 试验参数设定
Table 1. Experimental parameters
参数 设定值 stmax 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. -
下载:
下载:
点击查看大图
计量
- 文章访问数: 190
- HTML全文浏览量: 122
- PDF下载量: 82
- 被引次数: 0
