Evaluating FPGA-based convex optimization methods for onboard low-thrust trajectory guidance

The present work is focused on deploying in an FPGA an onboard guidance algorithm that employs convex approaches to minimum fuel space trajectory problems. An Earth to Mars case with 100 nodes is considered using the interior point solver ECOS. The Zedboard is the selected device. First, an algorithm is developed to solve the problem. Next, a profile sequence is carried out, from which two functions are elected to integrate the hardware. One is responsible for a numeric factorization of a sparse matrix. The other performs matrix-vector multiplications. These are chosen due to their impact on the application execution time. The original problem is reduced as a consequence of the limited memory resources of the board. Therefore, depending on the workspace of variables the onboard guidance algorithm presents, a device of appropriate resources shall be selected. The results from the hardware implementation exhibit a decrease in performance efficiency when compared to its software application. In fact, algorithms developed for software-oriented systems might display nondeterministic and data-dependent behaviors that are incompatible with FPGA optimization techniques. These, contrarily, require deterministic and data-independent cycles to take advantage of the parallelism features of FPGAs. In the ECOS case, significant changes must be made to the functions' structure to ensure compatibility with the concurrent procedures. Moreover, to fully exploit hardware performance, a workaround is to deploy fitting sections of the algorithm that enclose multiple successive operations with high execution time, instead of their separate implementation. This mitigates the additional cycles for the transfer and address of data in the FPGA. This thesis also highlights the need to apply single-floating point precision in the hardware designs of interior point methods. This is a consequence of the vast dynamic range of numbers these schemes comprehend. Finally, when correctly assembled, the performance gap between the original software application and the FPGA implementation should scale with the problem size.

Il presente lavoro si concentra sull'implementazione in un FPGA di un algoritmo di guida a bordo che utilizza approcci convessi ai problemi di traiettorie nello spazio a minimo consumo di carburante. Viene considerato un caso Terra-Marte con 100 nodi utilizzando il solutore de punto interno ECOS. Il dispositivo selezionato è la Zedboard. A seguito dello svilupo de un algoritmo per risolvere il problema, è stata eseguita una sequenza di scrematura, dalla quale sono stati selezionati due funzioni da integrare nell'hardware. Una è responsabile della fattorizzazione di una matrice sparsa, l'altra esegue moltiplicazioni matrice-vettore, entrambe scelte a causa del loro impatto sul tempo di esecuzione. Il problema originale è stato ridotto a causa delle risorse limitate di memoria della scheda. Pertanto, a seconda dello spazio di lavoro delle variabili presentato dall'algoritmo di guida a bordo, viene selezionato un dispositivo con risorse adeguate. I risultati dall'implementazione hardware mostrano una diminuzione dell'efficienza delle prestazioni rispetto alla sua applicazione software. Infatti, gli algoritmi sviluppati per sistemi orientati al software potrebbero mostrare comportamenti non deterministici e dipendenti dai dati, che sono incompatibili con le tecniche di ottimizzazione FPGA. Queste richiedono cicli deterministici e indipendenti dai dati per sfruttare la parallelizzazione degli FPGA. Nel caso di ECOS, è necessario apportare modifiche significative alla struttura delle funzioni per garantire la compatibilità con le procedure concorrenti. Inoltre, per sfruttare appieno le prestazioni dell'hardware, una soluzione alternativa sarebbe implementare sezioni dell'algoritmo che includono molteplici operazioni successive con un alto tempo di esecuzione, invece di implementarle separatamente. Questo mitiga i cicli aggiuntivi per il trasferimento e l'indirizzamento dei dati nell'FPGA. Questa tesi sottolinea anche la necessità di applicare la precisione dei numeri a virgola mobile singola nei progetti hardware dei metodi del punto interno. Questo è una conseguenza della vasta gamma dinamica di numeri compresa in questi schemi. Infine, quando correttamente assemblata, la differenza di prestazioni tra l'applicazione software originale e l'implementazione FPGA dovrebbe essere proporzionale alla dimensione del problema.