一种支持大规模数据逻辑函数优化的改进选拔算法  

Improved extraction method on logic function optimization of mass data processing

作　　者：叶静[1] 于磊[1] 曾光裕[1] 白燕[1] 

机构地区：[1]信息工程大学信息工程学院,郑州450002

出　　处：《计算机应用》2008年第11期2945-2947,2951,共4页journal of Computer Applications

基　　金：国家863计划项目(2006AA01Z404)

摘　　要：选拔算法是两级逻辑综合中求解最小化覆盖的经典方法之一,但在输出变量集合和质立方体集合规模较大的情况下,采用选拔法求最小化覆盖存在空间复杂度高、求解时间长等问题。为此,提出了求解多输出函数最小化覆盖的改进选拔算法。利用相交迭代和局部搜索的思想,分别对选拔法的极值运算和分支处理进行了改进。实验结果表明,在现有计算机资源条件下,该算法为大规模数据条件下逻辑函数的优化提供了一种有效的方法。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.

关 键 词：逻辑综合 最小覆盖 选拔法 极值 分支处理 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]