# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 4 Conflict-Detection Algorithms Using GPU
### Enhanced Parallel Conflict-Detection Algorithm  
When a filter executes conflict detection, its number of comparisons represents the workload of that filter; therefore, we prearranged the order of each filter based on the number of comparisons required for that filter. In the GPCDA, each filter \(F_{s}\) in list \(T\) must be initially compared with all preceding filters in list \(T\). We changed the comparison policy in the EPCDA. For each filter in the EPCDA, \(F_{s}\) only needs to compare the filter set with the location behind \(F_{s}\). For example, filter \(F_{0}\) needs to be compared with \(n\)-1 filters behind it, and \(F_{1}\) needs to be compared with \(n\)-2 filters behind it. Consequently, the number of comparisons required for each filter decreases with its sequential order in the filter list. In this way, the conflict-detection process is not duplicated, and the concept is the same as the LPT algorithm's, in which tasks are executed based on the sorted order of execution time. Furthermore, we presorted the filters in \(T\) based on the SA prefix length. When the EPCDA performs a conflict detection for filters, each comparison process performs a large number of logical comparisons. The presorted order of filters ensures that the SA prefix length of each filter that is being compared does not exceed its own. This simplifies the logical comparison process and reduces the number of memory accesses. We could construct \(T^{\prime}=\{F^{\prime}_{0},\ \ldots,\ F^{\prime}_{n-1}\}\) as the list obtained after sorting \(T\).  
In the EPCDA, the filter dispatch order is the same as that of the method proposed in [39]. Figure 6 illustrates the EPCDA dispatch method. Initially, \(K\) filters \(F^{\prime}{}_{0}\)-\(F^{\prime}{}_{K-1}\) are dispatched to thread 0 through thread \(K-1\). Because the filters in \(T^{\prime}\) have been sorted based on the workload, the dispatch order of the next \(K\) filters is opposite to that of the former \(K\) filters to balance the workload of each thread. Thus, \(F^{\prime}{}_{K}\)-\(F^{\prime}{}_{2K-1}\) are dispatched sequentially from thread \(K-1\) through thread 0. Whenever the EPCDA dispatches \(2K\) filters, the former \(K\) filters are dispatched to threads in the order from thread 0 to thread \(K-1\). In contrast, the latter \(K\) filters are dispatched to threads from thread \(K-1\) to thread 0. Such a dispatch order ensures that for each \(2K\) filter, the workload of each thread will be nearly balanced. Even when the number of dispatched filters is less than \(2K\), it still achieves minimal difference in the workload of each thread. Algorithm 1 shows the algorithm for each thread to process filter conflict detection in the EPCDA, and Table 3 lists the notations used in Algorithm 1.  
Figure 6: Filters dispatch of the EPCDA.  
From the dispatch in the EPCDA, we observed that the numbers of comparisons required by each thread for performing conflict detection were very close. When \(n\) equals \(2K\), each thread must execute \(2K-1\) comparisons. The more balanced the workload, the smaller the maximum number of total comparisons performed by the threads. In other words, the total time required to execute the detection algorithm is reduced. This finding demonstrates that the EPCDA can improve parallelism performance.