Multi-pattern matching on GPU myth or reality

Some lyrics

In the old days, when the grass was greener and the trees were taller, I firmly believed that such scary words as thread divergence, cache missing, coalescing global memory accesses and others do not effectively implement the task of multiple search on the GPU. The years went by, the confidence did not disappear, but one fine day I came across the PFAC library. If you are interested in what she is capable of - welcome under cat.

Why all this

Why do we do it and what do we want to get? The most interesting fact is the performance of the PFAC library. I want to get a high speed of work, obtained through the use of a GPU. For comparison, we will use the CPU and OpenMP implementation of the PFAC algorithm.

I assume that the reader has some understanding of the architecture of CUDA. If this is not the case yet, then the main ideas can be found in articles, for example, here and here .
')

About the library

The PFAC library was developed in 2012 and adapted to the architecture and capabilities of the video cards of that time, so if you have a video card with compute capability no higher than 3.0, you are ready to install ubuntu 12.04 and cuda 4.2, then everything should take off from the box. However, we are not looking for easy ways and in this article we will work with ubuntu 16.04 and cuda 9.0. A laptop with an Intel Core i7-7500U, GeForce 940MX and 8 GB of RAM will be used as a test bench.

Before we rush into battle and count gigabits, I will say a few words about the algorithmic part in order to understand what awaits us.

The library implements a parallel Aho-Korasik algorithm without gatherings. PFAC, respectively, is short for Parallel Failureless Aho-Corasick. The algorithm builds a prefix tree without gathering and packs it into a table.


As stated in the documentation, each thread processes data, starting with its input symbol.

However, if you look at the source, each thread handles 4 characters, which is associated with memory alignment.

All the scary words with which I started the article have a place to be in this decision. No one guarantees that all the threads inside one warp (32 successive threads inside one block) will process closely located data in the table. There are also no guarantees that all the threads inside the warp will move along one branch of the branch or exit the cycle of passage through the tree at one time.

But I suggest not to think about the bad, and with burning eyes and optimistic attitude to start a computational experiment.

Deployment

First, let's try deploying PFAC. I believe that CUDA is already installed, as well as the paths to nvcc and libraries added.

Go to the project, do make. Waiting - all is well, everything is unfolded. Harsh reality - some strange mistakes. It turns out that for CUDA 9.0 assemblies for video cards with compute capability below 3.0 are deprecated. This can be fought. You just need to change the src / makefile.


Rebuild.

Whew! It seems to be all right. Add to LD_LIBRARY_PATH the path to the lib folder. We try to run the test example simple_example - the error takes off:

simple_example.cpp:64: int main(int, char**): Assertion `PFAC_STATUS_SUCCESS == PFAC_status' failed.

If you add the output PFAC_status - we get the status 10008, which corresponds to PFAC_STATUS_ARCH_MISMATCH. For reasons unknown, the architecture is not supported.
We dive into the code deeper. In the src / PFAC.cpp file, we find the following code that generates this status.


From the comments next to it becomes clear that the code does not work only with compute capability 1.0. Replace this fragment with

  int device_no = 10*deviceProp.major + deviceProp.minor ; if ( 11 > device_no ) return PFAC_STATUS_ARCH_MISMATCH ; sprintf(modulepath, "libpfac_sm%d.so", device_no); 

It seems now everything is fine. More explicit dependencies on the version of the computational capabilities of the video card are not observed.

Again, try running the test version. Observe a strange error:

Error: fails to PFAC_matchFromHost, PFAC_STATUS_CUDA_ALLOC_FAILED: allocation fails on device memory.

Fortunately, there is a way to enable debug information in the library.
In the include / PFAC_P.h file you need to uncomment the line

 #define PFAC_PRINTF( ... ) printf( __VA_ARGS__ ) 

And, accordingly, comment out

 //#define PFAC_PRINTF(...) 

Now, after running simple_example, you can see a more distinct error message:

Error: cannot bind texture, 11264 bytes invalid texture reference
Error: fails to PFAC_matchFromHost, PFAC_STATUS_CUDA_ALLOC_FAILED: allocation fails on device memory

Yeah, so the problem is not the allocation of memory, but the use of texture memory. PFAC allows you to disable texture memory. Let's try to use it. In the test / simple_example.cpp file, after creating the handle, add the line:

 PFAC_setTextureMode(handle, PFAC_TEXTURE_OFF ) ; 

The miracle happened, the console gave us the long-awaited lines.


However, ancient manuscripts suggest that texture memory improves performance through the use of texture cache. Well, let's try to run PFAC with texture memory.

PFAC supports 2 modes of operation PFAC_TIME_DRIVEN and PFAC_SPACE_DRIVEN. We are interested in the first. The implementation is located in the src / PFAC_kernel.cu file.

We find the lines where the texture memory is mounted on the global one:

 cuda_status = cudaBindTexture( &offset, (const struct textureReference*) texRefTable, (const void*) handle->d_PFAC_table, (const struct cudaChannelFormatDesc*) &channelDesc, handle->sizeOfTableInBytes ) ; 

For video cards with compute capability 5.0 and later, the implementation of the texture memory operation is somewhat changed and the access mode set is incorrect, so we replace this line with

 cuda_status = cudaBindTexture( &offset, tex_PFAC_table, (const void*) handle->d_PFAC_table, handle->sizeOfTableInBytes ) ; 

After that, in the test / simple_example.cpp file we turn on the texture memory again:

 PFAC_setTextureMode(handle, PFAC_TEXTURE_ON ) ; 

We check the work - everything works.

Testing and Comparison

Now look at the performance of the library.

For testing we will use signatures provided by clamAV
Download the file main.cvd. Next, unpack

 dd if=main.cvd of=main.tar.gz bs=512 skip=1 tar xzvf main.tar.gz 

We will test on the signatures of the main.mdb file. We do many routine actions: we cut off n lines and consider them to be patterns, shaflim input data, etc. I think here it’s no longer necessary to bump into the details.

In order to play with performance, I have somewhat modernized the test / simple_example.cpp file.


Because for time measurements I use std :: chrono, in the test / Makefile file you need to add the -std = c ++ 0x flag. And do not forget to set the number of threads for OpenMP (I used 4 myself):

 export OMP_NUM_THREADS=4 

Now you can begin to measure performance. Let's see what the GPU can show. The length of each pattern is 32, the length of the input data is 128 MB.

We get the following schedule:



As the number of patterns grows, performance degrades. This is not surprising, because the Aho-Corasica algorithm without gathering depends not only on the input data, but also on the patterns, since for each position in the text, it is necessary to go deep into the tree for the length of the matched substring of the text with the prefix of any attribute, and with an increase in the number of patterns, the probability of finding a substring coinciding with a certain prefix increases.

And now a more interesting graph - acceleration, with the help of the GPU.



On a small number of patterns, it is almost imperceptible, it is eaten by data transfer. However, as the number increases, so does the acceleration, which indicates the potential possibilities of the GPU in an unusual task.

Instead of output

When I took on this task, I was skeptical, because there can be no such thing. However, the result gives hope for the possibility of using CUDA in an uncharacteristic industry.
The path of the researcher does not end there, it will take a lot of work, a lot of performance research and comparisons with competitors.

The first step is made, do not lose hope!