# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 5 Results and Discussion
### Analysis of Parallelism Efficiency  
In this subsection, we discuss the efficiency of parallelism for a fixed total number of threads using different (_ntThread_, _nBlock_) allocations for parallel computing. Here, we compare the efficiency of the (256, 8) and (512, 4) allocations. Tables 5 and 6 list the average required times to execute conflict detection by a filter using the Host, the GPCDA, and the EPCDA, with databases of the lowest and highest numbers of detected conflicts for  
Figure 8: Filter dispatch for different dispatch methods (LPT and SPT). Figure 9: Comparison of workloads. the three filter database types. The average required times for a filter to execute conflict detection in the GPCDA and the EPCDA were several times lower than that in the Host alone, regardless of the condition of the smallest or largest number of conflicts. Regardless of whether the GPCDA or the EPCDA was used, the time required for each filter to execute conflict detection under the \((256,8)\) allocation was always shorter than that under the \((512,4)\) allocation. This trend indicates that for the same total number of threads, the more threads in a block, the worse the parallel performance. Through analysis with NVIDIA Visual Profiler [42], two major factors that affect parallelism efficiency are \"stalled for memory dependency\" and \"stalled for synchronization\". \"Memory dependency\" is mainly attributed to the additional stall caused by the data dependency of two consecutive instructions, whereas \"stalled for synchronization\" is mainly attributed to the _syncthreads( ) instruction in the CUDA. Recall that threads in a block use a warp as a unit for hardware to execute parallel computing, and threads in the same block access the data in the same shared memory. When threads in the same warp are executed, the CUDA invokes the _syncthreads( ) instruction to ensure data consistency while the threads \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Database**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{6}{c}{**Filter Size**} \\ \cline{3-7}  & & **5K** & **10K** & **15K** & **20K** & **30K** \\ \hline \multirow{4}{*}{ACL2} & Host & 8.69 & 18.19 & 26.16 & 34.83 & 50.10 \\  & GPCDA (256, 8) & 1.88 & 3.34 & 4.51 & 6.60 & 9.20 \\  & GPCDA (512, 4) & 2.42 & 4.22 & 5.65 & 8.16 & 11.26 \\  & EPCDA (256, 8) & 0.87 & 1.87 & 2.54 & 3.29 & 4.36 \\  & EPCDA (512, 4) & 1.00 & 2.18 & 3.02 & 3.86 & 5.16 \\ \hline \multirow{4}{*}{FW2} & Host & 7.70 & 16.80 & 25.08 & 33.41 & 49.57 \\  & GPCDA (256, 8) & 1.80 & 3.69 & 5.35 & 6.46 & 9.92 \\  & GPCDA (512, 4) & 2.38 & 4.79 & 6.68 & 7.98 & 12.62 \\  & EPCDA (256, 8) & 0.90 & 1.78 & 2.25 & 2.81 & 4.32 \\  & EPCDA (512, 4) & 1.04 & 2.04 & 2.55 & 3.21 & 4.89 \\ \hline \multirow{4}{*}{IPC2} & Host & 8.64 & 18.57 & 27.73 & 36.94 & 55.20 \\  & GPCDA (256, 8) & 3.28 & 5.12 & 8.87 & 10.31 & 17.48 \\ \cline{1-1}  & GPCDA (512, 4) & 3.40 & 5.54 & 9.37 & 11.25 & 18.51 \\ \cline{1-1}  & EPCDA (256, 8) & 1.72 & 2.97 & 3.57 & 4.43 & 6.41 \\ \cline{1-1}  & EPCDA (512, 4) & 1.95 & 3.35 & 3.97 & 4.98 & 7.42 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Average detection time (\(\upmu\)s) for databases with most conflicts in each category.