[en] Abstract: Many of the most recent publications in the embedded MPC field choose to use first-order algorithms as a solution to the complexity of accelerating second-order algorithms in systems with restricted computing resources. Thus, the purpose of this project consist on evaluating the response of these first order algorithms and compare their performance with second-order algorithms to have consistent criteria to design specific accelerators optimized in the development of SoCs with application to the high performance embedded MPC. To aim this objective, the first part of the text focuses on explaining a background needed to understand the approach of the optimization algorithms in the solution of a reformulated MPC problem arising from a state-space model. In this chapter, definitions such as Shift and Delta discretisation, System Variable and Dynamics Stacking, and Sparse and Dense formulation are explained. Once the related background is presented, it is analysed in detail the application to the MPC of the most current and efficient first order algorithms, making a study of the proposals published in recent years. In this section, definitions such as optimality, stopping conditions and convergence will be taken into account. After this analysis, the application of these algorithms will be adapted to different MPC formulation options where it will be evaluated their computational performance in different scenarios. Lastly, the results obtained of the previous evaluation will be compared with the performance of the second order algorithms, particularly using a simplified Interior Point which it is optimised for an embedded MPC implementation. This comparison will allow to take appropriate design decisions in the implementation of MPC in embedded systems considering aspects such as hardware simplicity, computational performance and numerical characteristics.

[eu] Laburpena: MPC txertatuaren arloko argitalpen berrienetako askok lehen mailako algoritmoak erabiltzen dituzte baliabide informatiko mugatuak dituzten sistemetan bigarren mailako algoritmoen azelerazioaren konplexutasunari aurre egiteko. Beraz, proiektu honen helburua lehen mailako algoritmo horien erantzuna ebaluatzea eta haien errendimendua bigarren mailako algoritmoekin alderatzen da. Horrela, eraginkortasun handiko MPC kontrolagailu txertatuak gauzatzeko SoC arkitektura berriak diseinatzeko beharrezkoak diren azeleragailuak diseinatzeko irizpideak lortu nahi dira. Helburu hori lortzeko, lan honen lehen atalean, egoera-espazioko eredutik sortzen den birformulatutako MPC problemen ebazpenerako beharrezko diren optimizazioalgoritmoen planteamendua ulertzeko beharrezkoak diren aurrekariak azaltzen dira. Kapitulu honetan, zenbait definizio azaltzen dira, hala nola Shift eta Delta diskretizazioa, aldagaien eta sistemen dinamikaren pilaketa, eta formulazio trinko eta sakabanatuak. Aurrekariak aurkeztu ondoren, lehen mailako algoritmo berri eta eraginkorrenak MPC-aren arloan nola aplikatu diren aztertzen da, horretarako azken urteetako argitalpen zientifikoetan agertutako proposamenak aztertuz. Atal honetan optimizazioa, bukaera-baldintzak eta konbergentzia bezalako kontzeptuak kontuan hartuko dira. Ondoren, algoritmo horien aplikazioa MPCren formulazio-aukera desberdinetara egokituko da, haien errendimendu konputazionala hainbat egoera esanguratsuetan ebaluatuz. Azkenik, aurreko ebaluaziotik lortutako emaitzak bigarren mailako algoritmoen errendimenduarekin konparatuko dira, bereziki sistema txertatuetan erabiltzeko optimizatua izan den IP (Interior Point) algoritmo sinplifikatu bat erabilita, MPC txertatua ezartzeko optimizatuta dagoena. Konparazio horri esker, diseinu-erabaki egokiak hartu ahal izango dira sistema txertatuetan MPCa ezartzeko, ondorengo alderdi hauek kontuan hartuta: hardwarearen sinpletasuna, errendimendu konputazionala eta zenbakizko ezaugarriak.