# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 2 Related Work
### CUDA Architecture and Programming Model  
In 2007, NVIDIA introduced the Compute Unified Device Architecture (CUDA), which provides a platform for developing parallel computations on GPUs. The CUDA defines parallel thread execution and instruction set architecture so that GPU cores in the CUDA can process a specific segment of a parallel program simultaneously. The CUDA provides libraries and toolkits for developers, and version 11.6.2 [36] is currently the most updated. Following the evolution of hardware from version 1.0 to version 8.7, the GPU architecture provides increased GPU cores and computing power to improve GPU computing efficiency. The streaming processor (SP) is the basic processing unit. Many SPs in a GPU can perform computations simultaneously, and several SPs attached to other units, such as memory, computing units, and control units, can form a streaming multiprocessor (SM). An SM is the basic hardware unit for executing threads in the CUDA. CUDA-capable GPUs have a memory hierarchy, as shown in Figure 2. The GPU architecture exposes the following memory units.  
1. Registers: These are private to each thread, suggesting that registers assigned to one thread are invisible to other threads.
2. L1/Shared memory (SMEM): Every SM has a fast, on-chip scratchpad memory that can be used as an L1 cache and SMEM. All threads in a CUDA block can share shared memory, and all CUDA blocks running on a given SM can share the physical memory resources provided by the SM.
3. Read-only memory: Each SM has an instruction cache, constant memory, texture memory, and a read-only cache.
4. L2 cache: The L2 cache is shared across all SMs; therefore, every thread in every CUDA block can access this memory.
5. Global memory: As with the L2 cache, all threads can read and write this memory, but it is slower to access than other memories. This memory can be used to exchange data between the GPU and the CPU.  
A CUDA program contains two parts: the host function and device function, which are executed on the CPU and the GPU, respectively. Initially, the host function copies the data required by the device function to the device memory of the GPU through PCI-express and executes the device function on the GPU. The host then retrieves the results from the device memory when GPU computation is performed. The minimum execution unit in the device is a thread; several threads form a block, and several blocks form a grid. Before executing a program, program developers can set the number of threads and blocks based on the purpose of the computation. The maximum number of threads allowed within a block varies, depending on the hardware version. Up to 1024 threads are allowed in the current version. While the device is in execution, it assigns blocks to the SMs for computation block by block, and threads in the block are executed in groups based on the warps. Figure 3 illustrates an actual execution in the CUDA. Each warp consists of 32 threads, and the  
Figure 2: Memory hierarchy in GPUs.  
threads in each warp perform computations simultaneously. When an SM provides more warps, more threads can be executed simultaneously. The maximum number of warps supported by an SM varies, depending on the hardware specification.  
Each filter is mutually independent when executing conflict detection; therefore, we can assign the task of conflict detection to the device for execution. The task is then distributed to the threads for computation to improve performance through parallel computing. However, this distribution may reduce parallel computing performance if the workload distribution is imbalanced. For example, when more workload is assigned to fewer threads, the remaining threads accomplish the work earlier because of fewer assigned tasks, and these threads become idle. Therefore, evenly distributing the workload to threads is a critical issue in parallel computing.