面向高速网络监控的并行频繁项挖掘及GPU优化关键技术研究

在高速骨干网环境中，准确、及时地识别频繁项对于检测大规模网络安全事件具有重要的意义。随着骨干网链路带宽和流量的飞速增长，面向单核处理器的频繁项挖掘算法的性能受到了严峻挑战。在多核处理器平台上，有效的并行设计是提高算法吞吐量最为直接的途径，因此并行频繁项挖掘成为提高频繁项挖掘性能廉价、高效和通用的解决方案。据此，本课题对频繁项挖掘算法的并行化方法进行了全面的研究，从多角度、多方位来考察可能的并行化方法，提出了Lock-based解决方案、Lock-free解决方案和Lockless解决方案。同时，鉴于GPU具备强大的并行处理能力、较高的性能增长速度和逐渐完备的开发环境,本课题提出将Lockless解决方案移植到GPU环境中以进一步提高系统的处理能力，从而彻底解决高速网络监控中频繁项挖掘的性能问题。

在多核处理器平台上，有效的并行设计是提高频繁项挖掘算法吞吐量最为直接的途径。本课题对频繁项挖掘算法的并行化方法进行了全面的研究，从多角度、多方位来考察可能的并行化方法，设计并论证了Lock-based 方案、Lock-free 方案和Lockless 方案。通过研究发现，Lock-based方案的最高加速比为6，即便增加更多的CPU物理核心也无法进一步提高吞吐量。这是由于当前主流的频繁项挖掘算法均需要在内存中维护一个概要数据结构，当多个线程需要同时对这个概要结构进行操作时，为保证算法的正确性，需要进行加锁操作。即便是采用性能更好的细粒度加锁方法，随着开启的线程数量越多，锁之间同步开销会越大，逐渐抵消了由多个线程同时工作带来的性能收益，导致其加速比无法突破6。Lock-free方案本质上和Lock-based方案相近，只是采用了粒度最小的锁，即使用了一种由计算机硬件支持的CAS原子操作。通过实验发现，其加速比也无法随着开启的线程数量呈线性增长。Lockless方案本质上是一种数据并行方法，难点是如何降低多个概要数据结构归并开销问题。课题引入的延迟更新概念有效地解决了这一难题，即数据项在本地线程更新之后并不立即通知汇聚线程，而是在该更新经过一定时间的累积，超过一定的阈值之后才将其上传到汇聚线程。通过将延迟更新引入到当前主流的频繁项挖掘算法中（包括SpaceSaving,Frequent,LossyCounting和CountMin Sketch），得到了对应的并行化频繁项挖掘算法。通过实验发现，其加速比和开启的线程数量呈近似线性关系，即开启的线程数量越多（需要有对应的CPU物理核心支持），其吞吐量就越高。GPU具备强大的并行处理能力，通过将Lockless方案移植到GPU上，频繁项挖掘的性能得到了进一步提高。通过本课题提出的Lockless方案，解决了频繁项挖掘算法在多核CPU上的并行问题，为解决高速网络中的高性能频繁项挖掘提供了一种廉价、高效和简单的方案。