PyTorch: LinkedIn beschleunigte den DuaLip-Solver 75-fach auf GPUs

Die PyTorch Foundation veröffentlichte eine Fallstudie darüber, wie LinkedIn seinen verteilten Solver für lineare Programmierung DuaLip auf PyTorch umbaute, um Optimierungsprobleme extremen Ausmaßes zu lösen. Das ursprüngliche Werkzeug stützte sich auf einen prozessorgebundenen Scala/Spark-Stack, und die neue GPU-beschleunigte Version trägt den Namen DuaLip-GPU.

Was löste die lineare Programmierung bei LinkedIn?

Lineare Programmierung (LP) ist eine mathematische Methode zur Bestimmung der besten Entscheidung unter gegebenen Einschränkungen. Bei LinkedIn beantwortet sie die Frage: Welches ist aus Millionen oder Milliarden von Möglichkeiten der beste Satz von Aktionen unter Einschränkungen? Konkrete Beispiele umfassen das Zusammenführen von Jobs mit potenziellen Kandidaten, das Ausbalancieren mehrerer Geschäftsmetriken bei Ranking und Empfehlungen sowie die Optimierung des E-Mail-Versandvolumens. Solche Probleme umfassen Hunderte Millionen Nutzer und bis zu Billionen Entscheidungsvariablen.

Wie wurde die Beschleunigung erreicht?

Die PyTorch-Implementierung stützt sich auf drei Techniken: Operationen über dünnbesetzte (sparse) Tensoren zur Handhabung von Milliarden bis Billionen Variablen, verteilte Optimierung durch Aufteilung der Variablen auf GPUs mit Synchronisierung über kollektive Kommunikation (All-Reduce, Broadcast) sowie Konvergenzverbesserungen wie Zeilennormalisierung und beschleunigter Gradientenabstieg (AGD/FISTA-Varianten).

Wie sehen die Ergebnisse aus?

Die Studie nennt bis zu 75-mal schnellere Iterationen in Echtzeit auf 8 GPUs gegenüber der ursprünglichen Scala-Implementierung, mit einer Größenordnung an Beschleunigung gegenüber CPU-Systemen und nahezu linearer Skalierung über mehrere GPUs. Die Genauigkeit blieb dabei erhalten, was LinkedIn “produktive Optimierung in einem Ausmaß ermöglicht, das zuvor undurchführbar war”. Die Implementierung ist als Open Source verfügbar.