## 3 Methodology  
### GPU Mapping Implementation of SAR-SIFT Algorithm  
1. GPU Mapping for Scale Space Construction  
The 2D Gaussian kernel is a known separable kernel, meaning that convolution with a 2D Gaussian kernel is equivalent to two consecutive 1D convolutions, one along the rows and the other along the columns. The exponentially weighted ratio used in SAR-SIFT can also be separated into mean convolution along the columns and exponential convolution along the rows. It has been observed that leveraging this separability property can significantly enhance performance in GPU convolution operations. Therefore, we have adapted the NVIDIA kernel for 2D separable convolution to construct the SAR-SIFT ratio gradient convolution results of each scale space in parallel. The SAR-SIFT algorithm computes convolution results for SAR images by constructing mean and exponential convolution kernels at different scales, and then calculates the ratio gradient for each scale based on the convolution results. Thus, in the process of constructing the SAR-SIFT scale space, the natural order of kernel invocations is as shown in Algorithm 1 below. ```
For all scales from 1 to S do  Calculate the mean convolution kernel of the current scale;  Calculate the current scale exponential convolution kernel;  Using GPU to perform convolution operation;  Calculate the ratio gradient of the current scale; End for
```  
**Algorithm 1**The natural order of kernel invocations  
All scales are convolved one by one using GPU. For each of these convolutions, a unique kernel call must be made to use the correct number of blocks to cover the entire image at a specific scale. When each kernel is called, the code corresponding to the kernel function is transferred to the GPU. The number of read blocks requested is initialized, and convolution at a specific scale level is started. Each thread block can access the unique variable \(blockIdx\) that identifies the block. The input of the kernel is the original SAR image, and the output of the kernel is the convolution image corresponding to the specific scale under consideration and the corresponding ratio gradient result. Use of parallel convolution algorithm \(blockIdx\) and input images and generate output. After the kernel execution is completed, the next dimension will be considered. In the above process, parallelism is only exploited within each convolution for each scale. On the other hand, parallelism between scales and a combined kernel can be utilized. One of the primary challenges in designing such a combined kernel is maintaining a fixed grid size, ensuring that all convolutions for various scales operate with the correct inputs and outputs. Identifying a virtual single grid within the combined grid is crucial and must be achieved with minimal code overhead. All thread blocks executing convolutions in Algorithm 1, regardless of their scale space level, execute the same convolution code but with different inputs, outputs, and parameters. We leverage this property to assimilate all levels of thread blocks within a single combined kernel. The total number of blocks \(N_{COMBINED}\) for the new combined kernel depends on how a single kernel is laid out. The optimal placement strategy is to minimize the rectangular region required to enclose all thread blocks since CUDA (Compute Unified Device Architecture) kernels can only be invoked with a rectangular grid. Maintaining the structure and shape of a single kernel grid within the combined kernel is crucial, as the kernel code must be able to identify its original kernel to recognize the correct input-output (IO) parameters and define and use modified versions of variables \(blockIdx\) to compensate for offsets introduced by kernel combination. To initiate the selection of IO parameters, some additional code must be placed at the beginning of the combined kernel function. During kernel invocation, all necessary IO parameters for the original kernels must be passed.