An efficient multiple pattern matching algorithm on the graphics processing unit for digital forensics

The large increase in the average size of forensic targets and an increase in the number of forensic cases require more computational resources. The Graphics Processing Units (GPUs) are specialized for computational intensive and highly parallel operations and these enable investigators to process the forensic targets quickly. However, the GPUs have complex memory hierarchy with orders of magnitude difference in access times between certain classes of memory. The largest general purpose pool of memory on the device is uncached, much slower than access to the other memory pools and the faster memory has less capacity than others. In addition, the GPU has worse performance when the threads do not execute the same code. As threads diverge, the GPU has to begin executing them serially instead of in parallel. We propose a simple multiple pattern matching algorithm that aims at these limitations of GPU, yet gives better performance compared to other algorithms.