# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 4 Conflict-Detection Algorithms Using GPU
### General Parallel Conflict-Detection Algorithm  
During conflict detection, the matching process for each filter is independent. From the practical execution example in Section 3.2, during the programming stage we can assign a filter to several threads for execution. Figure 4 illustrates the proposed GPCDA architecture and its operating process. In Step 1, we copy the filter database from the host to the device. In Step 2, we sequentially assign the filter stored in the filter database to pre-allocated threads. Since the memory space required by the filter database is not large, we can store the filter database in a unified L1/texture cache (which is a read-only cache) to minimize memory access latency. In Step 3, each thread executes the detection algorithm independently and stores the conflict-detection results in the pre-allocated shared memory. In Step 4, each block collects the detection result reported by its associated thread and stores it in the device memory. In Step 5, all the detection results are sent back to the host through the device. We define the total execution time for conflict detection as the total time required to execute Steps 1 to 5.  
Suppose that \(i\) threads and \(j\) blocks are allocated. This means that \(i\times j=K\) threads are available for parallel computing. If \(n\) filters should execute conflict detection, each thread must execute \(\lceil n/K\rceil\) filter conflict detections. In the GPCDA, the filter dispatch order is based on the successive location in the filter database, such that threads can be assigned to execute sequentially. Assuming that \(n\) filters are stored in a filter database and denoted as list \(T=\{F_{0},\ \ldots,\ F_{n-1}\}\), \(K\) filters \(F_{0}\)-\(F_{K-1}\) are initially assigned as threads 0 to \(K-1\), and the next \(K\) filters, \(F_{K}\)-\(F_{2K-1}\), are also assigned as threads 0 to \(K-1\). Thus, each assignment order of \(K\) filters starts from thread 0 and ends at thread \(K-1\). Figure 5 illustrates how the filters in \(T\) are dispatched to \(K\) threads using the GPCDA. Because each filter must match other filters in \(T\), each thread should execute the detection algorithm twice when \(n=2K\), and the total number of matches is \(2(2K-1)\).  
Figure 4: Process flow of the GPCDA.  
We observed that the GPCDA might obtain a duplicated detection result when the above filters perform conflict detection. Assuming that filters \(f\) and \(g\) conflict, both \(f\) and \(g\) will detect each other while executing conflict detection [33]. Therefore, we changed the matching policy. For filter \(F_{s}\) in \(T\), we only needed to compare the filter set before \(F_{s}\), that is, filters \(F_{0}\)-\(F_{s-1}\). Consequently, it could prevent the duplicated detection problem and reduce the number of comparisons required by each filter. The reduction in the number of comparisons required by each filter indicates a reduction in time for the GPCDA to execute conflict detection. This creates a new problem. If we use the term \"the total number of filter comparison for each thread to execute\" to represent the workload of the threads, the workload of each thread will become unbalanced (Figure 5). For example, when \(n=2K\), thread 0 needs to execute \(K\) comparisons, whereas thread \(K-1\) needs to perform a comparison \(3K-2\) times. When the workloads between threads are unbalanced, some threads with less workload may finish the task earlier and become idle. However, threads in different blocks cannot access the same shared memory and support each other. Thus, the final detection results can only be returned to the host until the thread that \"finishes the last comparison\" reports its result. If the workloads among threads are balanced, thread idling and the total execution time of conflict detection can be reduced. The even distribution of the workload to threads is a key factor for improving the performance of parallelism.