Exploiting Parallelism in a QPALM-based Solver for Optimal Control

Cet article présente une implémentation optimisée en C++ de l'algorithme QPALM-OCP pour le contrôle optimal, qui exploite la parallélisation et la vectorisation des étapes indépendantes du problème pour améliorer les performances par rapport à la méthode QPALM originale.

L'essentiel

Imaginez que vous êtes le chef d'orchestre d'une très grande symphonie, mais au lieu de jouer de la musique, vous devez résoudre un problème mathématique complexe pour piloter une voiture autonome ou un robot. Ce problème s'appelle un problème de contrôle optimal.

En termes simples, c'est comme essayer de trouver le chemin parfait pour aller d'un point A à un point B, en évitant tous les obstacles, tout en utilisant le moins de carburant possible, et ce, en une fraction de seconde.

Voici comment les auteurs de cet article ont amélioré la vitesse de résolution de ce problème, expliqué simplement :

1. Le Problème : Une Tâche Gigantesque

Pour faire ce calcul, l'ordinateur doit regarder le futur pas à pas (comme si vous regardiez 100 cases devant vous sur un échiquier). Traditionnellement, les ordinateurs traitent ces cases une par une, comme un ouvrier qui pose des briques une à une sur un mur très long. C'est efficace, mais lent.

2. La Solution : Le "Super-Héros" Parallèle

Les chercheurs ont pris un outil existant (appelé QPALM) et l'ont transformé en une équipe de super-héros. Au lieu d'avoir un seul ouvrier, ils en ont mis plusieurs pour travailler en même temps. Ils ont utilisé deux astuces principales :

Astuce A : La "Boîte à Outils Compacte" (Vectorisation)

Imaginez que vous devez peindre 100 petits tableaux.

• La vieille méthode : Vous prenez un pinceau, vous peignez le tableau 1, vous le posez, vous prenez le pinceau, vous peignez le tableau 2...
• La nouvelle méthode (SIMD) : Les chercheurs ont créé un pinceau géant avec 4 ou 8 poils. Ils peuvent peindre 4 tableaux en même temps avec un seul mouvement.

Pour que cela fonctionne, ils ont réorganisé la façon dont les données sont rangées dans la mémoire de l'ordinateur. Au lieu de ranger les tableaux les uns derrière les autres, ils les ont entrelacés (comme un jeu de cartes où les couleurs sont mélangées) pour que le pinceau géant puisse les attraper facilement. C'est ce qu'ils appellent le format de stockage "compact".

Astuce B : L'Équipe de 8 Ouvriers (OpenMP)

Même avec un pinceau géant, si le mur est trop long, un seul pinceau ne suffit pas. C'est là qu'intervient la deuxième astuce : le parallélisme.
Imaginez que vous avez une équipe de 8 ouvriers (les cœurs de votre processeur). Au lieu de les faire travailler sur le même mur, vous divisez le mur en 8 sections. Chaque ouvrier peint sa section simultanément.

• Si le problème est petit, cela ne sert à rien (les ouvriers se marchent sur les pieds).
• Mais si le problème est énorme (comme piloter un robot complexe), cette équipe de 8 permet de finir le travail beaucoup plus vite.

3. Les Résultats : Une Vitesse Éclair

Les chercheurs ont testé leur nouvelle méthode sur des problèmes classiques, comme un système de masses et de ressorts (un peu comme un train de wagons reliés par des élastiques).

• Résultat : Leur nouvelle version est jusqu'à 65 fois plus rapide que l'ancienne méthode pour les gros problèmes.
• Pourquoi c'est important ? Dans le monde réel (voitures autonomes, drones), les décisions doivent être prises en quelques millisecondes. Si le calcul est trop lent, le robot ne peut pas éviter un obstacle à temps. Grâce à cette accélération, les robots peuvent être plus sûrs et réagir plus vite.

En Résumé

C'est comme passer d'une course à pied solitaire à un relais avec une équipe de champions, en utilisant des chaussures qui vous permettent de courir sur 4 pistes à la fois. Les chercheurs ont pris un algorithme déjà intelligent, l'ont habillé d'une tenue de course adaptée aux processeurs modernes, et ont prouvé qu'il pouvait gagner la course contre tous les autres concurrents.

Cela signifie que demain, les robots et les voitures autonomes pourront prendre des décisions plus complexes, plus rapidement, et de manière plus sûre.

Résumé technique

Voici un résumé technique détaillé de l'article « Exploiting Parallelism in a QPALM-based Solver for Optimal Control », structuré selon vos demandes.

1. Problématique

Le papier aborde la nécessité de résoudre efficacement des problèmes de commande optimale linéaire-quadratique (OCP), qui sont au cœur d'applications temps réel telles que la commande prédictive linéaire (MPC) et l'estimation sur horizon glissant (MHE). Ces applications, souvent déployées dans des environnements embarqués contraints, exigent des solveurs de programmation quadratique (QP) extrêmement rapides.

L'article se concentre sur l'optimisation de l'algorithme QPALM-OCP, une spécialisation récente du solveur QPALM (basé sur la méthode du lagrangien augmenté) conçue spécifiquement pour les OCP. Bien que la version précédente [6] ait déjà amélioré la gestion des contraintes d'égalité et l'efficacité des résolutions linéaires internes, il reste un potentiel significatif à exploiter pour réduire le temps d'exécution en tirant parti de la structure spécifique des problèmes de contrôle optimal et du matériel moderne.

2. Méthodologie

Les auteurs proposent une implémentation C++ optimisée qui exploite deux niveaux de parallélisme pour accélérer le solveur :

A. Structure du problème et algorithme de base

Le problème OCP est formulé comme un QP standard avec des contraintes d'égalité (dynamique linéaire) et d'inégalité (contraintes sur les états et les entrées). L'algorithme QPALM-OCP résout ce problème via une méthode de Newton semi-lisse (semismooth Newton) à l'intérieur d'une boucle de lagrangien augmenté.
La clé de l'optimisation réside dans la résolution du système linéaire de Newton (équation 6 dans le papier). La matrice hessienne généralisée $H_k(x)$ possède une structure bloc-diagonale, où chaque bloc correspond à une étape (stage) du horizon de contrôle. Cette indépendance entre les étapes est le point de départ de la parallélisation.

B. Parallélisme Vectoriel (SIMD)

Pour exploiter les instructions SIMD (Single Instruction, Multiple Data) des processeurs modernes (AVX-512) :

• Format de stockage compact : Les auteurs réorganisent la mémoire des matrices du problème ($A_j, B_j, C_j, Q_j, \dots$). Au lieu de stocker chaque matrice de manière contiguë (format "naïf"), ils entrelacent les éléments de plusieurs étapes consécutives.
• Fonctionnement : Si la longueur du vecteur est $d$ (ex: 2, 4 ou 8), les éléments $(A_j)_{ij}$ et $(A_{j+1})_{ij}$ sont placés côte à côte en mémoire. Cela permet d'appliquer une même opération (ex: multiplication matrice-vecteur) sur plusieurs étapes simultanément, réduisant ainsi le nombre d'instructions et améliorant l'utilisation des registres vectoriels.
• Implémentation : Les auteurs ont développé leurs propres routines d'algèbre linéaire (basées sur le framework BLIS) pour gérer ces blocs compacts, évitant les surcoûts observés avec les bibliothèques standards (comme MKL) sur des matrices de petite taille.

C. Parallélisme Multi-cœurs (OpenMP)

Pour les horizons de contrôle longs ($N$) qui dépassent la capacité d'un seul registre vectoriel :

• Le horizon est divisé en blocs de taille $d$.
• Ces blocs sont distribués sur les différents cœurs physiques du processeur en utilisant OpenMP.
• Les opérations indépendantes (calcul des blocs $H_j$, factorisation de Cholesky locale $L_{H,j}$, calcul des matrices intermédiaires $V_j$ et $W_j$) sont exécutées en parallèle.
• La factorisation globale du système tridiagonal par blocs ($\Psi$) reste séquentielle mais bénéficie des opérations linéaires parallèles à l'intérieur de chaque bloc.

3. Contributions Clés

1. Nouveau format de stockage : Introduction d'un format "compact" entrelacé pour les matrices OCP, permettant une vectorisation efficace à travers les étapes du horizon.
2. Routines d'algèbre linéaire optimisées : Développement de micro-kernels C++ utilisant std::simd et des boucles de blocage pour maximiser l'efficacité des opérations SIMD sur des matrices de petite taille, surpassant les bibliothèques génériques.
3. Parallélisation hybride : Combinaison de la vectorisation SIMD (niveau instruction) et du parallélisme OpenMP (niveau thread) pour exploiter pleinement le matériel multi-cœur moderne.
4. Validation empirique : Une analyse comparative rigoureuse montrant des gains de performance massifs par rapport aux solveurs de référence.

4. Résultats

Les expériences ont été menées sur un processeur Intel Core i7-11700 (8 cœurs) avec support AVX-512.

• Benchmark Spring-Mass (Problème diagonal) :

  • Pour un problème avec 70 masses et un horizon $N=15$ (3275 variables), la version dense optimisée de QPALM-OCP est 29 fois plus rapide que QPALM standard (avec blocs denses) et 19 fois plus rapide que QPALM avec élagage des zéros.
  • La version exploitant la structure diagonale spécifique est 65 fois plus rapide que QPALM dense.
  • QPALM-OCP surpasse également le solveur PIQP récent.

• Analyse de l'efficacité du parallélisme :

  • Vectorisation seule : Apporte un gain de vitesse d'environ 2,3x en mode mono-thread.
  • Parallélisme multi-thread (8 threads) : Augmente encore les performances, bien que limité par la bande passante mémoire et les parties séquentielles (comme la factorisation de $\Psi$).

• Benchmark MPC (QUADCMPC) :*

  • Sur des problèmes de locomotion de quadrupèdes (problèmes creux mais non diagonaux), QPALM-OCP (dense) est nettement supérieur au solveur QPALM creux.
  • Exemple : Pour QUADCMPC1, le temps de résolution passe de 21,2 ms (QPALM) à 5,1 ms (QPALM-OCP).
  • Pour les très petits problèmes, l'overhead d'OpenMP est évité, et QPALM-OCP reste compétitif (0,43 ms vs 0,46 ms).

5. Signification et Conclusion

Ce travail démontre que l'exploitation systématique de la structure bloc-diagonale des problèmes de contrôle optimal, combinée à des techniques de bas niveau (SIMD) et de haut niveau (OpenMP), permet d'atteindre des performances de résolution inégalées pour les applications temps réel.

L'approche proposée rend les solveurs basés sur le lagrangien augmenté (comme QPALM) viables et performants pour des problèmes de grande taille sur du matériel embarqué standard, comblant l'écart de performance avec des solveurs spécialisés comme HPIPM. Les auteurs prévoient d'améliorer davantage l'efficacité via un "packing" hors ligne des matrices et des routines de mise à jour de factorisation pour éviter les refactorisations complètes lors de changements mineurs de contraintes.