数据流字符串匹配算法并行化运行与性能测试

邢光升

摘要：该文实验模拟数据流在本地或集群分布式处理的条件下，多线程多进程、CPU+GPU异构等处理模式的字符串匹配测试，研究了在多进程，多线程下最佳并行运行节点数，GPU最佳优化参数设置，CPU+GPU异构环境下最佳搭配优化方案。

關键词：字符串匹配;CPU;GPU;测试优化;多线程;多进程

中图分类号：TP3        文献标识码：A

文章编号：1009-3044（2019）16-0278-02

开放科学（资源服务）标识码（OSID）：

网络数据处理过程中对于高速带宽环境下关键包快速识别提取要求较高，现行常用的做法是基于硬件的深度包检测设备（DPI），尽管该设备针对五元组和关键字匹配识别的性能强悍，现行可以达到40Gbps线速，几百万条五元组匹配和几十万条关键字匹配的性能，但由于其可扩展性差，不能与后面其他的软件程序松耦合度的灵活结合，且价格昂贵，通常一台DPI设备一块10Gbps处理板卡需要几十万的价格，因此更多的用在海量高速网络数据处理当中，对于对线速处理要求一般，关键字匹配条数不多的情况就可以直接在通用的X86平台或者集群下实现，甚至在带有GPU卡的平台环境下高效运行，如何有效地利用有限的资源最大程度地提高匹配速度成了需要研究的重点。

实验模拟数据流在本地或集群分布式处理的条件下，字符串匹配挖掘，主要包括多线程多进程、CPU+GPU异构等处理模式，给定关键字对整个数据流进行搜索匹配，并对处理过程进行记时，观察对比并行化处理下的效果，并且查找优化在并行运行过程中最佳优化时间，并记录此时绑定的核数。研究在多进程，多线程下最佳并行运行节点数，GPU最佳优化参数设置，CPU+GPU异构环境下最佳搭配优化方案。

1 实验条件及环境

（1）带GTX系列显卡笔记本两台：主要用于程序代码编写，程序编译、调试;

（2）天河二超算平台：程序在CPU环境下并行运行测试（多进程 多线程）;

（3）带GTX1070卡的GPU工作站：CPU+GPU处理模式调式测试;

（4）模拟字符串数据文件，大小500MB。

2 实验原理及思路

2.1 多线程/进程字符串匹配算法

该算法是基于朴素字符串匹配改进成的可以进行多进程实现的。字符串匹配算法主要是两个循环嵌套，但是两个循环都是相互独立的，所以我们每次滑动的窗口从原来的1，变为进程数n，也就是每个进程每次只识别匹配字段的长度，然后跳到n个字符后继续识别。最后再把每个进程所计算部分匹配的字符串总数规约到0号进程，统一输出。

2.2 CUDA流编程实现思路

CUDA流在加速应用程序方面起着重要的作用。CUDA流表示一个GPU操作队列，并且该队列中的操作将以指定的顺序执行。我们可以在流中添加一些操作，如核函数启动，内存复制等。将这些操作添加到流的顺序也就是他们的执行顺序。可以将流视为有序的操作序列，其中即包含内存复制操作，又包含核函数调用。然而，在硬件中没有流的概念，而是包含一个或多个引擎来执行内存复制操作，以及一个引擎来执行核函数。

因此，在某种程度上，用户与硬件关于GPU工作的排队方式有着完全不同的理解，而CUDA驱动程序则负责对用户和硬件进行协调。首先，在操作被添加到流的顺序中包含了重要的依赖性。CUDA驱动程序需要确保硬件的执行单元不破坏流内部的依赖性。也就是说，CUDA驱动程序负责安装这些操作的顺序把它们调度到硬件上执行，这就维持了流内部的依赖性。

2.3 GPU+CPU异构算法实现思路

主要按比例将实验数据分配到GPU众核模式和CPU多线程模式中进行检测，GPU控制独占一个线程，其他线程优化分配处理分配到CPU中的数据，延伸出的问题是，由于GPU独占一个线程，可能会破坏了原有单独测试CPU多线程模式的最佳工作状态，因此在具体测试过程中将CPU线程数加入考虑。

2.4 GPU热启动问题及解决思路

任何一个CUDA程序，在第一次调用CUDAAPI时后都要花费毫秒级的时间去初始化运行环境，后续还要分配显存，传输数据，启动内核，每一样都有延迟。为了解决这一问题，保证测试时间的正确性，因此在测试过程中测试过程循环运行多次，保证GPU在第一次调用后完全实现热启动。

3 实验结果

我们把实验整体分为三个部分，分别是：

（1）MPI编程实现数据流字符串匹配算法在天河平台的多进程运算效率优化测试;

（2）OpenMP编程实现数据流字符串匹配算法在天河平台的多线程运算效率优化测试;

（3）CUDA编程CPU+GPU模式下的关键字符串匹配程序，在GPU工作站上进行CPU+GPU异构运算效率优化测试。

1）多进程部分

2）多线程部分

3）GPU+CPU异构部分

（1）首先完成在工作站（gtx1070ti）环境下最优block和thread点测试，截图并记录不同点下的结果。先找到每个block的最大线程数量，是否时最佳运行效率。然后再找到每种GPU下最佳效率点的block数，判断是否时最大block承载数。

（a）测试每个block内thread数量极限及对于运行效率的影响，此时固定block数量为38，分别测试thread数量在32、64、128、256、512、1024、1025、2048时候的运行情况。

由上述实验结果可以发现，对于gtx1070ti显卡来说，其每个block最大thread数量为1024，超过这个数量运行会报错，同时1024也是最佳运行效率点。

（b）测试block数量对于运行效率的影响。接（1）中测试结果固定每个block中thread数量为1024，分别测试block数量为1、4、8、16、32、34、36、37、38、39、40，观察运行结果

由实验结果可以发现，对于gtx1070ti显卡来说，在block数量为36-38时运行效率较高，超过38运行效率会下降，这与查阅资料得到的结论block数量为Multiprocessor数量两倍时能够充分利用SM资源达到运行效率最佳的结论相吻合，gtx1070ti的Multiprocessor數量为19，由实验结果可知可以适用于一般实验结论。

结合上述两个显卡的实验结果结合查询资料，目前流行的GTX显卡系列单个block数量支持最佳（最大）thread数量为1024，最佳block数量为Multiprocessor数两倍。

（2）以之前测试的最优CUDA流数量和每个CUDA流分配数据量的最佳优化点作为GPU多CUDA流的基础运行参数，分别进行CPU+GPU异构环境下的初始优化测试。

在实际测试过程中取CPU线程数2-16，CPU数据占比0.05-0.95（粒度为0.05）进行测试，在实际测试过程中发现在工作站环境下测试优化比较烦琐，存在多个最佳优化组合区域。

可以发现存在以下优化组合区间，在CPU分配数据占比为0.05时，CPU优化线程数为1、2;在CPU分配数据占比为0.1时，CPU优化线程数为3、4、5;在CPU分配数据占比为0.15时，CPU优化线程数为3、4、5;在CPU分配数据占比为0.2时，CPU优化线程数为7、8;在线程数为3，数据占比为0.1和在线程数为7，数据占比为0.2时能够达到比较好的优化效果，有较大概率能够达到优化时间在210ms以下。

4 结语

通过实验我们发现，对比三种并行化手段，在相同算法并行方式的条件下，MPI的多进程并行对500MB数据的字符串匹配，最快可以做到206ms;OpenMP的多线程并行，最快可以做到271ms;以CPU+GPU的异构形式的多线程并行，在线程数为3，数据占比为0.1和在线程数为7，数据占比为0.2时能够达到比较好的优化效果，最快可以达到206ms。在CPU+GPU异构的条件下我们在工作站中跑出的结果可以和天河平台中跑出的结果基本相当，而单块gtx1070ti的价格远比天河集群的单节点都是12核至强E5的CPU的价格低得多，整个工作站的配置费用也比服务器集群低得多，这说明在字符串匹配方面众核GPU+CPU异构模式在特定场景下比CPU集群有更高的性价比，证明CPU+GPU异构在字符串匹配算法的并行优化是有意义的。下一步在日常的工作学习中还要进一步研究各种情况下的并行优化设计，以及GPU的高效运用。

【通联编辑：代影】