Hash算法在网络处理器中的实现-计算机工程.PDFVIP

第40卷　 第9期 　 计 算 机 工 程 　 2014年9月 　 　 Vol.40　 No.9 　 Computer Engineering September 2014 ·开发研究与工程应用 · 文章编号:1000-3428(2014)09-0269-06　 　 　 文献标识码:A　 　 　 中图分类号:TP393 Hash算法在网络处理器中的实现 付仲满,张　 辉,李　 苗,刘　 涛 (中国电子科技集团公司第三十二研究所,上海200233) 摘　 要:提出一种应用于网络处理器的Hash算法,通过建立新型查找表的结构和构造两级Hash 函数,能够有效地 解决Hash 冲突的问题。 描述Hash表的软件建立流程和硬件查找过程,在Hash查找的基础上,给出硬件表项的学 习过程和老化方法,简化表项的更新操作。 针对不同的应用,建立不同类型的Hash 表,合理地利用内外部存储资 源,兼顾了存储资源和处理速度的平衡。 实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均 具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25 Mb/ s, 能够满足网络处理器接口处理带宽20 Gb/ s的要求。 关键词:网络处理器;Hash表;查找效率;学习;老化 Implementation of Hash Algorithm in Network Processor FU Zhong-man,ZHANG Hui,LI Miao,LIU Tao (The32nd Research Institute of China ElectronicsTechnology Group Corporation,Shanghai200233,China) 【Abstract】A novel Hash algorithm isproposed in thispaper for network processor application.It resolves Hash collision problemby constructingnewlook up tableandnewtwo-level Hash function.The softwareprocessingandhardwarelookup 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 showthe algorithm workswell 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 isimproved to25Mb/ s,satisfingtherequinrement of20 Gb/ sbandwidth performance of