论文部分内容阅读
网络速度的飞速发展对网络搜索引擎提出了新的要求。应运而生的是各种硬件搜索引擎,最为常用的是基于TCAM(三态按内容可寻址存储器)的硬件搜索结构,它是一种并行搜索的硬件结构,具有较高的搜索速度,因此被广泛应用于各种高速网络搜索引擎中。然而TCAM的并行性导致其功耗特别高。而且TCAM结构较为复杂,一个典型的TCAM单元由14个晶体管组成,由它组成的搜索引擎面积很大,不利于扩展。因此它不适用于下一代高速网络应用。人们着眼于新的高速搜索解决方案。一种很好的解决方案是算法与硬件结合的解决方式。比较热门的主要有基于hash的硬件结构和基于 Trie的硬件实现。而基于 Trie的硬件实现方案被认为是下一代搜索引擎的最佳选择。为了进一步提高吞吐量,需要采用流水线的设计方案。但传统的基于Trie的硬件实现方式存在流水线内存分配不均,负载不均衡等问题。基于优化的线性流水线(OLP)方案,能均匀的分配每级流水线的任务,能实现每周期一次查找,但是该方案流水线级数太长,导致查找延时过长,且该方案存在节点布局不完整的问题,因此,该方案值得进一步研究。 本文研究了基于Trie的流水线实现方式,基于优化的线性流水线(OLP)方案,提出了一种EOLP(Enhanced Optimized Linear Pipeline)方案。首先是前缀扩展长度确立算法,有效的确定了每级流水线 SRAM的大小,有利于减少流水线的级数;其次本文提出了新的节点布局算法,解决了原有 OLP算法可能无法布局完节点的不足。最后,本文提出编码算法,能将节点有效的编码,使得其可在 SRAM进行索引操作。为了验证EOLP方案的可行性,本文将方案在FPGA上进行了实现和验证。FPGA实验结果表明,相对于OLP方案,EOLP方案的内存占用和流水线延时至少减少了1/6,并克服了可能无法完全布局节点的问题,同时达到了72Gbps的吞吐率,满足高速网络的需求。最后,在通过FPGA验证之后,针对典型路由表rrc(容量为50K条),本文做了专用集成电路(ASIC)的版图实现。采用Global Foundry65nm工艺,综合后的版图面积为3490um×3985um。版图后仿真结果表明,吞吐量为80Gbps,再次印证了EOLP的可行性。