Hash算法在网络处理器中的实现  

Implementation of Hash Algorithm in Network Processor

作　　者：付仲满[1] 张辉[1] 李苗[1] 刘涛[1] 

机构地区：[1]中国电子科技集团公司第三十二研究所,上海200233

出　　处：《计算机工程》2014年第9期269-274,279,共7页Computer Engineering

摘　　要：提出一种应用于网络处理器的Hash算法,通过建立新型查找表的结构和构造两级Hash函数,能够有效地解决Hash冲突的问题。描述Hash表的软件建立流程和硬件查找过程,在Hash查找的基础上,给出硬件表项的学习过程和老化方法,简化表项的更新操作。针对不同的应用,建立不同类型的Hash表,合理地利用内外部存储资源,兼顾了存储资源和处理速度的平衡。实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25Mb/s,能够满足网络处理器接口处理带宽20Gb/s的要求。A novel Hash algorithm is proposed in this paper for network processor application. It resolves Hash collision problem by constructing new look up table and new two-level Hash function.The software processing and hardware lookup flow of Hash table are descripted,and the learning process and ageing machine for entry of table are designed for simplifying the entry updating operation.For different engineering applications,the algorithm sets up different Hash table,which makes the efficience of memory utilization improved and the tradeoff between memory and processing speed optimized.Simulation results show the algorithm works well despite of the number of table entry and the size of keyword.The average length of look up＇s success is2 and the memory access times is reduced dramaticlly. The look up speed of micro-engine is improved to25Mb/s,satisfing the requinrement of20Gb/s bandwidth performance of network processor.

关 键 词：网络处理器 HASH表 查找效率 学习 老化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]