论文部分内容阅读
逻辑综合算法的目的是用数字电路实现布尔逻辑函数,并且能够用较少的电路面积来优化数字电路的性能。在过去50多年内,研究人员已提出了很多种逻辑综合算法。本文在调研前人算法的基础上,通过各种实验得出两条结论：a.逻辑综合中大部分优化的电路结构已经被其他的算法和工具生成,没有必要去实现新的算法重复生成这些电路。b.大的电路都是由小的电路构成,相当一部分小电路经过翻转输入／输出端口和重新排列输入端口后完全等效。基于以上结论,本文提出了一种基于预编译库的逻辑综合算法,利用前人的成果来进行逻辑综合。本文提出的逻辑综合算法能够将不同的算法作用在基准电路集上,收集这些算法产生的优化电路,建立一个预编译库。然后在逻辑综合时重用这些电路,而不是在运行时动态生成这些优化电路。为了能够更好地重用已有的电路,快速地对布尔函数进行分类和储存,本文提出了一种准NPN形式对函数进行分类,与传统的NPN(Negation-Permutation-Negation)分类方法相比,本文提出的准NPN算法大大降低了时间复杂度。在准NPN函数分类的基础上,本文建立了一个6输入的AIG库,该库中有多达上百万个逻辑结构。本文还对基准电路中出现的逻辑结构(输入数目小于等于12)进行了统计,并把统计到的结果开源,供后人使用。本文将这种基于预编译库的逻辑综合方法应用在了AIG级数优化上,进而改进电路在FPGA工艺映射后的时序性能。结果显示,相比最近提出的SOP平衡树算法,当作用在工业大电路时,工艺映射成4-LUT和6-LU后的时序性能分别改进17%和18%,而分别只牺牲了2%和5%的面积。而作用在学术电路MCNC电路集上时,工艺映射成4-LUT和6-LU后的时序性能也分别改进10%和12%,而分别只牺牲了3%和8%的面积。这样的改进是非常显著的,因为SOP平衡树算法已经是一个非常高效的优化算法。