چكيده به لاتين
Abstract:
Pattern matching algorithms are used in many areas. One of their most important applications is in the network intrusion detection systems (NIDS) and DNA sequencing. Given the fact that Internet bandwidth is increasing by the day, it is highly important to speed up pattern matching. There are many ways to increase your speed, but is one of the most optimal ways to implement parallel processing algorithms. Today, the Graphics Processor Unit, due to the high power of parallel computing and cheap, widely used in parallel processing.
The Rabin-Karp algorithm can be used for both single-pattern and multi-pattern matching. Nowadays GPUs are implemented due to their high processing power in parallel computations and their cheap prices in parallel processing. A new method was proposed for parallel execution of the Rabin-Karp algorithm. In this method, classification of patterns was used to prevent redundant comparisons and increase the speed up rate. This procedure has two advantages, one that reduces the number of comparators hash values and that given the low number of comparison, the reading patterns of global memory graphics processor is low. Given that the exchange is always a dilemma in memory parallel processing GPU, so the exchange with memory loss can lead to improved throughput output.
The proposed algorithm was tested on GPUs powered by NVIDIA in two general cases. In one case large number of letters other case for sequencing DNA that is of little letters. Each of these cases has increased for three entries, increase the number of pattern and extend the pattern were compared on NVIDIA GPUs using CUDA Platform was about implementation. When the number of characters is large, the acceleration was good, especially for the increasing number of patterns, the results of more than three times the reach to accelerate. But due to the low number of letters of DNA sequence and thus the low number of categories, as well as increased risk of incorrect attempts at Robin algorithm-crepe, good results when the number of characters is large is not. As a result of the algorithm Rabin-Karp for applications where a large number of letters in it much more suitable for applications that have a small number of letters. Because when the number of characters is large, you can create many categories in which case the maximum benefit from the proposed method can be used Categories patterns.
Keywords:
Pattern Matching; Rabin-Karp; GPU; NIDS; Parallel Processing; DNA sequencing
