进化可逆逻辑电路综合方法研究

发布时间：2020-08-22 08:39

【摘要】：计算机CMOS芯片的热耗散限制了芯片的集成度,而传统逻辑门的不可逆操作是导致能量耗散的主要原因。要避免能量耗散,电路必须由可逆门来构造。因此,可逆电路在可逆计算、低能耗CMOS设计,光计算、量子计算及DNA计算等领域有着广泛的应用,可逆电路综合逐渐成为新的研究热点。已有的可逆电路综合方法基本分为确定性算法、启发式算法和进化类算法。其中,一部分确定性算法能有效地获得可行解,甚至是对中、大规模可逆问题,但获得的解仍需后优化过程进行改进。后优化过程往往需要反复迭代并且作用有限。另一部分确定性算法使用穷尽式搜索方法取得最优解,但只局限于小规模三位、四位可逆电路的综合。启发式方法利用贪婪式启发策略进行解空间的约简,对中小规模电路能够在有限时间内获得有效解,但解仍需优化。进化方法由于具有全局搜索能力,已用于可逆电路综合,但相比较前两类算法,只对小规模、低复杂度可逆函数进行了测试,并没有取得突破性的成果。本文研究利用进化方法进行可逆电路综合,旨在解决穷尽式搜索力所不及的中小规模问题,并在这些问题上能够取得比确定性算法更优的解。可逆电路综合问题可以建模成具有等式约束的最小化问题,其中约束是指电路的误差,目标表示可逆电路的代价。针对可逆电路综合搜索空间巨大、最优解长度不确定、上位性和多峰等特点,主要从变长编码进化、等式约束处理、多样性保持策略、混合进化策略、适应度函数定义等方面入手,对进化可逆电路综合算法设计进行了全面深入的研究,获得了一些关键性的研究成果。主要概括为以下几个方面:(1)设计实现基本变长染色体编码进化算法。改进了约束违反评价函数,利用可逆电路的正极性Reed Muller表达式与恒等函数正极性Reed Muller表达式的差别项数做为评价标准,而不是用传统的矩阵迹距离,因而避免了计算量较大的矩阵积及矩阵克罗内克积的计算;利用从可逆函数的Reed Muller表达式中提取的因子数量信息,正确估计电路的最大长度并进行种群的初始化;采用染色体最大长度限制和无损交叉算子,使染色体长度逐渐增长,防止变长进化中的染色体膨胀。(2)设计了两种等式约束处理方法。第一种方法采用目标和约束分离的机制处理等式约束,对非支配的不可行解,计算节俭压力并与平衡因子比较,根据比较结果完成种群中染色体的排序,将其作为选择的基础。通常,约束违反降低的过程往往伴随着目标值的增加,平衡因子反映了约束违反单位下降所能容忍的目标值增加量,因此能起到防止染色体膨胀的作用。第二种方法采用基于偏好的多目标优化方法来处理约束。通过改进参考点多目标优化算法,根据解的分布动态生成并更新参考点,并定义新的基于距离的比较算子,使得搜索逐步受控地向约束违反减小的方向进行。(3)实现变长染色体编码进化算法的多样性保持机制。由于变长染色体编码进化选择过程中对具有较小约束违反的解的偏好,会使种群逐渐丧失多样性,陷入局部最优,又由于可逆电路综合问题解空间本身具有的多峰特点,进化过程中的多样性保持尤其重要。我们借鉴并改进了子种群探测和种子保留的多样性保持机制,定义了变长染色体之间的距离,增加了子种群的更新机制。实验证明采用该多样性保留机制后,可行解比例和解的质量均有所提高。(4)设计实现混合算法。将进化算法与基于PPRM的启发式算法结合,从当前解的RRPM表达式中提取优选因子构建优选门库,在进化停滞阶段进行个体的更新,从而加快进化算法的收敛速度,提高可行解的比例。(5)将进化可逆逻辑综合研究成果与基于忆阻器蕴含门的逻辑综合问题特点相结合,提出了基于忆阻器蕴含门的逻辑综合进化算法。算法将变长编码进化可逆逻辑综合算法框架用于忆阻器蕴含门的逻辑电路综合问题,提出了忆阻器蕴含门的染色体编码、评价方法及提高可行解率的局部搜索方法,实验证明了算法的有效性。本文对进化可逆逻辑电路综合中的关键性问题进行了有效的探索和尝试,实验结果分析表明本文的方法对中、小规模的可逆标准测试函数具有有效性,达到了预期的设计目的。另外,将进化可逆逻辑电路综合方法应用于基于忆阻器蕴含门的逻辑综合问题,实验结果进一步验证了该方法可以推广到其它变长编码的逻辑电路综合问题。
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP331.1
【图文】：

综合算法,逻辑电路

第一章绪论9图1.2 可逆逻辑电路综合算法比较1.3 论文的研究目的和内容1.3.1 研究目的就上一节所总结的可逆逻辑综合面临的问题，及进化算法所具有的全局并行搜索和根据适应度函数定义的不同优化不同指标的特点，本研究的目的就是针对可逆逻辑综合问题大搜索空间、最优解编码长度未知、必须满足等式约束等特点，设计专门的进化算法及进化、启发式方法相结合的算法，在不引入多余输入线的前提下，降低4-bit 及 4-bit 以上中小规模可逆电路的量子代价，设计可逆综合多目标优化算法，取得多个优化指标的平衡。另外，由于除了可逆电路逻辑综合问题外，大部分电路逻辑综合问题都具有最优解长度未知，需要满足等式约束等特点，因此，得出能够借鉴推广、并有效解决具有上述特点的一类逻辑综合问题的进化算法或混合算法

二叉决策图,可逆函数

数的节点数量，但二叉决策图的变形形式能够用多项式的节点数量来表示许多实际函数。函数 3_17 的二叉决策图如图 2.1 所示。图2.1 可逆函数 3_17 的二叉决策图表示不相交循环表示。循环置换是置换的另一种表达形式，它以发生变化的文字的变化次序为序，表达成轮换的形式。如：可逆函数 3_17 的置换过程为0 7 5 2 4 0，其余元素 1，3，6 不变，因此可以表示成 8 元素的循环置换 0 7 5 2 4 。一般每个循环的表达方法不唯一，习惯上总是将循环置换中出现的最小文字置首位。对于长度大于 2 的循环

可逆电路,真值表,可逆函数

西安电子科技大学博士学位论文16图2.2 可逆电路输入输出结构图表2.1 逻辑与运算可逆真值表z y x f1f2f30 0 0 0 0 00 1 0 0 1 00 0 1 0 0 10 1 1 1 1 11 0 0 1 0 01 1 0 1 1 01 0 1 1 0 11 1 1 0 1 1图 2.3 显示了其对应的可逆规范真值表。其中阴影部分为原不可逆规范，z 为常量输入位，2f ,3f 为垃圾输出位,满足2f y，3f x，1f z xy。当电路输入端给 z赋值为 0 时，在输出端1f 总能获得 x 与 y 逻辑与运算的结果。2.1.3 可逆门可逆门 g 实现可逆函数，门 g-1能够实现逆变换。基本可逆门定义如下，符号表示和矩阵规范见表 2.1。定义 2.3 设1 2 nX { x , x , , x} 是域变量集合。通用 Toffoli 门 GT[1]记为 TOF( C；t )

【相似文献】