基于XNOR/OR的FPRM极性优化研究

论文摘要

功耗和面积优化是当前集成电路逻辑层综合设计和优化的一项重要内容。之前的相关研究大都针对Boolean逻辑电路展开,事实上,与之对应的,以XNOR/OR门或XOR/AND门为基本单元的Reed-Muller（RM）逻辑电路在功耗、面积、速度以及可测试性等方面具有巨大的优势。n变量的固定极性RM （FPRM）逻辑函数有2n个繁简不同的逻辑表达式,对应2n个固定极性。可见,极性决定RM逻辑函数的繁简,并进一步影响电路的功耗、面积以及速度,因此有必要深入研究具体目标下RM逻辑电路的最佳极性搜索（亦即极性优化）技术。当前RM逻辑的综合优化主要集中在XOR/AND电路,而对XNOR/OR电路的研究相对较少。鉴此,本文从XNOR/OR电路功耗和面积优化入手,针对当前FPRM逻辑电路极性优化中存在的共性和关键问题进行系统研究,主要研究内容如下：1)极性优化问题的数学模型：针对当前FPRM电路极性优化中的极性评估方法的不足,整理和细化了电路面积和功耗估算方法,并在此基础上建立了以XNOR/OR电路面积最小化、功耗最低化以及电路的面积、功耗综合优化为目标的数学模型。2)面向较大规模电路的极性优化算法：为求解XNOR/OR电路极性优化的数学模型,综合传统遗传算法和量子算法的优势,提出简单并行进化算法（SPEA）;为进一步提高算法的优化性能,将协同进化思想与SPEA算法相结合,提出种群协同进化算法（PCEA）。从改善多峰/多模态/多最优解问题的求解效果出发,针对传统小生境遗传算法要求预知小生境具体信息的不足,提出改进的小生境遗传算法；以进一步提高算法的全局优化能力为目的,引入协同进化思想,提出协同小生境遗传算法（CENGA）。标准函数测试结果分别从不同角度验证了以上两类算法的优化性能。3)极性转换和极性遍历策略：在分析当前常见的几种基于列表技术的极性转换算法基础上,通过综合其中两种极性转换算法的优势,提出XNOR/OR电路不同极性间的并行列表极性转换算法。基准电路的测试结果表明,相比于其它基于列表技术的极性转换算法,该极性转换算法的效率更高；为节省较大规模电路的极性搜索时间,提高电路的整体优化效率,将启发式思想引入优化过程的每一代极性评估过程,提出最少操作极性遍历算法。不同规模基准电路的测试结果表明了该算法的适用范围和效率。4)多输入逻辑门低功耗分解：通过对多输入逻辑门低功耗分解问题以及当前常见的基于分类的多输入门分解算法的深入分析,将多输入门低功耗分解问题转化为最小二叉树寻找问题,根据之前建立的功耗估算模型,以信号概率表示树间距离,并引入贪婪思想,提出通用型多输入门低功耗分解算法（UDMLG）。基准电路测试结果表明了UDMLG的多输入门分解效果以及稳定性。5) XNOR/OR电路功耗优化和面积优化：基于上文研究结果,基于PCEA分别构建XNOR/OR电路低功耗极性优化方案和面积最小化极性优化方案；针对最佳极性不唯一电路,以面积最小化为目标,构建了基于CENGA的多最佳极性XNOR/OR电路极性优化方案,并通过测试数据分析比较算法CENGA对多峰函数和电路极性优化的求解性能,进一步提出改进的协同小生境遗传算法,以改善最佳极性不唯一XNOR/OR电路极性优化的效果。基准电路测试了以上方案的求解效率以及优化效果。6)多目标XNOR/OR电路综合极性优化：以探索XNOR/OR电路多目标优化的最佳极性分布特点为目的,根据XNOR/OR电路综合优化问题的特点改进了多目标遗传混合算法,并基于该算法构建了电路功耗、面积综合优化方案,并基于基准电路测试数据分析了XNOR/OR电路多目标综合优化的最佳极性分布特点和规律。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 电路逻辑综合与功耗分析
• 1.2.1 逻辑综合
• 1.2.2 功耗分析
• 1.3 FPRM电路极性优化研究历史与现状
• 1.3.1 极性转换算法
• 1.3.2 极性评估方案
• 1.3.3 极性优化策略
• 1.4 本文研究内容及章节安排
• 第2章 RM电路极性优化的数学基础
• 2.1 引言
• 2.2 异或和同或运算的定义及性质
• 2.2.1 异或运算的定义和性质
• 2.2.2 同或运算的定义及性质
• 2.2.3 异或和同或之间的换算
• 2.3 函数的RM展开
• 2.3.1 基于XOR/AND运算的RM展开式
• 2.3.2 基于XNOR/OR运算的RM展开式
• 2.4 XNOR/OR电路极性优化
• 2.4.1 XNOR/OR逻辑函数的极性与展开式
• 2.4.2 XNOR/OR电路极性优化的数学模型
• 2.5 本章小结
• 第3章 基于协同进化思想的极性优化算法
• 3.1 引言
• 3.2 种群协同量子遗传算法
• 3.2.1 传统量子算法
• 3.2.2 简单并行进化算法
• 3.2.3 种群协同进化算法
• 3.2.4 算法测试及结果分析
• 3.3 小生境遗传算法及其改进
• 3.3.1 传统小生境遗传算法
• 3.3.2 半径动态调整的小生境遗传算法
• 3.3.3 协同小生境遗传算法
• 3.3.4 算法测试及结果分析
• 3.4 本章小结
• 第4章 XNOR/OR电路极性转换及极性遍历策略
• 4.1 引言
• 4.2 极性转换
• 4.2.1 两种逻辑展开式之间的极性转换
• 4.2.2 不同极性XNOR/OR展开式间的极性转换
• 4.2.3 两种逻辑展开式之间的快速列表极性转换
• 4.2.4 不同极性XNOR/OR展开式间的并行极性转换
• 4.2.5 算法测试和比较
• 4.3 基于列表极性转换算法的极性遍历次序
• 4.3.1 极性遍历次序的最优化数学模型
• 4.3.2 最少操作极性遍历方法
• 4.3.3 极性遍历算法测试及结果分析
• 4.4 本章小结
• 第5章 XNOR/OR电路功耗估算及多输入门低功耗分解
• 5.1 引言
• 5.2 功耗估算方法
• 5.3 多输入门低功耗分解方法
• 5.3.1 基于分类的多输入门分解算法
• 5.3.2 基于贪婪算法的通用型多输入门低功耗分解算法
• 5.3.3 分解算法测试和分析
• 5.4 本章小结
• 第6章 XNOR/OR电路单目标极性优化
• 6.1 引言
• 6.2 XNOR/OR电路低功耗最佳极性搜索
• 6.2.1 XNOR/OR电路低功耗极性优化数学模型
• 6.2.2 基于PCEA算法的低功耗优化方案
• 6.3 XNOR/OR电路面积最小化极性搜索
• 6.3.1 基于PCEA的XNOR/OR电路面积优化方案
• 6.3.2 基于协同小生境遗传算法的XNOR/OR电路面积优化方案
• 6.4 本章小结
• 第7章 XNOR/OR电路综合极性优化
• 7.1 引言
• 7.2 多目标优化
• 7.3 基于目标加权的XNOR/OR电路功耗面积综合优化
• 7.3.1 多目标遗传混合算法
• 7.3.2 XNOR/OR电路功耗面积综合极性优化方案
• 7.4 测试结果及分析
• 7.5 本章小结
• 第8章 总结与展望
• 参考文献
• 致谢
• 攻读博士学位期间完成的学术论文及参与项目情况