基于AVX指令集的Sketch算法优化研究  

Optimization Study of Sketch Algorithm Based on AVX Instruction Set

作　　者：谭玲玲 杨飞[1] 易军凯 TAN Ling-ling;YANG Fei;YI Jun-kai(Institute of Automation,Beijing Information Science and Technology University,Beijing 100192,China)

机构地区：[1]北京信息科技大学自动化学院,北京100192

出　　处：《计算机科学》2021年第S02期585-587,596,共4页Computer Science

基　　金：NSFC-通用技术基础研究国家自然科学基金联合基金重点基金项目(U1636208)。

摘　　要：网络流量检测是网络测量中最基础也是最重要的一环。基于Sketch的侦测方法可对网络数据流进行计数,此计数在网络流量的异常检测中具有区分大象流,并对异常流量进行检测和定位的作用。Sketch的实现过程中因用到多个哈希函数而对内存资源的要求较高,针对Sketch的实现中应用多个哈希函数的性能瓶颈问题,提出了一种基于效率高、成熟度高的AVX指令集来提高Sketch性能的方法,研究了对CPU指令的消耗和算法计算效率的影响。首先,将数据流的元素用向量的形式来描述和存储,运用AVX指令实现向量的构造和运算。其次,将多次哈希运算简化成一次向量运行,降低Sketch对CPU计算资源的消耗,提升了多次哈希函数的综合性能,使得提升Sketch优化性能成为可能。最后,运用AVX指令集对Count-Min Sketch算法程序中的关键函数进行优化,并对优化后的代码进行测试分析。实验结果表明:在哈希函数的运算方面,AVX优化版本消耗的时间为原始版本的25%;当数据长度较短时,多个哈希函数消耗的指令在整个Sketch中占比较少,AVX优化版本消耗的时间约为原始版本的70%;随着数据长度逐渐增大,多个哈希函数消耗的指令在整个Sketch中占比也逐渐增大,AVX优化版本消耗的时间降为原始版本的40%。实验的仿真结果验证了该算法在提高网络数据流测量效率方面的有效性。Network traffic detection is the most basic and important part of network measurement.The detection method based on Sketch can count data flow of network,which can distinguish elephant flow,detect and locate abnormal traffic in abnormal detection of network traffic.Higher requirement of the memory resources is needed for multiple hash functions used in the implementation of Sketch.To address the restriction problems raised by multiple hash functions applied in the realization of Sketch,a method of improving the performance of Sketch algorithm using AVX instruction set is put forward,and also the effects on CPU instruction consumption and algorithm computing efficiency are studied,which had high efficiency and high maturity.Firstly,the elements of data stream are described and stored in the form of a vector,utilizing AVX instructions to realize structures and operations of vectors.Secondly,multiple hash operations are transformed into a vector operation,which reduces the CPU resources consumption of the Sketch algorithm,improves the comprehensive performance of multiple hash functions,and made it possible to improve the optimized performance of Sketch algorithm.Finally,AVX instruction set is used to optimize the key functions in the Count-Min Sketch algorithm program,and the optimized code is tested and analyzed.The experimental results show that the AVX optimized version takes 25%time of the original version in the operation of hash function.When the data length is short,the instructions consumed by multiple hash functions are relatively small in the whole Sketch,and the AVX optimized version consumes about 70%time of the original version.As the length of the data increases,instructions consumed by multiple hash functions take up a larger proportion in the whole Sketch algorithm,and the time consumed by the AVX optimized version can be reduced to 40%of the original version.The simulation results demonstrate the effectiveness of the proposed algorithm in improving the measurement efficiency of network data flow.

关 键 词：AVX指令集 SKETCH 网络测量 CPU加速 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]