# Parallel Eclipse-Aware Routing on FPGA for SpaceWire-Based OBC in LEO Satellite Networks
## 3 Proposed Method
### IP Design for Eclipse-Aware Routing on FPGA with Parallelization Achieved Through Pipelining  
In this study, it was important to use both PS and PL to reduce the calculation time to ensure real-time performance. For this purpose, it is very important to reduce the calculation time using pipelining in the PL. For pipelining, the KSP algorithm was implemented in the PS area of the FPGA to measure which function takes the longest calculation time. Figure 2 is a table showing the results. Total execution time (KSP) is the total execution time of the KSP function, total execution time (DFS) is the total execution time for the DFSalgorithm to be performed within the KSP algorithm, neighbor expansion time is the time taken for the path to extend, backtracking time is the time to backtrack, pop & visit check time is the time to check whether the path has reached its destination, and sort & K-paths selection time is the time to sort and K stored results by reaching the destination from the DFS function. According to the above results, it was decided to run the KSP algorithm in a PL including the most time-consuming DFS algorithm and the sorting and selection of K results and pipelining some of the processes. To enable pipelining, the KSP algorithm was first converted into an intellectual property (IP) core, which is a reusable, standalone hardware block that can be instantiated within the FPGA fabric and interfaced through standard AXI buses. Figure 3 depicts the structural layout of the KSP and EAR algorithms executed across the processing-system (PS) and programmable-logic (PL) regions. Although its basic operational flow mirrors the PS-side algorithm diagram introduced in Figure 1, the KSP algorithm has been encapsulated as a dedicated IP core to run in the PL. Within this IP, the color-highlighted sections denote regions where pipelining has been applied to shorten execution time. Figure 4 presents a schematic overview of the pipelined KSP algorithm operating in the PL. Unlike the original implementation--whose computations were performed sequentially as in Order 1--the accelerated version leverages pipelining to launch a new operation every clock cycle, enabling parallel execution and dramatically reducing overall runtime.  
```
eclipseMatrix[time][nodes] paths[]: result of KSP sampleTime NoE, TxE, RxE nTimeStep
```  
Output minPath
1. InitializeConstants: NoE, TxE, RxE
2. InitializeenergyTable[pathCount][maxLength] = 0
3. For each pathIdx from 0 to topPath \(-\) 1; currentPath \(<\) paths[pathIdx];
5. For saddx from 0 to length(currentPath) \(-\) 1; currentSat \(<\) currentPath[saddx]
7. If eclipseMatrix{timeIndex}[currentSat] == 1; (startIdx, endIdx) \(<\)= locateEclipseInterval(eclipseMatrix, timelndex, currentSat)
10. eclipseDuration = (endIdx - startIdx) \(\times\) sampleTime;
11. txEstimate \(<\)= round(eclipseDuration \(\times\) random(0.01, 0.1));
12. ComputeEnergy Consumption:
13. baseEnergy \(<=\) eclipseDuration \(\times\) NoE;
14. commEnergy \(<=\) (txEstimate + 1) \(\times\) (TxE + RxE)
15. energyTable[pathIdx][saddx] \(<\)= baseEnergy + commEnergy
16. End if
17. End for
18. End for
19. ComputeMaximumEnergyConsumition per Path:
20. For each pathIndex from 0 to topPath \(-\) 1;
21. maxEnergyPerPath[pathIdx] \(<\) maximum value in
22. energyTable[pathIdx]);
23. End for
24. SelectOptimalPath:
25. minPath \(<=\) index of Minimum value in maxEnergyPerPath
27. Return minPath;
Figure 2: PS area profiling results of existing KSP algorithm.