# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 5 Results and Discussion
### Comparison of Performance for Different Workload Dispatch Methods  
In this subsection, we evaluate the effect of different workload dispatch methods on performance. We added two workload dispatch methods for comparison with the GPCDA and the EPCDA. The first comparison used the worst workload dispatch method. Suppose that \(K\) threads execute a computation. We divided \(n\) filters into \(K\) equal parts. The filters in each part were dispatched sequentially to the threads for execution. For example, thread 0 is responsible for performing conflict detection of filters 0 to \(n/K-1\), thread 1 is responsible for filters \(n/K\) to \(2n/K-1\), and so on, until thread \(K-1\) performs conflict detection of filters \(((K-1)n)/K\) to \(n-1\). When the poorest workload dispatch method was used, we observed a significant difference in the total number of comparisons between threads 0 and \(K-1\), leading to the most significant workload imbalance. The second comparison method involved using the dispatch method of the shortest processing time (SPT) algorithm in the EPCDA (denoted EPCDA\({}_{\text{R}}\)). The dispatch method in the SPT algorithm is the opposite of that in the LPT algorithm. Each filter \(F_{s}\) was compared with filters \(F_{0}\)-\(F_{s-1}\). Here, we address the EPCDA with respect to the difference in performing conflict detection using the LPT and SPT algorithms. First, if the number of filters is a multiple of \(K\), regardless of whether the LPT or the SPT algorithm is used, each thread requires the same total number of comparisons. However, if the number of filters is not a multiple of \(K\), a difference exists. This trend can be explained using Figure 8. When the dispatched four threads performed conflict detection of filters \(F_{0}\)-\(F_{8}\), the filters dispatched in the LPT algorithm experienced a significantly more balanced workload than those in the SPT algorithm. The total number of comparisons for both algorithms was 9. For example, \(F_{0}\) and \(F_{7}\) required eight and one comparisons, respectively, in thread 0 (\(F_{8}\) did not need an additional comparison), and \(F_{2}\) and \(F_{5}\) required six and three comparisons, respectively, in thread 2. However, when filters were dispatched through the SPT algorithm, the workload in thread 0, which reached 15 (needing 0, 7, and 8 comparisons) was higher than that of the other threads. Workload imbalance increased the total execution time for conflict detection. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Databases**} & \multicolumn{3}{c}{**Statistics**} & \multicolumn{3}{c}{**Average Detection Time (\(\upmu\)s)**} \\ \cline{2-6}  & **Number of Filters** & **Number of Conflicts** & **Host** & **GPCDA** & **EPCDA** \\ \hline ACL1 & 99,341 & 1,144,326 & 247.69 & 17.78 & 7.35 \\ ACL2 & 74,194 & 10,851,664 & 128.47 & 21.45 & 8.78 \\ ACL3 & 99,542 & 25,600,127 & 266.86 & 33.85 & 13.92 \\ ACL4 & 99,121 & 14,013,339 & 262.43 & 29.82 & 12.40 \\ ACL5 & 98,098 & 15 & 236.45 & 17.47 & 7.35 \\ FW1 & 87,986 & 207,072,436 & 227.10 & 70.82 & 21.79 \\ FW2 & 96,092 & 417,272,543 & 242.96 & 33.67 & 13.27 \\ FW3 & 84,472 & 227,534,381 & 207.72 & 74.92 & 20.04 \\ FW4 & 83,811 & 144,579,158 & 209.64 & 53.26 & 19.61 \\ FW5 & 83,677 & 333,717,457 & 183.99 & 65.89 & 19.65 \\ IPC1 & 99,284 & 49,864,378 & 263.68 & 35.90 & 15.42 \\ IPC2 & 100,000 & 308,440,932 & 279.19 & 52.15 & 18.91 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Performance evaluation for synthetic databases under (512, 8) allocation. Second, for the number of memory access times, after the dispatch of the LPT algorithm, while processing the first conflict detection in each thread, each thread wrote the compared filters in the cache, owing to a cache miss. Assuming that the cache size is sufficiently large to store all compared filters, the next conflict-detection process could be immediately performed because the filters to be compared were already written to the cache.