DuaLip-GPU Technical Report

Dit paper introduceert een herschreven GPU-gebaseerde solver voor grote lineaire programmeringsproblemen die de schaalbaarheid en doorvoersnelheid van eerdere CPU-gebaseerde systemen aanzienlijk verbetert door een operatorcentrisch model, geoptimaliseerde GPU-technieken en geavanceerde regularisatiemethoden te combineren, wat resulteert in een snelheidswinst van minimaal 10x.

De kern

Stel je voor dat je de logistiek moet regelen voor een gigantisch festival met miljoenen bezoekers en duizenden stands. Iedere bezoeker wil naar een specifieke stand, maar elke stand heeft een beperkt aantal plekken (budget, tijd, capaciteit). Je moet een plan maken dat voor iedereen eerlijk is en dat het festival zo goed mogelijk laat verlopen.

Dit is precies wat DuaLip-GPU doet, maar dan voor LinkedIn. Het is een superkrachtige rekenmachine die enorme lijsten met keuzes (wiskundig gezien: "lineaire programma's") in een flits oplost.

Hier is hoe dit werkt, vertaald naar alledaags taal:

1. Het Oude Probleem: De Verouderde LKW

Vroeger gebruikte LinkedIn een systeem (genaamd DuaLip) dat werkte als een oude, zware vrachtwagen.

• Het was traag: Het reed op CPU's (de standaard "hersenen" van een computer), wat langzaam is voor zulke enorme hoeveelheden data.
• Het was stijf: Je kon er maar twee soorten routes mee rijden. Wil je een nieuwe route? Dan moest je de hele vrachtwagen ombouwen.
• Het was niet toekomstgericht: Het kon geen gebruik maken van de nieuwe, supersnelle "sportauto's" (GPU's) die er nu zijn.

2. De Oplossing: De Nieuwe Formule

Het team van LinkedIn heeft het systeem volledig herbouwd. Ze noemen het DuaLip-GPU.
Stel je voor dat ze de vrachtwagen hebben gesloopt en er een vliegende drone van hebben gemaakt.

• Snelheid: Deze drone is 10 keer sneller dan de oude vrachtwagen.
• Flexibiliteit: Je kunt er nu allerlei nieuwe routes mee vliegen, niet alleen de oude vaste paden.
• Kracht: Hij gebruikt de kracht van moderne grafische kaarten (GPU's), die eigenlijk zijn gemaakt om beelden te maken, maar hier gebruikt worden om miljoenen berekeningen tegelijkertijd te doen.

3. Hoe werkt het? De Drie Sleutels

Om deze drone zo snel en slim te maken, hebben ze drie trucjes gebruikt:

A. De "Blokken" aanpak (Het Legbord)

In plaats van één enorme, rommelige puzzel te proberen op te lossen, hebben ze de puzzel opgedeeld in kleine blokken.

• De analogie: Stel je voor dat je een enorme muur van bakstenen moet bouwen. De oude methode probeerde één steen tegelijk te leggen. De nieuwe methode laat 100 mensen tegelijk een stuk muur bouwen.
• De truc: Ze zorgen ervoor dat elke "persoon" (GPU) alleen naar zijn eigen stukje muur kijkt en dat ze alleen even kort praten over de hoekpunten waar ze samenkomen. Hierdoor hoeven ze niet constant te wachten op elkaar.

B. De "Vergrotingslens" (Preconditioning)

Soms zijn sommige getallen in de berekening heel groot en andere heel klein. Dat maakt het rekenen onstabiel, alsof je probeert te wandelen op een helling waar sommige stukken modderig zijn en andere ijskoud.

• De oplossing: Ze gebruiken een wiskundige "vergrotingslens" (Jacobi-normalisatie). Dit maakt alle hellingen even steil en glad. Nu kan de drone soepel en snel vliegen zonder te struikelen.

C. De "Rijstijl" (Regulatie)

In het begin van de berekening willen ze snel zijn, maar aan het einde willen ze precies zijn.

• De analogie: Stel je voor dat je een auto bestuurt. In het begin rijd je hard op de open weg (grote stapgrootte). Naarmate je dichter bij je bestemming komt, rem je af en rijdt je voorzichtig om perfect te parkeren.
• De truc: Het systeem begint met een "ruwe" versie van het probleem om snel vooruitgang te boeken, en maakt het probleem langzaam steeds fijner en preciezer naarmate het dichter bij de oplossing komt.

4. Het Resultaat: Waarom is dit belangrijk?

Voor LinkedIn betekent dit:

• Snellere beslissingen: Ze kunnen elke dag (of zelfs vaker) nieuwe plannen maken voor wie welke vacature ziet, welke advertenties worden getoond, of wie uitnodigingen krijgt.
• Meer mensen helpen: Omdat het zo snel is, kunnen ze veel complexere regels toepassen zonder dat het systeem vastloopt.
• Minder energie: Het is efficiënter, wat goed is voor het milieu en de kosten.

Samenvattend

Dit artikel vertelt het verhaal van hoe LinkedIn een trage, stijve rekenmachine heeft omgebouwd tot een razendsnel, flexibel en slim systeem. Ze hebben de oude "vrachtwagen" vervangen door een "vliegende drone" die gebruikmaakt van de kracht van moderne chips, slimme wiskundige trucs en een flexibele bouwstijl. Het resultaat is dat ze enorme problemen in een fractie van de tijd kunnen oplossen die daarvoor nodig was.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het rapport "DuaLip-GPU Technical Report" in het Nederlands.

Titel: DuaLip-GPU: Een herschreven, GPU-versnelde solver voor extreme schaal lineaire programmering

1. Het Probleem

Lineaire programmering (LP) vormt de basis voor veel grote schaal beslissingssystemen bij LinkedIn, zoals ranking, allocatie en matchingsproblemen (bijv. het toewijzen van gebruikers aan advertenties of campagnes). Deze problemen worden op een terugkerende cadans (bijv. dagelijks) opgelost.

De bestaande oplossing, DuaLip (een open-source Scala/Spark-stack), had echter ernstige beperkingen:

• Stijve architectuur: Het was gekoppeld aan twee vaste schema's, waardoor het moeilijk was om nieuwe probleemformuleringen of complexe constraints toe te voegen.
• CPU-afhankelijkheid: Het systeem was ontworpen voor CPU's en kon de parallelle rekenkracht van moderne GPU-acceleratoren niet benutten.
• Schaalbaarheid: Het bereiken van een bepaald optimaliteitsniveau was traag, vooral bij extreme schaalproblemen met honderden miljoenen variabelen.

Het doel was om deze solver te herarchitectureren voor hergebruik, flexibiliteit en hoge prestaties op GPU-hardware.

2. Methodologie

De auteurs hebben de solver volledig opnieuw ontworpen als een Python-bibliotheek (PyTorch-gebaseerd) die drie kerncomponenten co-designt:

A. Operator-centric Programmamodel
In plaats van een "roep de solver"-API, biedt de bibliotheek een modulaire interface gebaseerd op drie primitieven:

1. Objectives: Bevat de data en berekent de duale gradiënt.
2. Projections: Voert bloksgewijze projecties uit op decomposeerbare constraints (bijv. simplex of box-constraints).
3. Optimizer: Voert de duale ascent uit.
   Dit maakt het mogelijk om nieuwe LP-formuleringen lokaal toe te voegen zonder de hoofdloop van de oplossing of de diagnostiek te hoeven wijzigen.

B. Algorithmische Verbeteringen (Ridge-geregulariseerde duale ascent)
Het team heeft de bestaande methode versterkt met drie technieken om convergentie en stabiliteit te verbeteren:

• Jacobi-voorconditionering (Rij-normalisatie): De rijen van de constraint-matrix worden genormaliseerd om de conditienummer van het duale probleem te verbeteren. Dit zorgt voor een gelijkmatiger convergentie van de gradiëntstappen.
• Continuatie-schema voor regularisatie ($\gamma$): De ridge-parameter $\gamma$ wordt niet constant gehouden, maar begint hoog voor snelle initiële convergentie en neemt vervolgens af (decay) om de oplossing dichter bij het originele LP te brengen zonder de stabiliteit te verliezen.
• Primaal schalen: De variabelen worden geschaald om te voorkomen dat de regularisatieterm sommige coördinaten domineert en andere negeert, wat de geometrie van de doelstelling verbetert.

C. GPU-Implementatie en Sparse Layouts
Om de parallelle potentieel van GPU's te benutten, zijn specifieke systeemkeuzes gemaakt:

• Sparse Tensor Layouts: De constraint-matrix wordt opgeslagen in Compressed Sparse Column (CSC) formaat, afgestemd op de blok-diagonale structuur van matchingsproblemen. Dit minimaliseert geheugenverkeer en maximaliseert cache-locality.
• Gebatchte Projecties: In plaats van kleine, inefficiënte kernels voor elke kolom, worden projecties gebatched in "logaritmische buckets". Dit vermindert de kernel-launch overhead aanzienlijk.
• Distributiepatroon: Alleen de duale variabelen ($\lambda$) worden gesynchroniseerd tussen GPU's. De berekening van de gradiënt en projecties gebeurt lokaal op elke GPU, wat de communicatie-overhead minimaliseert.

3. Belangrijkste Bijdragen

1. Operator-centric Library: Een flexibele Python-bibliotheek die nieuwe LP-formuleringen en constraint-families ondersteunt via een composabel model, in tegenstelling tot de stijve schema's van het vorige Scala-systeem.
2. Verbeterde Algorithmiek: Een robuustere versie van ridge-regularized dual ascent met Jacobi-voorconditionering, adaptieve regularisatie en primaal schalen, wat leidt tot snellere en stabielere convergentie.
3. GPU-Snelheid en Schaalbaarheid: Een implementatie die de beschikbare parallelle rekenkracht volledig benut via sparse layouts en gebatchte operaties, waardoor extreme schaalproblemen efficiënt kunnen worden opgelost.

4. Resultaten

De prestaties zijn getest op synthetische matchingsproblemen met tot 100 miljoen bronnen (gebruikers) en 10.000 bestemmingen:

• Snelheidswinst: De GPU-versie is minimaal 10x sneller dan de vorige verspreide CPU-versie (Scala/Spark) om een vaste sub-optimaliteitsgap te bereiken.
• Schaalbaarheid: Het systeem toont bijna lineaire schaalbaarheid bij het toevoegen van meer GPU's (bijv. ~3,86x snelheidswinst op 4 GPU's).
• Numerieke Pariteit: De PyTorch-implementatie vertoont een bijna perfecte overlap met de originele Scala-solver in termen van de duale doelstellingsverloop, met een relatieve fout van minder dan 1% binnen de eerste 100 iteraties.
• Effect van Verbeteringen: Experimenten tonen aan dat voorconditionering de vroege convergentie aanzienlijk versnelt en dat het continuatie-schema voor $\gamma$ een betere balans biedt tussen snelheid en oplossingskwaliteit.

5. Betekenis

Dit werk transformeert ridge-regularized dual ascent van een gespecialiseerde, schema-gebonden oplossing naar een flexibele, hoogpresterende architectuur die geschikt is voor moderne GPU-gestuurde pipelines.

• Het stelt LinkedIn in staat om complexere en grotere matchingsproblemen op te lossen met minder engineering-overschot.
• Het demonstreert dat first-order methoden, wanneer ze goed geoptimaliseerd zijn voor hardware en structuur, concurrerend kunnen zijn met of zelfs superieur kunnen zijn aan geavanceerde solvers voor specifieke industriële workloads.
• De open-source code (beschikbaar op GitHub) biedt een blauwdruk voor andere organisaties om extreme schaal LP-problemen op GPU's te implementeren.

Samenvattend biedt DuaLip-GPU een krachtige combinatie van algoritmische innovatie en systeemontwerp om de uitdagingen van extreme schaal lineaire programmering in productieomgevingen aan te pakken.