关键字 |
电源,架构,异或接口,凸轮单元,芯片,设计 |
I.INTRODUCTION |
内容寻址存储器(CAM)是一种快速数据并行搜索电路。与标准存储器电路不同,例如随机存取存储器(RAM)的数据搜索是在单个时钟周期内对所有存储的信息执行的。事实上,CAM是RAM的产物。CAM广泛应用于内存映射、中央处理器的缓存控制器、数据压缩和编码等领域,主要应用于高速网络路由器和处理器上的快速Internet协议(IP)包分类和转发。IP路由是通过检查协议报头字段来完成的,即根据路由表中存储的信息检查起始地址和目的地址、传入和传出端口等。如果注册了匹配,则包被转发到表中定义的端口。在非常高速的网络和巨大的通信量上,任务需要在快速和大规模的并行中执行。然而,管理高速和大型查找表需要硅面积和功耗。功耗、硅面积和速度是设计人员面临的三大挑战。由于它们之间总是存在权衡,在不牺牲其他的情况下减少一个是最近对大型CAMs[2]的主要研究。 Finding a solution could be approached on circuit or architectural level. Here is presented the later. |
本文的其余部分组织如下。第2节是指范围内的相关工作。第3节说明了要解决的问题和所实现的技术介绍。最后给出了凸轮芯片的结构设计。第四部分是评估结果并讨论问题。第五部分对本文的工作进行了总结。 |
2相关工作 |
CAM硬件已经有几十年的历史了,许多研究都是针对在电路、架构和应用层开发高容量和有效的CAM设计。许多项目都倾向于基于CAM及其扩展版本即三元CAM (TCAM)[1]的有效的包转发算法的“真实”应用。通过“不在乎”状态增强的CAM存储器用于更复杂的项目,如基于硬件的网络入侵检测和防御系统(NIDPS)[9]。在“较低”级别的设计中,许多论文介绍了速度、功率和物理电路资源的方法和优化。[2]的作者从晶体管和电路层面详细描述了CAM功能的原理,包括核心单元、匹配线和搜索线结构以及功耗公式。并在电路层面上提出了减小功率和面积的技术。[4]给出了体系结构层面的实用设计。所提出的CAM芯片设计是基于[5]中所解释的RAM芯片电路的修改 |
3凸轮芯片设计 |
一个基本的CAM单元功能可以被观察到有两个方面:与RAM一样的位存储和CAM特有的位比较。在晶体管中,即电路级CAM结构实现为nand型或nor型及其变体已由[2]解释。但在架构级位存储使用简单的(S)RAM单元和比较功能相当于XOR,即XNOR逻辑操作。因此,我们的基本芯片单元设计被抽象为SRAM和XNOR电路的交叉产品。图1为逻辑符号和电路编译。 |
输入信号是来自搜索数据寄存器的一个位值,即要与存储在CAM数组中的所有值或存储在CAM单元中的值进行比较的输入字。单元格使能信号允许或阻止比较,即匹配过程意味着对触发器中的存储位值和输入位进行异或运算。值得一提的是表1所示的三态缓冲区扩展真值表,其中x表示输入信号,y为输出信号。“Z”表示高阻抗或实际断开的线路或开关的开关。 |
由于比较过程在两种情况下都是进行的,因此每个单元的功耗都存在于匹配状态或缺失状态。Cell使能信号即三状态缓冲区的目的是将Cell从匹配过程中“断开”,从而从功耗过程中断开。 |
A.单格分割功耗降低方案 |
正如前面在常规内容可寻址存储器中提到的,数据搜索过程沿着数组的所有单元均匀地执行,从而在每个单元中产生热量。一些提出的技术可以缓解这个问题。当执行搜索时,如果前几位不匹配,就没有必要检查剩余的位。选择性预充电最初只搜索前n位,只搜索匹配前n位的单词。对于均匀随机数据,它只需要搜索(1/ 2)n行。对于n=3,这将节省约88%的匹配线功率[2],[3] |
选择性预充能方案基本上将马赫线分为两段。一般来说,遵循相同的概念,它可以分为许多段,从而形成一个管道。如果漏掉任何一级,则关闭后续级,从而节省电力。该方案的缺点是由于管道阶段而增加的延迟和区域开销。这里展示了一种节能设计,降低了速度,即增加了延迟,但保留了相同的电路面积。这个概念背后的基本思想是在mach线中以一种方式分割,即每个CAM单元都形成一个自己的段,如图2所示。 |
所提议的方案的主要好处来自于图1所示的CAM单元的实现。即,单元格的输出仅仅是用于连续位比较的单元格使能信号,从而减少了从单元格传输结果的额外门。缺点是每个单元的三态缓冲区和XNOR门增加了传播延迟。典型的CAM由36 ~ 144位的字组成,在实际应用中应该是可接受的延迟值。值得注意的是,这里提出的一种单元分割方法是一种概念观点,而不是可以在循环级别上实现的真正的节能方案。 |
B.奇偶校验预计算功耗降低方案 |
内容可寻址存储器广泛用于网络路由器,用于IP包转发,或用于防火墙和NIDPS系统,用于包过滤。对于IPv4,基本过滤器集是在头字段{源IP,目的IP,源端口,目的端口,协议}上定义的5元组,每个字段分别等于{32位,32位,16位,16位,8位}。由此可见,104位字CAM是必需的。另一方面,大多数过滤器和NIDPS规则是在端口范围上定义的,例如[1024:2048]。用CAM实现,没有“不在乎”,它将获得单词字段重复,其中端口位增加1。即使采用预充电或流水线方法,不仅需要占用巨大的内存面积,而且在位比较中也会损失不必要的功率。例如,对于固定的源IP地址和目的IP地址,计算将在所有前64位执行,而不管剩余位字段。在这方面,可以通过对字的比特进行统计预计算来实现改进。 |
预计算从存储的词中存储一些额外的位,用于搜索主词之前的初始搜索。如果初始搜索失败,主字搜索将中止,从而节省电力。原理图如图3所示。 |
一种方法是使用预计算电路来计算1的数量,并以二进制格式将这些数据与单词一起存储。为预计算预留的比特数为log (2) 2n ï ' «[8]。作为第一步,对每个存储的单词和匹配的预计算位进行比较,该过程继续进行数据搜索。循环级计数参数提取器的一种可能的解决方案包括并行和串行连接的全加法器(FA)[7]。为了执行计算,数据字位被分组在三个位段中。值得注意的是,电路级的简单FA是由两个与、两个异或和一个或门[5]实现的。1的计数预计算凸轮的主要缺点为长数据字提出。第一个问题是由于大量的全加法器组装而产生的复杂计算方案。我们抱怨的第二个问题是预留用于存储预计算位的硅区域的损失。 |
为此提出了一种新颖而简单的预计算算法。这个解决方案很好地适应了之前推广的单单元分割管道功耗降低方案,包括以下内容:我们不计算1(或0)的数量,而是只检查数据字中1的奇偶性。为了均匀分布,功率降低了一半。与单一计数方案相比,该方案节省的电能较少,但在复杂度和使用面积方面有所提高。更多的比特奇偶校验计算只需要一个比特(k=1)来存储结果。间接地,降低计算复杂度具有速度增量的含义。如图4所示,仅用异或门实现了简单的位奇偶校验逻辑电路。数据字中1的奇数为位“1”,1的偶数为位“0”。 |
有趣的是,XOR-ing可以对任意定位的位而不是相邻的位执行。在所谓的block - xor计算块中使用了类似的电路,以实现均匀比较[7]。 |
C. CAM芯片架构 |
基于到目前为止讨论的方法,更具体地说,结合所提出的单单元分割管道和奇偶校验功耗降低机制,我们可以设计出如图5所示的内容可寻址内存的完整架构。它实际上表示小型4x4 CAM芯片,其中每一行包含存储的字,包括一个位参数存储器。2-to-4解码器仅用于写功能的行选择。值得注意的是,CAM芯片不需要时钟信号,除了数据寄存器,其中用于比较的新存储值与全局系统时钟同步。由于每个存储单元的三态缓冲区是位比较CAM功能的开关,因此可以将CAM使能(CE)信号视为CAM芯片的全局开关信号。 |
当CE=0时,所有参数内存单元都关闭,使剩余单元的搜索进程处于禁用状态。4行凸轮存储器的输出是4-to-2编码器,生成匹配发生的行号的二进制表示。最常用的是优先级编码器。 |
四、绩效评估与讨论 |
功耗降低技术总是与逻辑面积或处理速度相平衡。与以前的设计相比,本文提出的方法需要相同或更少的面积资源,特别是参数提取器。所有的功率降低都是在增加时间延迟的情况下实现的。由于匹配过程应该在单个时钟周期内完成,因此将整个系统延迟投影到图6所示的时钟周期内。一个完全匹配的整体延迟T是每个组件的所有连续延迟的和 |
T ï ' ½T ï ' «nï ´ |
其中t代表参数提取器的延迟,ï ´是凸轮单元的延迟。 |
在速度和复杂性方面,一个可能的改进可以通过分割预计算位来实现,这意味着只对一些位执行检查,例如最后一个位而不是数据字中的所有位。 |
单单元分割所节省的电量优于常规流水线,但位奇偶校验预计算与之前的方法相比减少较少。 |
另一个设计考虑因素是三状态缓冲区和XNOR门的实际实现,输入信号“Z”作为一个操作数。为仿真目的使用VHDL使用IEEE。STD_LOGIC _1164包,即STD_LOGIC信号定义,我们的CAM单元设计套件很好。 |
诉的结论 |
本文从体系结构层面设计了CAM芯片的整体模型。同时介绍了两种功耗降低技术的结合:流水线功耗方案和改进的基于预计算的方法。首先,我们将管道分割到单个细胞阶段,其中给定阶段中的每个正匹配都充当下一个状态匹配的开关,从而表明不需要像一些早期研究中所述的那样,在每个细胞中要求额外的圆形来启动比较。第二种改进方法是采用新的预计算算法。位奇偶校验需要较少的参数内存空间,执行速度快。当然,它也有一些缺点,比如功耗降低。主要的挑战仍然存在:基于所提出的方法在电路级上投射CAM网格。 |
|
表格一览 |
![Click Here 表的图标](//www.cheescube.com/articles-images/table-icon.gif) |
表1 |
|
|
数字一览 |
|
|
参考文献 |
- David E. Taylor, Edward W. Spitznagel,“使用内容可寻址存储器进行包分类”,应用研究实验室,圣路易斯华盛顿大学,2005年
- Kostas Pagiamatzis, Ali Sheikholeslami,“内容寻址存储器(CAM)电路和架构:教程和调查”,IEEE固态电路杂志,Vol.41, No.3, 2006年3月
- Scott Beamer, Mehmet Akgul“低功耗内容寻址存储器(CAM)的设计”,加州大学伯克利分校电气工程与计算机科学系
- Qutaiba Ibrahim,“使用SRL16可重构内容寻址存储器(RCAM)的高速网络设备的设计与实现”,《国际阿拉伯电子技术杂志》,第2卷,第1期。2011年6月2日
- Enoch O. Hwang“使用VHDL的数字逻辑和微处理器设计”,La Sierra大学,河滨
- 谢瑞元,阮善长,“基于栅极块选择算法的低功耗预计算内容寻址存储器参数提取器的综合与设计”,电子工程系,台北,台湾
- 陈晓明,陈晓明,“基于内容可寻址内存的预计算比较能力分析”,计算机科学与工程学报,7(4):471-474,2011
- 王金诗言“低功耗高速内容可寻址存储器”,国立中正大学,台湾
- 宋浩宇,John W. Lockwood,“基于FPGA的高效数据包分类网络入侵检测”,现场可编程门阵列国际研讨会(FPGA'05),加州蒙特利,2005年2月20-22日
|