# GPU-Accelerated Eclipse-Aware Routing for SpaceWire-Based OBC in Low-Earth-Orbit Satellite Networks
## 3 Proposed Method
### BFS-Based K-Shortest Path Algorithm
In contrast, the CSR method converts graph connectivity information into a continuous array format, making it an optimized graph representation for efficient execution on GPUs [24]. In CPU implementations, graphs are typically stored using a 2D vector structure, where each node maintains a variable-sized vector for its adjacency list. However, this approach can lead to inefficient memory access patterns when performing searches on a GPU. Specifically, since each node's adjacency list varies in size, memory fragmentation occurs, and the parallel search process suffers from random memory access, resulting in inevitable performance degradation [25]. To address this issue, the CSR (Compressed Sparse Row) technique is applied, converting the graph into three contiguous arrays, optimizing it for efficient memory access in a GPU environment. In the CSR format, a graph is stored using three arrays, as illustrated in Figure 4. The h_offsets array stores the starting position of each node's adjacency list, allowing quick determination of where a specific node's adjacency list begins in the h_edges array. The h_edges array contains all adjacency lists in a contiguous format, storing the destination nodes of all edges, so scanning from h_offsets[i] to h_offsets[i + 1] enables efficient retrieval of all adjacent nodes for a given node. The h_weights array, maintaining the same order as h_edges, stores the edge weights, ensuring quick access to the weight information corresponding to each adjacent node. By applying CSR transformation, the memory inefficiencies and challenges of parallel search encountered in the traditional adjacency list method are resolved, enabling fast and optimized path searching in a GPU environment. ### Configuration of the CUDA Kernel

To parallelize KSP search, this study proposes a CUDA-based BFS search method. In conventional CPU-based BFS search, candidate paths must be expanded sequentially, leading to increased search time as the number of nodes or K grows. In contrast, by leveraging CUDA, multiple candidate paths can be expanded in parallel, significantly improving search speed. CUDA (Compute Unified Device Architecture) is a parallel computing platform and API developed by NVIDIA, designed to efficiently handle large-scale computations by utilizing GPUs. Unlike traditional CPU computations, which execute tasks sequentially across a limited number of cores, GPUs leverage thousands of cores to perform parallel processing, making them highly effective for graph-based computations such as BFS search [26]. In this study, CUDA is employed to parallelize KSP search, enabling a more efficient exploration process compared to conventional CPU-based methods. The overall workflow of the proposed method can be explained using the block diagram presented in Figure 5. Similar to the CPU-based approach, the process consists of three main stages: graph initialization, KSP search, and energy consumption calculation. First, the CPU reads the graph data, converts it into the CSR format as previously described, and transfers it to the GPU. In the KSP search stage, instead of performing sequential expansion, a CUDA kernel is executed, enabling parallel expansion of candidate paths. Each thread is responsible for handling a single candidate path, checking its adjacent nodes, and generating new candidate paths. Finally, the eclipse state and energy consumption of

Figure 4: CSR format conversion example. the satellites are calculated in a similar manner to the CPU-based approach, and the most optimal path is selected. A more detailed execution process follows the pseudo code in Algorithm 3. The CUDA-based BFS search operates similarly to the CPU-based BFS, but the key difference is that candidate path expansion is performed in parallel. In CPU-based BFS, as shown in Figure 3, paths are expanded one at a time, causing the computation time to increase exponentially as the number of candidate paths grows. In contrast, during CUDA kernel execution, each candidate path is expanded in parallel across multiple threads.