DuaLip-GPU Technical Report

Ce rapport technique présente une nouvelle architecture de solveur pour les programmes linéaires à grande échelle, conçue pour découpler la spécification du problème du moteur d'optimisation et exploiter les GPU, offrant ainsi une accélération d'au moins 10 fois par rapport à la version CPU précédente tout en conservant des garanties de convergence.

L'essentiel

Imaginez que LinkedIn doit distribuer des millions de publicités, d'offres d'emploi ou de notifications à des milliards d'utilisateurs chaque jour. C'est un peu comme essayer de remplir des milliers de boîtes aux lettres avec des lettres, tout en respectant des règles strictes : chaque boîte ne peut recevoir qu'un certain nombre de lettres, et chaque lettre ne peut aller que dans certaines boîtes.

Mathématiquement, c'est un problème d'optimisation linéaire. C'est un casse-tête géant où l'ordinateur doit trouver la meilleure combinaison possible parmi des milliards de possibilités.

Voici l'histoire de la nouvelle solution présentée dans ce rapport, racontée simplement :

1. Le Problème de l'Ancienne Voiture (L'ancien système)

Avant, LinkedIn utilisait un système appelé "DuaLip". C'était une voiture très efficace, mais elle avait deux gros défauts :

• Elle était conçue pour une seule route : Elle ne pouvait gérer que deux types de problèmes très spécifiques. Si vous vouliez ajouter une nouvelle règle (comme "ne pas envoyer de pub le week-end"), il fallait reconstruire tout le moteur.
• Elle était lente et lourde : Elle utilisait des processeurs classiques (CPU), comme un moteur à essence qui tourne doucement. Pour des problèmes aussi énormes, c'était comme essayer de traverser l'océan avec un canot pneumatique.

2. La Nouvelle Solution : Le "DuaLip-GPU"

Les ingénieurs ont décidé de reconstruire le système de zéro. Ils ont créé une nouvelle bibliothèque logicielle (un outil) qui ressemble plus à un kit de construction LEGO qu'à une voiture toute faite.

Voici les trois piliers de cette nouvelle approche, expliqués avec des analogies :

A. Le Kit de Construction Modulaire (Programmation par opérateurs)

Au lieu de dire à l'ordinateur "Résous ce problème spécifique", ils ont créé des briques de base interchangeables :

• La brique "Objectif" : Ce que l'on veut optimiser (ex: maximiser les clics).
• La brique "Règles" : Les contraintes (ex: budget limité, nombre d'utilisateurs).
• La brique "Optimiseur" : Le cerveau qui cherche la meilleure solution.

L'analogie : Imaginez un chef cuisinier. Au lieu de lui donner une recette figée pour faire un gâteau, on lui donne des ingrédients de base (farine, œufs, sucre) et des outils (moule, fouet). Il peut maintenant faire un gâteau, une tarte ou un pain, sans avoir à changer de cuisine. De la même manière, les ingénieurs peuvent maintenant ajouter de nouvelles règles à leur problème de distribution sans réécrire tout le code.

B. L'Accélérateur de Formule 1 (L'Algorithme amélioré)

Le système utilise une méthode mathématique appelée "descente duale". C'est comme essayer de descendre une montagne dans le brouillard pour trouver le point le plus bas.

• Le problème : Parfois, la montagne est très irrégulière (certaines pentes sont raides, d'autres plates), ce qui fait que le marcheur trébuche ou avance très lentement.
• La solution : Les ingénieurs ont ajouté trois "accessoires" pour aider le marcheur :
  1. Le nivellement (Préconditionnement) : Ils lissent les pentes pour que la descente soit plus régulière.
  2. Le guide de vitesse (Régularisation) : Ils commencent par descendre vite avec une grande prudence, puis ralentissent et affinent leur pas à la fin pour ne pas rater le point exact.
  3. L'échelle (Mise à l'échelle) : Ils ajustent la taille des pas en fonction de la pente.

Le résultat : Au lieu de trébucher, le système glisse comme sur un tapis roulant parfaitement lisse, atteignant la solution beaucoup plus vite.

C. Le Super-Train à Grande Vitesse (L'exécution sur GPU)

C'est ici que la magie opère. Les anciens systèmes utilisaient un seul gros camion (CPU) pour transporter tout le chargement. Le nouveau système utilise un train à grande vitesse avec des wagons séparés (GPU).

• La répartition : Au lieu de tout faire faire à un seul cerveau, ils divisent le travail en milliers de petits morceaux. Chaque carte graphique (GPU) est un wagon qui traite sa propre partie du problème en même temps que les autres.
• La communication : Les wagons ne parlent pas tout le temps entre eux (ce qui ralentirait le train). Ils ne se parlent que pour s'assurer qu'ils sont tous sur la bonne voie, puis continuent leur travail individuellement.
• L'organisation : Ils ont rangé les données de manière intelligente (comme des livres dans une bibliothèque triée par ordre alphabétique) pour que les wagons puissent les attraper instantanément sans chercher.

Les Résultats Concrets

Grâce à cette nouvelle architecture :

• Vitesse : Le nouveau système est 10 fois plus rapide que l'ancien. Ce qui prenait une heure, prend maintenant 6 minutes.
• Flexibilité : On peut ajouter de nouvelles règles de distribution en quelques lignes de code, au lieu de passer des semaines à reprogrammer le système.
• Évolutivité : Si le problème double de taille, on ajoute simplement plus de wagons (plus de GPU) et le train continue d'aller aussi vite.

En Résumé

Ce rapport raconte comment LinkedIn a transformé un outil rigide et lent en une plateforme flexible et ultra-rapide. Ils ont passé d'une approche "usine à gaz" (tout est collé ensemble) à une approche "modulaire" (des pièces interchangeables), et ils ont remplacé le moteur à essence par un moteur électrique de Formule 1 (les GPU).

Cela leur permet de résoudre des problèmes de distribution massifs en temps réel, garantissant que vous recevez le bon contenu, au bon moment, sans que l'ordinateur ne s'effondre sous la charge.

Résumé technique

Voici un résumé technique détaillé du rapport de recherche DuaLip-GPU, rédigé en français.

1. Problématique et Contexte

Les programmes linéaires (LP) sont fondamentaux pour de nombreux systèmes de décision à grande échelle dans l'industrie, notamment pour le classement, l'allocation et les problèmes d'appariement (matching) exécutés de manière récurrente.

• Limites des systèmes précédents : Les travaux antérieurs, tels que ECLIPSE (ascension duale régularisée par ridge) et la version open-source de DuaLip de LinkedIn (basée sur Scala/Spark), ont démontré que les méthodes du premier ordre pouvaient être mises à l'échelle. Cependant, ces systèmes présentaient des défauts majeurs :

  • Ils étaient fortement couplés à des schémas de données fixes (deux modèles uniquement), rendant difficile l'expression de nouvelles formulations.
  • Ils reposaient sur un runtime centré sur le CPU, empêchant l'utilisation efficace des accélérateurs modernes (GPU).
  • L'ajout de nouvelles contraintes ou familles de contraintes nécessitait des modifications profondes du code interne.

• Objectif : Repenser l'architecture du solveur pour le rendre réutilisable, flexible et capable d'exploiter la puissance des GPU, tout en conservant la capacité à résoudre des LPs à une échelle extrême (des millions de variables).

2. Méthodologie et Architecture

L'équipe a conçu une bibliothèque Python qui co-conçoit une interface compositionnelle, un package algorithmique et des techniques d'exécution sur GPU. L'approche repose sur l'ascension duale régularisée par ridge.

A. Modèle de Programmation Centrée sur les Opérateurs

Au lieu d'une interface déclarative rigide, le nouveau système expose des rôles au niveau des opérateurs, permettant une composition locale :

1. Objectives/ : Encapsule les données et le calcul du gradient dual.
2. Projections/ : Gère les projections bloc par bloc sur les polytopes de contraintes "simples" (ex: contraintes de capacité par utilisateur).
3. Optimizer/ : Effectue l'ascension duale en utilisant le gradient.

• Avantage : La boucle de résolution et les diagnostics restent inchangés. De nouvelles formulations de LP peuvent être ajoutées localement sans modifier le cœur du solveur.

B. Améliorations Algorithmiques (Ascension Duale Régularisée)

Pour améliorer la robustesse et la convergence sur des problèmes de production, trois améliorations clés ont été intégrées :

1. Préconditionnement de Jacobi (Normalisation des lignes) : Pour améliorer le conditionnement du problème dual, les contraintes complexes sont redimensionnées. Cela égalise les valeurs propres de la matrice Hessienne duale, stabilisant les mises à jour du gradient.
2. Schéma de continuation pour le paramètre de régularisation ($\gamma$) : Au lieu d'utiliser une valeur fixe, $\gamma$ commence à une valeur élevée pour assurer une convergence rapide et stable au début, puis décroît progressivement pour se rapprocher de la solution exacte du LP non régularisé.
3. Mise à l'échelle des variables primales : Pour gérer les hétérogénéités d'échelle dans les variables primales, une mise à l'échelle diagonale est appliquée. Cela empêche le terme de régularisation quadratique de dominer certaines coordonnées tout en devenant négligeable pour d'autres.

C. Exécution sur GPU et Optimisations Système

L'implémentation utilise PyTorch pour exploiter les primitives de calcul tensoriel et distribué :

• Format de données Sparse (CSC) : La matrice de contraintes est stockée au format Compressed Sparse Column (CSC), alignée sur la structure des blocs diagonaux des problèmes d'appariement. Cela optimise la localité des données et les opérations matrice-vecteur.
• Opérateurs de projection par lots (Batching) : Au lieu de lancer des noyaux GPU pour chaque colonne (inefficace), les projections sont regroupées par lots de tailles similaires (seuils logarithmiques). Cela amortit les coûts de lancement des noyaux et augmente l'occupation des GPU.
• Communication Distribuée : Seules les variables duales ($\lambda$) sont synchronisées entre les GPU. Chaque GPU calcule localement sa contribution (projection et gradient) sans dépendances croisées, réduisant considérablement la surcharge de communication (une réduction et deux diffusions par itération).

3. Résultats Expérimentaux

Les expériences ont été menées sur des données synthétiques d'appariement à grande échelle (jusqu'à 100 millions de sources) et comparées à l'implémentation Scala/Spark existante.

• Parité Numérique : Les trajectoires de l'objectif dual entre la version PyTorch (GPU) et la version Scala (CPU) sont quasi identiques, avec une erreur relative inférieure à 1 % après 100 itérations.
• Performance et Mise à l'échelle :
  • Gain de vitesse : La version GPU offre un gain d'ordre de grandeur, soit au moins 10 fois plus rapide que la version distribuée CPU pour atteindre un écart de sous-optimalité fixe.
  • Scalabilité : Le solveur montre une mise à l'échelle quasi-linéaire sur plusieurs GPU (ex: 3,86x de vitesse sur 4 GPU par rapport à 1 GPU, proche de l'idéal de 4x).
  • Gestion de la mémoire : Le partitionnement des colonnes sur plusieurs GPU permet de résoudre des instances trop volumineuses pour tenir sur un seul dispositif.
• Impact des améliorations algorithmiques :
  • Le préconditionnement accélère significativement la convergence, surtout dans les premières itérations.
  • Le schéma de continuation de $\gamma$ permet d'obtenir une convergence plus rapide tout en préservant la fidélité de la solution finale.

4. Contributions Clés

1. Modèle de programmation flexible : Remplacement d'une interface basée sur des modèles rigides par un modèle centré sur les opérateurs, facilitant l'ajout de nouvelles familles de contraintes sans réécrire le solveur.
2. Améliorations algorithmiques robustes : Intégration de techniques de préconditionnement, de mise à l'échelle et de continuation de régularisation pour garantir une convergence stable sur des problèmes industriels complexes.
3. Architecture GPU-native : Démonstration de la faisabilité de résoudre des LPs extrêmes sur GPU en utilisant des layouts de données sparse et des communications distribuées minimales, atteignant des gains de performance massifs par rapport aux systèmes CPU traditionnels.

5. Signification et Impact

Ce travail marque une transition importante dans la résolution de programmes linéaires à grande échelle pour l'industrie. En passant d'un système couplé au CPU et rigide à une architecture modulaire et accélérée par GPU, DuaLip-GPU permet :

• De résoudre des problèmes d'appariement et d'allocation 10 fois plus rapidement, permettant des cycles de décision plus fréquents ou plus fins.
• De traiter des problèmes plus grands (plus de millions de variables) grâce au partitionnement efficace sur plusieurs GPU.
• D'offrir une flexibilité accrue pour les équipes d'ingénierie, qui peuvent désormais exprimer de nouvelles formulations de problèmes (contraintes multiples, structures complexes) avec un effort de développement minimal.

En résumé, ce rapport présente une refonte complète d'un solveur industriel critique, transformant une méthode spécialisée en une plateforme haute performance adaptable aux besoins futurs de l'optimisation à l'échelle de l'entreprise.