Gibt es eine eingeschränkte nichtlineare Optimierungsbibliothek wie IPOPT, die auf GPUs ausgeführt wird?

8

Jemand in meinem Team möchte IPOPT parallelisieren. (zumindest einige Funktionen davon). Ich konnte keine GPU-Implementierung oder ein ähnliches Paket finden. Ich habe auch nichts in ihren Dokumenten gefunden.

Die Frage ist also, gibt es eine Alternative, die bereits auf der GPU implementiert ist? oder zumindest jemand, der daran arbeitet, es auf die GPU zu portieren, damit wir zusammenarbeiten können?

jbcolmenares
quelle

Antworten:

12

tl; dr: Mein allgemeiner Eindruck aus der Literatur ist, dass Beschleunigungen bescheiden sind (falls vorhanden). Der Hauptkern, den Sie in diesen Methoden sehen, ist eine Methode mit geringer Dichte (z. B. LU mit geringer Dichte, LDLT mit geringer Dichte), und die Speicherzugriffe sind unregelmäßig. Diese Eigenschaften begünstigen nicht die Verwendung von GPUs. Auch parallele IPMs stecken noch in den Kinderschuhen. Ich vermute immer noch, dass Leute an GPU-Implementierungen arbeiten werden, aber ich bin skeptisch, dass viel von ihnen kommen wird. (IPMs mit verteiltem Speicher scheinen jedoch etwas vielversprechender und nützlicher zu sein.)


Einige Leute haben an IPMs (Interior-Point-Methoden) für GPUs gearbeitet:

  • Smith, Gondzio und Hall entwickelten ein IPM für lineare Programme (LPs), das eine 4-10-fache Beschleunigung erreichte
  • Jung und O'Leary betrachten einige der linearen Algebra-Kernel in IPMs für LPs und sehen bescheidene Beschleunigungen für GPUs bei größeren Problemen in ihrem Testsatz

Im Allgemeinen vergleichen die Zeitungen ihre Arbeit nicht mit hoch abgestimmten LP-Lösern. Jung und O'Leary vergleichen sich mit Linprog, was für die meisten Praktizierenden nicht die Wahl wäre, und der Eindruck, den ich beim Scannen des Papiers von Smith et al. Habe, ist, dass eine serielle Innenpunktmethode von Grund auf neu geschrieben wurde. Angesichts der Tatsache, dass Hall sehr an Open-Source-LP-Lösern beteiligt ist, nehme ich diese Arbeit etwas ernster. Einer der besseren Open-Source-LP-Löser da draußen ist Clp, das Hall unterhält, und wenn sie diesen Code verwendet hätten, würde er namentlich erwähnt. Ich würde also mehr Aufmerksamkeit schenken, wenn diese Codes bereits hochgradig abgestimmte Löser beschleunigen würden, anstatt einmalige serielle Vergleiche, die nicht auf dem neuesten Stand der Technik sind.

Das heißt, die vorhandene Arbeit ist für LPs, und Sie fragen wahrscheinlich nach einem nichtlinearen Programmierlöser (NLP), denn genau das ist IPOPT. Folgendes weiß ich über den NLP-Solver-Fall:

Die meisten Forschungen scheinen an der Parallelität für den Fall des verteilten Speichers zu arbeiten (was schwierig genug ist). Es gibt einige Arbeiten am Shared-Memory-Fall für LP- und QP-Löser, da diese Arbeit es in kommerzielle Codes (z. B. Gurobi, CPLEX, Xpress) schafft. Bestehende Arbeiten sind interessant, aber für GPUs scheint es noch nichts Überzeugendes zu geben, mit Ausnahme spezieller Anwendungen (z. B. maschinelles Lernen, für die Sie verschiedene Algorithmen verwenden können, die besser für GPUs geeignet sind).

Geoff Oxberry
quelle
Die Parallelisierung von IPMs für LP läuft darauf hinaus, die spärliche Cholesky-Faktorisierung zu parallelisieren. Dies ist kein gut gespeichertes Problem, insbesondere bei GPUs. Das Parallelisieren von Simplex-Methoden für LP ist viel schwieriger und es gab in diesem Bereich nur sehr wenig nützliche Arbeit. Wenn Sie eine LP in großem Maßstab parallel lösen möchten, möchten Sie wahrscheinlich ein IPM verwenden.
Brian Borchers
1
Bei SDP ist die Matrix, die bei jeder Iteration berücksichtigt werden muss, meistens dicht, und die Cholesky-Faktorisierung lässt sich auf einer gemeinsam genutzten Speichermaschine gut parallelisieren. Der Aufbau dieser Matrix ist auch ziemlich einfach zu parallelisieren. Auf diese Weise ist es möglich, auf einem Multiprozessor mit gemeinsamem Speicher mit einer Innenpunktmethode für SDP mit einer Anzahl von Prozessoren bis zu 64 (soweit ich das getan habe) einigermaßen gute parallele Beschleunigungen zu erzielen
Brian Borchers
cuSolver ist NVidias Satz von Cuda-Solvern und bietet APIs wie csrlsvchol, die auf der Cholesky-Faktorisierung docs.nvidia.com/cuda/cusolver
Andrew Hundt
@GeoffOxberry Einige Links funktionieren nicht.
T ....
1

Im Allgemeinen ist eine nichtlineare Optimierung schwer zu parallelisieren, da der Schrittalgorithmus sehr sequentiell ist. GPUs sind langsamer als CPUs, sodass Sie nur dann eine Beschleunigung erhalten, wenn Sie ein Problem haben, das sehr parallel ist (dh Tausende von Threads). Daher würde ich keine große Beschleunigung erwarten (oder eine, die normalerweise langsamer ist), wenn ich den nichtlinearen Löser auf die GPU setze. Das ist höchstwahrscheinlich der Grund, warum niemand es gut gemacht hat und die meisten Leute es nicht versuchen würden.

Wenn andererseits Ihre Ziel- und Einschränkungsfunktionen hochparallel (oder vektorisiert) berechnet werden können, können Sie eine massive Beschleunigung erzielen, indem Sie Ihre Ziel- / Einschränkungsfunktionen auf der GPU lösen. Dies ist eine gängige Methode zur Verwendung von GPUs mit nichtlinearer Optimierung, da die GPU-Beschleunigung für den schwierigsten (und parallelsten) Teil des Codes verwendet wird und daher wahrscheinlich die effizienteste ist.

Chris Rackauckas
quelle
1

Ich bin etwas spät dran, aber die kurze Antwort lautet: Ja, es ist möglich, eine interne Punktmethode für GPUs zu parallelisieren. Ob dies jedoch erfolgreich ist oder nicht, hängt von der Struktur des Problems ab. In Bezug auf vorhandene Software kann Optizelle dies tun. Besorgen Sie sich den Entwicklungszweig, bis in naher Zukunft eine neue Version erscheint.

Die Situationen unterscheiden sich geringfügig, je nachdem, ob das ursprüngliche Problem Gleichheiten oder Ungleichungen enthält oder nicht. Es gibt verschiedene Möglichkeiten, dies zu tun, aber meiner Meinung nach ist der beste Weg, dies bei Problemen mit nur Ungleichheitsbeschränkungen zu tun, die Verwendung einer Newton-Methode mit ungenauer Vertrauensregion in Kombination mit einer Methode mit zwei ursprünglichen inneren Punkten.

Nur für Ungleichungen finden Sie die grundlegende ungenaue Newton-Methode für Vertrauensbereiche in der numerischen Optimierung von Nocedal und Wright auf Seite 171 oder auf den Vertrauensbereichsmethoden von Conn, Gould und Toint auf Seite 205. Dieser Algorithmus kann erfolgreich mit einer Primärmethode kombiniert werden. Dual-Interior-Point-Methode unter Verwendung der modifizierten Truncated-CG-Methode ab Seite 890 des Papiers Eine Interior-Point-Methode für die nichtlineare Programmierung in großem Maßstab von Byrd, Hribar und Nocedal. Persönlich gefällt mir nicht, wie sie ihr inneres Punktesystem einrichten, daher würde ich ihre innere Punktformulierung nicht verwenden, aber das ist die Präferenz. NITRO ist ein guter Algorithmus. In Bezug auf die Details des Innenpunkts wird im Handbuch von Optizelle in seinem Handbuch erläutert, wie dies zu tun ist. Ich sollte wahrscheinlich ein aktualisiertes Handbuch veröffentlichen,

Für den Fall sowohl mit Ungleichheits- als auch mit Gleichheitsbeschränkungen glaube ich, dass der beste Algorithmus darin besteht, die ungenaue SQP-Methode mit zusammengesetzten Schritten für Vertrauensbereiche von Heinkenschoss und Ridzal in einem Artikel mit dem Titel Eine matrixfreie SQP-Methode für Vertrauensbereiche für die Optimierung mit eingeschränkten Gleichheitsbereichen zu kombinieren. Grundsätzlich funktioniert der Prozess des Anheftens einer inneren Punktmethode ziemlich genau wie der uneingeschränkte Fall, außer dass der quasinormale Schritt ebenfalls sichergestellt werden muss.

Was die Parallelisierungsmöglichkeiten angeht, funktionieren die oben genannten Algorithmen gut, da diese Algorithmen matrixfrei implementiert werden können. Insbesondere die Implementierung von Optizelle für das Problem

minxX{f(x):g(x)=0,h(x)0}

Erfordert, dass der Benutzer eine Implementierung für bereitstellt

  • f(x),f(x),2f(x)x

  • g(x),g(x)x,g(x)y,(g(x)x)y

  • h(x),h(x)x,h(x)y,(h(x)x)y

Es ist egal, woher diese Implementierungen kommen oder wie sie parallelisiert sind. Sie können im gemeinsam genutzten Speicher, im verteilten Speicher oder in GPUs ausgeführt werden. Es spielt keine Rolle. Was für ein bestimmtes Problem am besten funktioniert, hängt von der Struktur ab. Darüber hinaus muss der Benutzer eine lineare Algebra für bereitstellen

  • init: Memory allocation and size setting
  • copy: y <- x (Shallow. No memory allocation.)
  • scal: x <- alpha * x
  • axpy: y <- alpha * x + y
  • innr: innr <- <x,y>
  • zero: x <- 0
  • rand: x <- random
  • prod: Jordan product, z <- x o y
  • id: Identity element, x <- e such that x o e = x
  • linv: Jordan product inverse, z <- inv(L(x)) y where L(x) y = x o y
  • barr: Barrier function, barr <- barr(x) where x o grad barr(x) = e
  • srch: Line search, srch <- argmax {alpha \in Real >= 0 : alpha x + y >= 0} where y > 0
  • symm: Symmetrization, x <- symm(x) such that L(symm(x)) is a symmetric operator

Diese Vorgänge können im seriellen, parallelen, verteilten Speicher, im gemeinsam genutzten Speicher oder auf GPUs ausgeführt werden. Es spielt keine Rolle. Was am besten ist, hängt von der Problemstruktur ab.

Schließlich gibt es die linearen Systeme und es gibt drei, die bereitgestellt werden können:

  • Vorkonditionierer für2f(x)
  • Linker Vorkonditionierer fürg(x)g(x)
  • Richtiger Vorkonditionierer fürg(x)g(x)

Jeder dieser Vorkonditionierer kann entweder im seriellen oder parallelen, verteilten Speicher oder gemeinsam genutzt oder auf GPUs implementiert werden. Grundsätzlich ist der erste Vorkonditionierer der Vorkonditionierer für das verkürzte CG-System, das den Optimalitätssystemen zugeordnet ist. Die letzten beiden Vorkonditionierer werden für die erweiterten Systemlösungen verwendet, die dem zusammengesetzten Schritt-SQP-Algorithmus zugeordnet sind. Im Allgemeinen erhalten Sie hier Ihren größten Leistungsschub. Stellen Sie sich vor, die Einschränkung repräsentiert eine Art PDE. Dann entspricht der Vorkonditionierer für einer Vorwärts-PDE-Lösung, gefolgt von einer adjungierten PDE-Lösung. Beachten Sie, wenn sie quadratisch wären,g ' ( x ) g ' ( x ) ( g ' ( x ) g ' ( x ) ) - 1 = g ' ( x ) - g ' ( x ) - 1gg(x)g(x)(g(x)g(x))1=g(x)g(x)1. Für eine große Anzahl von PDE-Formulierungen, wie z. B. Finite-Differenzen-Methoden mit expliziten Zeitintegratoren, können diese Lösungen auf einer GPU sehr gut parallelisiert werden.

Schließlich arbeiten die Algorithmen in Optizelle an symmetrischen Kegelproblemen, zu denen gebundene, Kegel zweiter Ordnung und semidefinite Einschränkungen gehören. Trotzdem neigen die linearen Kegellösungen im Allgemeinen dazu, diese zu übertreffen. Grundsätzlich können lineare Kegellösungen die Machbarkeit und Optimalitätslösungen eines wirklich kompakten Systems reduzieren, das nach Choleski berücksichtigt werden kann. Da Optizelle mit nichtlinearen Systemen arbeitet, kann es das nicht wirklich. Zumindest weiß ich nicht wie. Darüber hinaus gibt es Einschränkungen hinsichtlich der Größe der SDP-Blöcke, die Optizelle verarbeiten kann. Der Betreiberlinvoben erfordert die Umkehrung der SDP-Matrizen und diese Umkehrung ist für große Blöcke wirklich teuer. Darüber hinaus gibt es einen zusätzlichen Schutz, der eine Choleski-Faktorisierung erfordert. Diese Faktorisierungen lassen sich auf einer GPU nicht wirklich gut parallelisieren. Zumindest kenne ich keine Implementierung, die gut parallelisiert werden kann. Unter dem Strich sollten Sie als lineares Kegelprogramm einen linearen Kegellöser wie CSDP oder SDPT3 verwenden.

TLDR; Verwenden Sie Optizelle . Es ist kostenlos, Open Source und BSD-lizenziert. Ich habe es auf ungefähr eine halbe Milliarde Variablen skaliert und es hat gut funktioniert. Ich habe es mit GPUs betrieben und es hat gut funktioniert. Ob es mit einer GPU gut funktioniert oder nicht, hängt davon ab, ob die oben genannten Vorgänge auf einer GPU gut parallel sind oder nicht.

wyer33
quelle