基于矩阵表示的CMOL电路容错映射

针对存在缺陷的CMOS/纳米分子混合(CMOS/nanowire/MOLeclular hybrid, CMOL)电路的单元容错映射问题, 提出一种基于矩阵表示的CMOL电路容错映射方法. 首先, 将逻辑电路和CMOL电路建模为矩阵表示; 然后采用文化基因(memetic)算法进行矩阵间可匹配字符的搜索, 采用小矩阵元值优先匹配的策略完成单元缺陷容忍映射. ISCAS测试电路的实验结果表明, 与已有方法相比, 本文方法在求解速度上有36.98%的提升.     

逻辑函数高阶布尔e偏导数求解算法的实现

针对已有方法在求解布尔e偏导数时只能解决小规模电路的问题,提出了一种基于逻辑函数不相交运算的大函数高阶布尔e偏导数的求解算法.该方法将逻辑函数转化为不相交乘积项的集合,用逻辑函数的不相交运算替代布尔e导数运算中的逻辑“与”运算;并将不包含待求导变量的乘积项拆分出来,不参与布尔e导数运算,以达到降低算法复杂度、提高算法速度的目的.提出的算法用C语言编程实现,并用MCNC测试电路进行了测试.实验结果显示,本算法能快速实现大函数高阶布尔e偏导数的求解,求解效率与参与不相交运算的乘积项数量有关,但对输入变量的数量不敏感.     

基于Majority逻辑门映射的电路面积优化

提出了一种采用三输入Majority逻辑门(M门)和反相器实现电路逻辑功能的电路面积优化算法.该算法首先用动态规划策略完成电路的AIG(And-Inverter Graph)切割,然后通过搜索适合M门覆盖的AIG子结构以及与门和M门之间的等效替代,将AIG转换为适合M门映射的MIG(Majority-Inverter Graph),最后用Ω法则和Ψ法则对MIG进行简化,得到节点数更少的MIG,从而实现基于M门映射的电路面积优化.优化算法用C语言实现,并用MCNC电路测试.结果表明,相比于逻辑综合工具ABC的结果,用M门映射后电路面积可得到平均约12%左右的优化.     

基于逻辑复合门映射的电路面积优化

提出了一种基于复合门映射的电路面积优化方法.该方法首先通过BDD结构的拆分将待优化的逻辑电路转化为由二输入基本逻辑门组成的多级逻辑网络,然后利用复合门搜索和等效转换算法将逻辑网络中适合复合门实现的子结构用相应的复合门替换.提出的优化算法用C语言编程实现,并用MCNC电路进行了测试.测试结果表明,相比于ABC和BDS软件结果,经算法优化后,电路的节点数可分别减少约37%和29%.     

考虑缓冲时间的受扰航班恢复问题建模与求解

在制定受扰航班恢复计划时,为航班设置缓冲时间,可有效减少航班实际执行时的延误传播。研究考虑缓冲时间的受扰航班恢复问题,以恢复成本最小化为目标建立混合整数规划模型和集合划分模型。采用改进分支定价算法求解,并应用两种加速策略加快算法的求解。小规模算例的求解与CPLEX优化软件进行对比,验证了模型和算法的有效性,大规模算例实验表明了改进分支定价算法的高效性。使用加速策略使得算法的平均求解时间由937.63 s降到185.22 s,平均效率提高80.25%。     

基于树形Mux的逻辑电路优化

为实现用case语句描述的逻辑电路的面积和延迟优化,提出了一种基于树形Mux的逻辑电路优化方法.该方法先将case语句转换为树形Mux,通过合并case语句实现Mux树中Mux门的个数和层级减少,并通过化简地址逻辑实现地址再编码电路的精简,进而实现映射后电路面积与延迟的优化.提出的算法使用C++语言实现,电路面积和延迟优化结果由常用学术开源EDA工具abc,结合国内EDA公司提供的映射库得到.实验结果表明,相比于abc工具,使用该方法得到的面积和延迟优化分别提升了26%和21%.     

基于可满足性模理论的CMOL电路单元映射

针对纳米CMOS混合电路(CMOL)单元映射时, 传统的精确算法存在编码变量多、文件存储大导致的求解规模受限问题, 提出了一种基于可满足性模理论(SMT)的CMOL电路单元映射方法, 该方法通过整型编码减小文件存储大小, 通过渐进式求解算法兼顾求解规模和速度. 实验结果表明, 与传统的精确算法相比, 本文提出的方法可大幅减少中间处理文件的大小, 并以较小的求解速度为代价提高了处理大规模电路的能力.     

基于近似逻辑的不完全指定FPRM函数的功耗优化

基于精确逻辑的逻辑综合和优化方法已有广泛的研究. 但有时并非需要精确逻辑, 从而可利用这种特性进行关键指标的综合和优化. 本文提出了基于近似逻辑的不完全指定固定极性Reed-Muller (Incompletely Specified Fixed Polarity RM, ISFPRM)逻辑函数的逻辑优化方法. 首先建立基于二级逻辑的功耗估算模型和近似电路的设计效能评估模型, 然后提出基于近似逻辑的ISFPRM函数的优化算法, 并用遗传算法加以实现. 所提算法应用于MCNC标准电路进行测试, 结果表明在一定的面积约束下, 电路每增加1%的误差率获得12%~18%的功耗优化     

一种求解混合整数非线性规划问题的演化算法--搜索空间自动收缩法

提出一种求解混合整数非线性规划问题的新的演化算法 -搜索空间自动收缩法 (ACSSOS) .在这种算法中 ,演化算法既用来定位最优解区域 ,实现搜索空间自动向全局最优解收缩 ,又用来最终求得最优解 .由于在遗传算子中引用了舍入操作 ,它不仅可用来求解混合非线性整数规划问题 ,也可求解纯整型或纯实型变量非线性函数优化问题 .数值试验结果表明本文的算法在解的质量、稳定性和收敛速度等方面优于一般的演化算法 .     

基于DNSGA-Ⅱ算法的三值FPRM电路面积与功耗优化

针对三值FPRM电路面积与功耗综合优化问题,提出一种基于差分非支配排序遗传算法(Differential Non-dominated Sort Genetic Algorithm Ⅱ,DNSGA-Ⅱ)的最佳极性搜索方案.首先在DNSGA-Ⅱ算法中,随机抽取种群个体进行高斯变异而产生变异群体.从Pareto非劣解集和变异群体中抽取父代进行二项式交叉产生子代群体,从而维持算法的多样性.然后,结合DNSGA-Ⅱ算法与三值FPRM电路极性转换技术和低功耗技术,搜索电路面积与功耗的最佳极性.最后对MCNC Benchmark电路进行测试,与GA和NSGA-Ⅱ算法搜索到的结果相比,DNSGA-Ⅱ算法获取的最佳极性电路功耗平均减小19.53%和15.08%,面积平均节省9.01%和6.05%.     

自适应memetic算法求解集合覆盖问题

集合覆盖问题是一个经典的NP困难的组合优化问题,有着广泛的应用背景.首先,采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后,基于集合覆盖问题的结构特征,设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略,提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法,并将其结果与现有遗传算法进行了比较,表明该算法能够在可接受的时间内找到高质量的解,能够有效求解大规模集合覆盖问题.     

基于SMPSO算法的三值FPRM电路延时优化

n输入变量的三值FPRM电路存在3n个不同极性及其对应的函数展开式. 通过对三值列表转换技术以及三值FPRM逻辑表达式的研究, 并结合自适应变异粒子群算法提出一种三值FPRM电路延时优化解决方案. 首先根据三值FPRM逻辑表达式的特征建立延时估计模型; 然后结合三值列表转换技术和SMPSO算法, 对三值FPRM电路延时进行优化; 最后采用PLA格式的MCNC Benchmark电路进行算法测试. 结果表明: SMPSO算法相比于穷尽算法的优化效果更佳, 电路的延时和面积平均节省11.6%和18.6%.     

三值FPRM电路极性间转换算法及其在面积优化中的应用

通过对三值FPRM(Fixed-polarity Reed-Muller)展开式和四值列表技术的研究,提出了一种三值FPRM电路极性间转换算法,并将其应用于电路面积优化.首先根据四值RM(Reed Muller)逻辑多项式系数的计算方法,推导出三值FPRM展开式极性间系数转换算法;然后利用该算法,结合三值模代数特点以及电路面积估计模型,沿非循环格雷码极性遍历路径进行三值FPRM电路面积最佳极性搜索,得到面积最优的FPRM电路.最后对8个MCNC基准电路进行测试,结果表明：与0极性Reed-Muller电路相比,三值FPRM电路的面积平均减少56.2%.     

基于AIG的多级逻辑电路延迟近似优化

在对多级逻辑电路延迟进行优化中,提出了一种针对关键路径中节点输出的近似替换方法,用于实现延迟优化.提出的算法先建立待优化电路的关键路径集合,然后通过选取每一条关键路径中错误率影响最小的节点构成待优化节点集,再结合提出的节点输出近似替换技术,在错误率约束下实现节点删除和关键路径压缩,进而达到多级逻辑电路延迟优化.提出的算法用C++和ABC工具内置命令编程实现,使用ISCAS85以及LGSynth91电路进行测试.实验结果显示,与已提出的常量替换方法相比,面积和延迟优化效果分别提升22.96%和31.49%.同时相较于最新提出的针对延迟优化的算法,在延迟优化效果相近的情况下,算法运行时间上有61.88%的提升.     

基于近似计算技术的FPRM逻辑功耗优化

提出了一种基于近似计算技术的FPRM逻辑功耗优化的算法, 该算法包括基于信号概率和跳变密度的固定极性Reed-Muller(Fixed Polarity Reed-Muller, FPRM)函数动态功耗模型, 基于遗传算法的以功耗优化为导向的RM逻辑极性搜索方法, 以及利用双锐积运算的RM逻辑错误率计算方法. 在错误率的约束下, 通过有选择性地删减部分乘积项, 实现功耗优化. 提出的算法用C语言实现, 并用MCNC Benchmark电路测试. 结果表明: 与原始FPRM电路功耗相比, 在平均错误率为3.21％时, 电路动态功耗平均减少了22.77％.     

生物地理学优化算法中基于Zoutendijk可行方向法的变异算子设计

根据约束优化问题的全局收敛性要求,基于传统优化与智能优化,设计了一种基于Zoutendijk可行方向法的新型变异算子,并将其应用于生物地理学优化算法,构建了一种用混合优化算法求解优化问题的方法.通过算子设计策略的理论验证、智能算法的收敛性分析及6个不同类型算例的仿真试验,证明此自适应求解优化问题机制具有实效性.     

基于动态分级和邻域反向学习的改进粒子群算法

针对粒子群算法容易陷入局部最优解的问题,提出了一种基于动态分级和邻域反向学习的改进粒子群算法.该算法通过构建动态分级机制,将种群中的粒子动态地划分成3个等级,对不同等级内的粒子采取不同的扰动行为,使得粒子在增强种群多样性的同时保持向全局最优方向进化;采用粒子智能更新方式,提高了粒子的搜索能力;引入动态邻域反向学习点建立全局搜索策略,促使种群快速寻优.最后,利用多种典型测试函数对该算法进行仿真实验,结果表明,与其他几种优化算法相比,本算法具有较好的收敛性和稳定性.     

高阶常微分方程的动态演化建模

提出了采用高阶常微分方程模型代替传统时序分析中所用的ARMA模型来实现一维时间序列的建模和预报．设计的将遗传程序设计与遗传算法相嵌套的动态演化建模算法,用遗传程序设计优化模型结构,以遗传算法优化模型参数,边收集数据边建模边预报,首次成功地实现了时间序列实时预报的程序自动化．两个时间序列的应用实例表明采用此算法可获得较好的实时预报效果．     

基于支持向量机及遗传算法的光刻热点检测

提出一种基于支持向量机（SVM）及遗传算法（GA）的集成电路版图光刻热点检测方法.首先对版图样本进行离散余弦变换（DCT）以提取样本的频域特征,然后基于这些样本训练SVM分类器以实现对光刻热点的检测.为了提高光刻热点检测的精度及效率,采用遗传算法（GA）对频域特征进行选择,并同时优化SVM参数.实验结果表明,基于SVM及版图频域特征并结合遗传算法进行优化的光刻热点检测方法可以有效提高版图光刻热点的检测精度.