## 5 Experimental Results
### Throughput Analysis
#### 5.3.2 Wu-Manber Algorithm  
Algorithm 2 shows pseudo-code of the parallel implementation of the WM algorithm that executes the pattern-matching process using multiple CUDA threads. Here, pos represents the current position on the target text, m represents the length of the shortest pattern in the pattern set, and patSize represents the number of patterns in the pattern set. Pattern-matching tests of the WM algorithm are performed in two different versions. In one of them, network packets are held in global memory (WM), while in the other version, network packets are held in shared memory (WM-ps). Figures 11 and 12, respectively, compare the packet-processing times and throughputs of these pattern-matching versions applied to datasets with different numbers of patterns.  
Figure 10: Comparison of the throughputs obtained from the pattern-matching tests performed using the AC algorithm.  
Figure 9: Comparison of the packet-processing times obtained from the pattern-matching tests performed using the AC algorithm.  
```
input: pos, m, patSize ifpos is greater than m-1 or equal to m-1 then  targetTextSuffixHash=ComputeTargetTextSuffixHash(pos);  GetShift(targetTextSuffixHash); ifshift is equal to 0 then  targetTextPrefixHash=ComputeTargetTextPrefixHash(pos,m);  GetNumOfPatSameSuffixHashFromPrefixSizeTable(targetTextSuffixHash); forcount value from 0 to number of patterns with the same suffix hash calculation do  GetPrefixHashFromPrefixValueTable(targetTextSuffixHash,patSize,count); ifprefix hash of target text and prefix hash from prefix value table are equal then  GetPathdexFromPrefixIndexTable(targetTextSuffixHash,patSize,count); ifTarget text and pattern text are equal then  UpdateDetectedPatternCount();  end if  end if  end for  end if
```  
**Algorithm 2** Wu-Manber algorithm  
Similar to the AC algorithm, the pattern-matching performance of the WM algorithm is also related to the memory space required by the algorithm and access overheads. In addition, an increase in the number of patterns represented by a SHIFT table also negatively affects the performance of the WM algorithm. Patterns with the same suffix hash value fall into the same address in a SHIFT table. An increasing number of the examined patterns also increases the number of patterns in the same address space in a SHIFT table. The algorithm has to sequentially compare patterns in the same address space in a SHIFT table and with the same prefix hash value with the target text to detect a match. As a result, the pattern-matching speed drops for large pattern datasets. Executing packet processing in shared memory with shorter access latency instead of global memory reduces the packet-processing time (Figure 11). As a result, the pattern-matching tests processing network packets in shared memory produce a higher throughput (Figure 12).  
Figure 11: Comparison of the packet-processing times obtained from the pattern-matching tests performed using the WM algorithm.  
While detecting patterns using the WM algorithm, threads act independently of access patterns. The values in the tables are placed according to the hash values of the patterns, and the hash values calculated by the different threads differ. This causes uncoalesced memory accesses. Also, the absence of any access pattern during pattern detection causes bank conflicts on shared memory.