摘  要： 内容可寻址存储器(CAM)是一种快速匹配存储器件,在通信、雷达等许多领域有着广泛的应用。在介绍CAM基本原理的基础上,提出了以两类新型FPGA实现CAM的设计方法" title="设计方法">设计方法。例举了一种基于CAM实现的关联比较器" title="比较器">比较器及其在雷达截获系统信号处理" title="信号处理">信号处理领域的重要作用。

　　关键词: FPGA  内容可寻址存储器(CAM)  APEX系列  VIRTEX系列  关联比较器

　　内容可寻址存储器(CAM)是一种新型的存储器,它的高速、并行、易扩展和实现的灵活性使它一出现就得到人们的重视。CAM基于内容寻址,通过硬件电路实现快速匹配。CAM的并行处理特性使得它在数据分选领域倍受青睐,被广泛应用于以太网网址搜寻、数据压缩、模式识别、高速缓存、高速数据处理、数据安全和数据加密等。另外,CAM的出现也为军用信号处理(尤其是雷达截获系统信号处理)提供了新的思路。但是,由于CAM的实现是以牺牲硬件资源为代价的,常规的FPGA器件只能实现很小规模的CAM。因此,以前的CAM都是专用器件且规模较小,使用灵活性较低。随着FPGA器件门数的增加和结构的改进以及IP库的不断丰富,基于FPGA的CAM实现已成为可能。尤其是1999年底和2000年初,Altera公司和Xilinx公司相继推出了APEX和VIRTEX系列超大规模FPGA,使得利用FPGA实现大规模CAM的时机趋于成熟。

1 CAM的基本原理

　　CAM是一种专门为快速查找数据地址而设计的存储器。CAM通过把输入数据与其内所存数据相比较,能快速确定输入数据是否与其内部某个数据或某几个数据相匹配。CAM的数据寻址方式因应用要求不同而不同,最快方式下仅需要一个时钟周期便可完成对所有数据的寻址。

　　与RAM一样,CAM也是采取阵列式数据存储。其数据的写入方式与RAM差不多,但CAM的数据读取方式却与RAM不同。在RAM中,输入的是数据地址,输出的是数据;而在CAM中,输入的是所要查询的数据,输出的是数据地址和匹配标志(Match)。若匹配(即数据搜寻到),则输出数据地址。在RAM中,RAM的存储容量由地址线宽度确定。例如,10bit宽地址总线的RAM存储容量为210=1024个字节,CAM却没有这个限制,因为它不是采用传统的通过地址读取数据的方式。如若从1024个字节中查询某一数据,输入数据宽度为8bit,数据存在则输出匹配标志和10bit宽的数据地址。因为CAM不是采用传统的地址线模式读取数据,存储空间可以很容易地扩展,输入数据线宽度只由需查询的数据位数决定。图1为数据读取模式下的RAM和CAM的比较。

　　显然,CAM 的数据查询速度远远高于RAM。因此,CAM大量应用于需要高速数据处理的系统之中。CAM的出现加快了一些系统和技术的应用,如大型数据库管理、数据链接、模式识别等在图像识别、语音识别中的应用。CAM的核心为存储单元" title="存储单元">存储单元阵列和存储单元与输入数据之间的比较器。不同的应用对CAM的速度、密度有不同的要求,而且CAM实现途径也是多样的。

2 用APEX系列FPGA实现CAM

　　APEX系列FPGA是Altera公司最新推出的高档FPGA芯片,APEX系列真正实现了单芯片的系统级综合。在多心线结构的支持下,APEX芯片既具有以往PLD的优点,又对这些优点有所扩展,并且在复杂系统的设计和应用中表现出极大的灵活性和高效性。

APEX芯片内含多达250万个逻辑门,能够单芯片实现诸如锁相倍频环之类的复杂系统。它拥有64bit的数据线宽度和66MHz的总线频率,数据处理速度达620Mbit/s。2.5V供电的APEX采用0.22微米工艺,1.8V供电的APEX芯片则采用更先进的0.18微米工艺。

　　APEX芯片主要由三大部分组成:LUT、Product Term和Memory。这三大部分综合到一个芯片中,不但节省了应用系统所占空间,而且使复杂系统的设计和实现变得简单可靠,系统执行效能也大大提高。ESB(Embedded System Block)是APEX芯片的核心,它可以用来构成APEX芯片的各种控制部件。

　　通常,许多需要快速数据寻址的系统使用分立的CAM,这不仅会延长开发周期、占用印制板空间,而且也会因片内、外的时延而降低系统效能。APEX芯片则较好地解决了这个问题,它内含嵌入式CAM,把分立式CAM 20ns的时延降低至4ns以下。与采用分立式CAM的系统相比较,采用APEX芯片的系统,则效率成倍提高。对中小型系统来说,APEX芯片无疑是系统优化的最佳选择。

APEX芯片可用ESB直接构成CAM,实现高速数据寻址。还可用多个ESB扩展CAM的容量和数据宽度。在APEX20KE芯片中,每一ESB可配置成大小为32word×32bit的CAM,如图2所示。

3 用VIRTEX系列FPGA实现CAM

　　APEX提供了一个规范的CAM基本器件,可通过级联和位扩展来实现更大规模的CAM,但实现方式还是不够灵活。而Xilinx公司开发的Foundation系列软件和VIRTEX系列FPGA为CAM的应用提供了优越的软硬件条件,且VIRTEX最大的优点是没有为CAM提供固定的模式。它设计的灵活性,使CAM能在不同条件下、不同领域内,以不同方式实现,达到最优化。基于VIRTEX的CAM的实现主要有三种途径:用SRL16E的实现;用Block SelectRAM实现;用Distributed SelectRAM的实现。

3.1 用SRL16E实现CAM

　　在这种模式下,设计的基本模块为SRL16E移位寄存器。SRL16E为VIRTEX库的基本模块,用户可以使用SRL16E和其它基本模块设计出不同字宽和字深的CAM来。

　　用SRL16E实现的8-bit的CAM如图3所示。初始化时,已知参数与4位递减计数器内容依次相比较,得到16bit" title="16bit">16bit比较值(含1个“1”,15个“0”),经过16个时钟周期,依次存入SRL16E移位寄存器。寄存器带有4位地址端,可对移位寄存器的16bit数据位实现寻址。CAM工作时,数据直接输入寄存器的地址端,若此数据与初始化时参数相一致,则输出“1”,否则输出“0”。

3.2 用Block SelectRAM实现CAM

　　除了用SRL16E实现CAM外,利用VIRTEX芯片内可编程资源Block SelectRAM也是实现CAM的途径之一。一个Block SelectRAM可配置成一个CAM16Word×8bit的CAM基本模块,且有独立的读写双通道,这得益于Block SelectRAM的双口特性。Block SelectRAM是真正具有独立双通道的存储器,它的每个通道拥有各自的时钟和控制信号,A口和B口可独立配置成4096Word×1bit或256Word×16bit RAM模式。基于Block SelectRAM 的CAM的设计正是利用了Block SelectRAM内部地址映射的灵活性。

　　如图4所示,Block SelectRAM 的A口和B口具有共同的存储单元(4096bit),但可以具有各自的地址映射表,A口配置成4096Word×1bit模式,B口配置成256Word×16bit模式。在这种配置形式下,A口可以以地址线宽为12bit、存储单元容量为1bit的方式写入数据,而B口则可以以地址线宽为8bit、存储单元容量为16bit的方式读取数据。

　　CAM16×8的A口为数据写入口,数据输入带宽为8bit,地址线宽为4bit。Data_write[7：0]也可由它的译码值形式唯一地表示,Data_write[7：0]经译码成256bit,存入Addr[3：0]所指的地址单元。

　　CAM16×8的B口为数据读出口,匹配数据直接输入B口的地址端,数据读取只需一个时钟周期,输出字宽16bit的匹配结果。

3.3 用Distributed SelectRAM实现CAM

　　Distributed SelectRAM也是实现CAM的途径之一。与Block SelectRAM类似,VIRTEX芯片内部还有一种由LUT配置而成的Distributed SelectRAM,这两种存储器都可用来形成CAM。

    每个LUT(Look-Up Table)可配置成一片16Word×1bit RAM,每片RAM可以位寻址。16bit宽数据写入时,分散写入16片RAM。数据读取时,地址端由一递增计数器产生4位地址,从RAM读出数据与查询数据逐个比特相比较。最多经过16个时钟周期,便可完成与整个存储数据相比较,得到匹配结果。

4 基于CAM的关联比较器的实现及应用

    国外研究表明,关联比较器(Coherent Processor，简称CP)技术对高密度信号环境下的脉冲列去交错有着积极和重要的意义。由于器件方面的限制,国内相关领域的研究一直停留于理论分析层面,仅有极少数系统采用了一些小规模的并行比较器件。

    CP与CAM的主要区别是:CP是实现范围比较,而CAM是精确单值匹配。在基于CAM的CP设计实践中,我们结合复杂信号环境的具体应用背景和上述CAM设计方法,探索了两种可能的途径:(1)CAM和RAM结合实现结构灵活的CP;(2)从CAM内部结构和原理出发,对CAM进行适当改造,使得CAM具备范围匹配功能。

    第一种途径是通过研究许多CAM的应用实例而受到启发的。例如,IP地址到以太网地址的映射是由CAM和RAM相结合完成的,首先将IP输入CAM,得到匹配标志和匹配地址,然后将匹配地址作为RAM的输入,从RAM中读取相应的以太网地址,完成地址映射过程。还有IP路由表、高速缓存等应用的基本原理也是如此。相应地,在脉冲去交错应用中,若将脉冲参数范围内的每一个值都作为CAM中的一项,将得到的匹配输出地址作为预先存储的RAM表项的输入,即可实现CP的功能。如图5所示,设辐射源M的频率参数范围是011111100b≤RF≤011111111b,则辐射源M在CAM中占用4个存储单元n～n+3,在RAM内n～n+3地址的存储内容均初始化为M。当输入频率值落入辐射源参数范围时,便可由关联比较器直接得到所属的辐射源类型M。这种设计方法利用外部RAM实现了组合逻辑功能。

　　第二种途径是利用可编程逻辑器件灵活的设计方法,对CAM内部结构进行改造,使其具备范围参数匹配的功能。图6示出了利用这种途径实现CP的基本原理,图示结构为用一个256×1bit的RAM来实现一个8bitCAM单元。在CAM单元初始化时,以输入数据作为RAM的地址,根据参数范围对相应地址的RAM内容进行初始化,落入参数范围的寻址内容为1,否则为0。完成初始化后,CAM即可实现范围参数的匹配。

　　上述两种实现途径实际上都是通过耗费更多的硬件资源来达到范围匹配的目的。当参数范围较大时,硬件资源的需求会急剧增加,导致CAM深度的下降。若我们将上述两种途径与中值比较的原理结合起来,即用合理截取有效位数的方法来充分表示参数范围特点,则可以获得预期的效果。

　　我们利用Xilinx公司的Foundation系列软件和XCV100PQ240(10万门)FPGA芯片设计了一种基于CAM的脉冲去交错专用器件,考虑到军用信号处理领域对处理速度的严格要求,设计采用了VIRTEX的第二种实现方法:用Block SelectRAM资源实现CAM。通过功能仿真和时序仿真验证了处理器的功能,并基于我们设计的高性能可编程信号处理背板^[4]进行了半实物仿真分析,初步验证了处理器的复杂信号处理能力。

　　高度并行性是CAM的基本特征。随着FPGA技术的不断进步,CAM实现的规模和速度将会有更大的进步,基于FPGA的CAM实现将在数据压缩、模式识别、高速缓存、高速数据处理、数据安全和数据加密以及军用信号处理等各种不同的应用领域中迸发出勃勃生机。

参考文献

1 Stromon，C.D.，et al.An Architecture Based on Content  Addressable Memory for the Rapid Execution of Prolog. Proceedings of 5th International Conference and Symposium on Logic Programming， Seattle， WA，1998

2 High-Density Embedded Programmable Logic Devicesfor System-level Integration. Altera Corporation, July 1999

3 Virtex FPGA application Notes. Xilinx Corporation, 2000

4 徐 欣，卢启中.基于Virtex系列FPGA的可编程嵌入式信号处理背板的开发设计.电子技术应用，2000；(26)11

5 徐 欣,周一宇,卢启中.雷达截获系统实时信号分选处理技术研究.系统工程与电子技术,2001(3)