海成用
基于FPGA的布尔匹配算法改进研究
俞亚
(掌庆学院电子信息与机电工程学院广东肇庆526061)
算法分析
摘要：文中首先介绍了市尔匹配与FPGA的关承，分析了市尔医配问题转化为可满足性问题，针对市尔匹配算法的问题提出了改进措施，通过异构的查找表象映射电路可以减小关键路径上的时间延这通过把可编程逻辑单元的入划分为等价类，能够有效加快布尔匹配的速度。
关键词：FPA布尔匹配算法算法改进中图分类号：TN791
文献标识码：A
1、布尔匹配与FPGA的关系
文章编号：1007-9416(2011)10-0109-02
中L输出，当x，X，，的输入值为01时，选中L1，输出，以此类推。按算
FPGA(FPGAField-Programmable Gate Array,即现场编程门阵列)是-种可以直接编写程序的芯片组。可编写程序是指芯片在制造出广后，程序编写者能够对给芯片组进行加载不同的配置参数或文件来实现不同的电路功能。
在应用异构FPGA的技术映射过程中，布尔匹配是一个相当重要环节，布尔匹配目前正要应用在集成电路设计中的技术映射过程阶段。与树匹配的方法相比，布尔匹配具有最佳的映射效果，其理由是树匹配属丁拓扑型结构的，而布尔匹配则是属于布尔函数的，现实中大多时候树匹配是无法判断映射问题的，基本上都可以用布尔匹配来解决闻题。
2、布尔匹配问题转化为可满足性问题
FPGA对十可编程逆辑区域内的不可编程器件，是可以把器件的相关逻辑功能通过输山变量和输人变量来组成的合取范式的方法来表示。
算法2.1通过真值表来构造CNF的实现过程如下：
Stepl对每个门表示的函数f.假定它的输人为x1，×2....，x n，输出为y，为该逻辑门构造-·个表示特征函数的真值表，即(y <=>(×1，×2，，×n))。真值表表示了对于该逻辑门而言哪些输人和输出的组合是合法的。
Step2对步1中的真值表中的闭集(off-set，即最右一-列为假的那些项)构造-个积之和公式，用来表示真值表中不合法的输人输出组合，记该公式为一中。
Step3应用DeMorgan律，中一（一），得到表示该门j的CNF 公式。
( 介并为·个了句α。其中α是文字的析取。这个处理过程在S^T求解的术语中称为消解(resolution)。
这·步相当于化简，并不是必领的。 2.1可编程逻辑块到CNF的转换
在：-个可编程的逻辑块内，可能既有专门的宏门电路，也有食找表，将：-个尔表达式变换成CNF形式有多种方法，算法2.1给出了，-种基下真值表的方法，将每个其本的门或者负找表转换成 CNF
例如，对下两输人的或门电路，如果它的两个输人分别为×和 y，输出为%，按节法2.1的步骤1。
按步聚2目真值表中闭集构造出公式为
=(A)+(A, A)+(xF2)+(xA,FA~) 第3步，可以得到功，
(2 + .f + K= + + K= + . + x)2 + + + x) =
第4步，对子创进行消解处理后，得到化简后的CNF，即 = (x+ y+ K+ 2)y + 2)
对于查找表，也可以算法2.1来进行处理，例如，图2.1是--个两输人的查找表，它的配置位为LL,L,L，，当×，×，的输入值为00时，选
法2.1的第一步列出真值表，显然可以得到不合法的输入(即闭集)。
函数的真值表(b)一个可编程逻辑块
LO
00
1
L2H 1.3
图2.1
x1x2x3
000 001 010 011 100 101 110 111(a)
0 0 1 0 1-1 一
01 10
xI
4 NUX
A x2
个两输入的查找表 xI
LUT2 X2
X3
(b)
2(a)函数f的真值表。(b)一个可编程逻辑块
图2.2
把这些项组成一-个析取范式，然后取反，就可以得到这个查找表对应的CNF公式：
(x, + X, + L, + z) ^ (x, + X, + L, + ) A(x, + X, + ~L, + 2) ^ (x, + X, + L, +2) ^(x, + x, + L, + 2) ^ (x, + X, + L, + )^(x, + X, + ~L, + 2) ^ (x, + X, + L, + 2) A
对由多个和食找表构成的可编程逆辑单元，为每个门或者查找表增加·个表示它的输出的中间变最，然后分别为每个门或者征找表按照输人和输出关系来构造相应的CNF公式，再把这些公式合取就得了最终的CNF公式。
2.2布尔匹配间题到可满性间题的转换
通过将作尔配相关间题转化为可以是性相关前题，并根据 2.1法可知,用CNF公式的通数G(x.,.Z,.Z.0)来表示FPGA可编程逻辑模块的功能，其中用到的变量有x..。。意指是输人信号，变量名为L...L。意指查找表对应的配置位信息，变量名为Z,.,Z,，意指FPGA可编程逻辑模块内中心间的连接信号，0意为输出。用方法F(..)来表示输人x输出值为f
109