## 3 Methods
### Optimization for Gather-GEMMs-Scatter  
Unlike 2D images, where computations can be performed by continuously sliding a convolution window, sparse convolution relies on mapping operations. A common implementation records the coordinates of non-zero inputs in a hash table with entries of the form \((key=coordinates,value=input\ index)\). After mapping, sparse convolution queries the hash table to retrieve the inputs associated with each kernel. These inputs are then rearranged to meet the continuity requirements for subsequent matrix multiplication. Once the computation is completed, the results need to be scattered back to their respective output positions. This entire process is referred to as the Gather-GEMMs-Scatter dataflow. Matrix multiplication is the core component of sparse convolution, and it takes up about 20-50% of the whole execution time [19]. However, the data orchestration process, which aims to make the data more regular, consumes a significant portion of the execution time, accounting for nearly half of it. Therefore, optimizing the Gather-Scatter operations can accelerate the overall execution time. Considering the parallelism of the modern CPU platform, we use SIMD to execute Gather-Scatter operations in parallel. As shown in Figure 5, SIMD technology utilizes vector registers or vector processors to perform the same operation on a batch of data simultaneously. Under the control of a single instruction, the vector processor can process multiple data elements at once, significantly improving computational efficiency and performance. This means more data can be processed within the same time on CPU. For sparse convolution, as shown in Figure 3, it is expected to perform matrix multiplication for each unique kernel weight to obtain partial sums, which are then added together to obtain the final result. During Gather and Scatter operations, the first step  
Figure 8: Prune operation overview. involves extracting the parts of the discontinuous point cloud data that are involved in the current kernel calculation and arranging them in a continuous sequence for the next operation (in the Scatter operation, the continuous data are placed back in their original position), as shown in Figure 9. In this step, data is read in batches of channel size and then switched to another position. Compared with scalar operation, the efficient utilization of SIMD operations allows for parallel acceleration along the channel dimension, enabling the simultaneous processing of multiple data points. This approach significantly enhances computational speed, optimizing performance in high-dimensional data processing tasks. In SIMD operations, channel-wise batched data are truncated based on the length of the vector register rather than reading one data point at a time from the cache or memory. In scenarios where the channel number is not an integer multiple of the SIMD vector register length, it is imperative to fetch data of the SIMD vector register length from the tail end of the batch rather than using the pad. This precaution prevents errors stemming from array out-of-bounds access, thereby maintaining the computation's integrity and accuracy. The detailed steps are outlined in Algorithm 1. Complexity Analysis: The original complexity was O(\(N^{2}\)) due to the need for nested two-layer for loops during the Gather and Scatter operations. After implementing SIMD rewriting, the number of iterations in the inner loop is significantly reduced, especially when the number of input and output channels is small (the number of iterations in the inner for loop is determined by these two channel counts). In this case, the inner loop iterations can be considered as constant relative to the outer loop iterations, leading to a time complexity that can be viewed as O(N). However, when the number of channels is large, the size restrictions of vector registers make it challenging to substantially reduce the number of iterations in the inner loop.