# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 6 Conclusions  
In this study we applied GPUs to conflict-detection algorithms, and developed the GPCDA and the EPCDA, which can accelerate conflict detection through parallel computing in GPUs. Based on the simulation experiment, we found that the GPCDA and the EPCDA performed conflict detection up to 33.7 times faster than the CPU, regardless of the type and size of the filter databases; this was particularly evident when the number of allocated threads for parallel computing became large. We also observed that for the same total number of threads, different numbers of allocated blocks and threads significantly influenced the parallel efficiency. We analyzed the factors affecting the parallel efficiency, which may guide GPU utilization in other applications.  
Figure 10: Limitation of parallel computing.  
If the workload between threads was unbalanced, different threads required different computation times. This may have caused some threads to be idle because of a smaller workload, whereas threads with a larger workload spent more time, increasing the total parallel computing. Therefore, the workload balance was an essential factor that influenced parallel performance. Unfortunately, the literature reports that dispatching tasks with different execution times to multicores with the same computing capability and achieving optimized workload balance is an NP-complete problem. Thus, we developed a near-optimum workload balance mechanism in the EPCDA, such that the workload among threads could approach a balance and maximize the performance of parallel computing. Based on the simulation experiment, we observed different performances for different workload dispatch methods. Using the EPCDA, even though we used fewer threads for parallel computing, it achieved the same performance as the GPCDA, which used more threads for parallel computing; thus, the hardware cost was reduced.  
Finally, when the number of filters was large, the EPCDA still maintained good performance, with a filter database size of 100K. In the EPCDA, each filter spent 22 us, at most, to process conflict detection; this was 9.4 to 33.7 times faster than using only a CPU. Therefore, the EPCDA is suitable for applications with frequent filter-database updates. The limitations and future research directions of this study are as follows. First, the detection speed can be increased by improving the GPU memory access efficiency, such as by minimizing non-coalesced memory accesses and bank conflicts. Second, in this study, we focused on analyzing the critical procedure in 5D conflict detection, and balancing the workload of GPU threads. The proposed algorithms were not designed for a specific GPU architecture/model. For a specific GPU architecture/model, our proposed algorithms can be modified to achieve better performance by taking advantage of hardware features. Third, this study assumed that conflict detection is executed on a single-GPU platform. For a heterogeneous multi-GPU platform, the workload balancing problem becomes much more complicated and the communication cost between GPUs should be taken into account when designing a conflict-detection algorithm.  
Conceptualization, C.-L. and Y.-C.C.; data curation, G.-Y.L.; formal analysis, G.-Y.L.; investigation, G.-Y.L.; methodology, G.-Y.L.; project administration, C.-L.L. and Y.-C.C.; resources, Y.-C.C.; software, G.-Y.L.; supervision, C.-L.L. and Y.-C.C.; validation, G.-Y.L.; writing--original draft, G.-Y.L.; writing--review and editing, C.-L.L. and Y.-C.C. All authors have read and agreed to the published version of the manuscript.  
This research was funded by the Ministry of Science and Technology of Taiwan (MOST 104-2221-E-182-005 and 110-2221-E-182-010) and Chang Gung Memorial Hospital (BMRP 942).  
Not applicable.  
The authors declare no conflict of interest.