GPGPU OpenCL实现精确字符串查找

字符串查找是信息安全、信息过滤领域的重要操作，尤其是对大文本的实时处理。这篇作为实例，使用GPU OpenCL进行精确模式串查找。

1.加速方法

(1)将少量常量数据，如模式串长度、文本长度等，保存在线程的private memory中。

(2)将模式串保存在GPU的local memory中，加速线程对模式串的访问。

(3)将待查找的文本保存在global memory中，使用尽可能多线程访问global memory，减小线程平均访存时间。

(4)每个work-group中的线程操作文本中一段，多个work-group并行处理大文本。

2.同步

(1)work-group内，使用CLK_LOCAL_MEM_FENCE、CLK_GLOBAL_MEM_FENCE

(2)全局使用对__global int 的原子操作，来保证每个线程将结果写到全局内存的正确位置。设备支持的操作可以通过查询设备的扩展获得，如下图，可知核函数支持原子操作、printf操作：

3.代码实例，大文本精确模式串搜索

3.1 核函数(string_search_kernel.cl)：

int compare(__global const uchar* text, __local const uchar* pattern, uint length){
    for(uint l=0; l<length; ++l){
        if (text[l] != pattern[l])
        return 0;
    }
    return 1;
}

__kernel void
    StringSearch (
      __global uchar* text,        //Input Text
      const uint textLength,        //Length of the text
      __global const uchar* pattern,    //Pattern string
      const uint patternLength,        //Pattern length
      const uint maxSearchLength,    //Maximum search positions for each work-group
      __global int* resultCount,    //Result counts (global)
      __global int* resultBuffer,    //Save the match result
      __local uchar* localPattern)    //local buffer for the search pattern
{  

    int localIdx = get_local_id(0);
    int localSize = get_local_size(0);
    int groupIdx = get_group_id(0);

    uint lastSearchIdx = textLength - patternLength + 1;
    uint beginSearchIdx = groupIdx * maxSearchLength;
    uint endSearchIdx = beginSearchIdx + maxSearchLength;
    if(beginSearchIdx > lastSearchIdx)
    return;
    if(endSearchIdx > lastSearchIdx)
    endSearchIdx = lastSearchIdx;

    for(int idx = localIdx; idx < patternLength; idx+=localSize)
        localPattern[idx] = pattern[idx];
    barrier(CLK_LOCAL_MEM_FENCE);

    for(uint stringPos=beginSearchIdx+localIdx; stringPos<endSearchIdx; stringPos+=localSize){
    if (compare(text+stringPos, localPattern, patternLength) == 1){
            int count = atomic_inc(resultCount);
            resultBuffer[count] = stringPos;
        //printf("%d ",stringPos);
        }
    barrier(CLK_LOCAL_MEM_FENCE);
    }
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索memory
， 线程
， 文本
， 模式
， opencl
， global
， fence 线程
精确
grep 精确匹配字符串、sed 精确匹配字符串、python精确匹配字符串、java字符串精确匹配、vba find 精确查找，以便于您获取更多的相关知识。