摘要
选拔算法是两级逻辑综合中求解最小化覆盖的经典方法之一,但在输出变量集合和质立方体集合规模较大的情况下,采用选拔法求最小化覆盖存在空间复杂度高、求解时间长等问题。为此,提出了求解多输出函数最小化覆盖的改进选拔算法。利用相交迭代和局部搜索的思想,分别对选拔法的极值运算和分支处理进行了改进。实验结果表明,在现有计算机资源条件下,该算法为大规模数据条件下逻辑函数的优化提供了一种有效的方法。
Extraction method is one of the classical methods that achieve the minimum coverage in two-level logic synthesis. But as the output variables and the prime implicant grow up, both the long processing time and the resource requirement become the major problems＇ to be resolved with the extraction method. To overcome these drawbacks, a new ameliorated algorithm for the coverage minimization was presented in this thesis on the basis of the extraction method theory, which was adapted to the processing of mass data. Based on the intersection ilerative and the local search algorithm theory, two major phases in this algorithm were improved, including the extremal selecting and the branches processing. As a result, by using the existing computer resources, testing shows a promising result and the improved algorithm is superior to the others multi-output logic function optimizations.
出处
《计算机应用》
CSCD
北大核心
2008年第11期2945-2947,2951,共4页
journal of Computer Applications
基金
国家863计划项目(2006AA01Z404)
关键词
逻辑综合
最小覆盖
选拔法
极值
分支处理
logic synthesis
minimum coverage
extraction method
extremal value
process branch
