Az NVIDIA bemutatta a cuOpt Multi‑GPU Primal‑Dual hybrid gradient for Linear Programming (mPDLP) megoldást, amely nagy, ritka lineáris programokat (LP) oszt szét NVLink‑kapcsolattal összekötött több GPU között. A cél az, hogy azokat a tervezési feladatokat, amelyek egyetlen GPU memóriakorlátját vagy az időablakot meghaladják, gyakorlati határidőn belül rendezni lehessen. A több‑GPU megközelítés két fontos eredményt ígér: rövidebb megoldási időt a nagyon nagy modellek esetén és egy GPU‑ra vetítve akár 6x alacsonyabb csúcsmemória‑használatot a single‑GPU PDLP‑hez képest (LP‑problémák 2,1 milliárd nemnulla bejegyzésig).
Miért volt szükség több‑GPU megoldásra?
Az ellátási láncok, az energiaipar és más ipari területek egyre több SKU‑t, útvonalat és korlátozást kezelnek, emiatt a modellek mérete és a belső bizonytalanság nő. Bár a GPU‑gyorsított cuOpt egyetlen GPU‑n már több mint 10x gyorsulást tudott elérni CPU‑alapú megoldókhoz képest nagy lineáris programokon, a legnagyobb tervezési feladatok órákat vehetnek igénybe vagy meghaladhatják az egy GPU memóriáját — ez üzleti döntéshozatali szűk keresztmetszethez vezet. A kihívást jól szemlélteti a kutatói közösségben ismert zib03 példa, amely Thorsten Koch 2008‑as problémája több mint 104 millió nemnullával és gyakran benchmarkként szolgál új algoritmusokhoz és hardverekhez.
A PDLP algoritmus röviden
A Primal‑Dual hybrid gradient for LP (PDLP) egy elsőrendű, iteratív módszer LP‑k megoldására. A módszer a gradiense‑módra emlékeztető, elemenkénti műveletekre épül, ami jól párhuzamosítható és GPU‑barát. Az iterációk forró belső ciklusa Sparse Matrix‑Vector Multiplication (SpMV), majd több térképezés és projekciós lépés. A módszer egyszerre tartja nyilván a prímális (x) és dualis (y) vektorokat; minden iterációban az Ax és A^T y SpMV‑k dominálnak. Mivel ezek memóriakötött műveletek, a rendelkezésre álló memória‑sávszélesség növelése (több GPU‑val) gyorsítást hozhat, de el kell kerülni a nagy kommunikációs és terhelés‑egyensúly‑veszteségeket.
Hogyan osztja meg mPDLP a munkát?
A cuOpt mPDLP nem a korábbi 2D‑s részleges SpMV‑végrehajtást alkalmazza (ahol a mátrixot sorok és oszlopok szerint blokkokra bontják és minden blokk SpMV‑jét függetlenül számolják), hanem min‑cut grafpartícionálást használ. A folyamat:
- A mátrixból bipartit gráfot képeznek, amely a prímális‑ és duális változók közti függőségeket jelzi.
- A gráfot k‑irányban (k GPU) úgy partícionálják, hogy a vágásba eső élek száma minimális legyen; a belső élek lokálisan kiszámíthatók, a vágott élek kommunikációt igényelnek.
- Minden GPU a saját sorainak és oszlopainak megfelelő részt kapja; a PDLP iterációk jelentős része lokális marad, kommunikáció csak a partíción átvágott éleknél történik.
Ez a min‑cut alapú elrendezés kihasználja, hogy a PDLP egymást követő SpMV‑i között erős függőségek vannak az x és y vektorokban, és így kevesebb kereszt‑GPU adatmozgatásra van szükség, mint a független 2D megközelítésnél.
Hardver‑ és szoftvertámogatás a skálázáshoz
A több‑GPU skálázáshoz NVIDIA NVLink és NVSwitch adja a fizikai sávszélességet, míg a szoftveres rétegen a NCCL (NVIDIA Collective Communications Library) biztosítja a GPU‑direct kommunikációs primitíveket (AllReduce, AllGather, Broadcast). Együtt az NVLink/NVSwitch és NCCL lehetővé teszik, hogy több különálló GPU gyors, alacsony késleltetésű megosztott gépként viselkedjen.
Teljesítmény‑eredmények és korlátok
A tesztek több mint 100 LP‑esetre terjedtek ki, különböző benchmark‑készletekből (Hans Mittleman LPFeas, PDLP és D‑PDLP benchmarkok, Open Energy Benchmark, valamint ipari partnerek problémái). Az összehasonlításoknál a célkövetelmény 10^−6 volt, egy óra időkorlát mellett. A több‑GPU tesztek NVIDIA DGX B200 csomóponton futottak, ahol a GPU‑k all‑to‑all NVLink topológiával kapcsolódnak; az egyetlen‑GPU PDLP összehasonlítás egy B200 GPU‑n történt.
Főbb megállapítások:
- A mPDLP gyorsulása erősen korrelál a probléma méretével: észrevehető javulás körülbelül 10^7 nemnulla fölött. E fölött a méret fölött a több‑GPU változat előnye nő.
- Ha csak a PDLP lépéseket vizsgáljuk, mPDLP elérte az 11,4x gyorsulást egy tsp‑gaia‑10m nevű példán. Az end‑to‑end (egész folyamat) gyorsulás mérsékeltebb volt, például 4,2x egyes esetekben, mivel az előfeldolgozás (presolving), host‑oldali transzponálás, graf‑partícionálás és postsolving iterációfüggetlen költségeket jelent.
- Összehasonlítva a korábbi több‑GPU D‑PDLP‑vel, mPDLP általában 1,2x–2,5x gyorsabb volt a nagyok (nnz>10^7) esetén. Néhány ultra‑nagy eseten azonban mPDLP lassabb volt; ezek a konkrét benchmark‑problémák eltérő sűrűségi mintázattal rendelkezhetnek, ezért nem feltétlenül reprezentálják az ipari felhasználás jellemzőit.
- A több‑GPU megközelítés csak elegendően nagy problémákon hoz nyereséget; kis problémákon a szinkronizációs és iterációnkénti adatmozgatási költségek felülírhatják a párhuzamosítás előnyeit.
- A mátrix ritkasági szerkezete kritikus: ha a min‑cut partícionálás után nagy az edge‑cut arány, akkor sok kereszt‑GPU kommunikáció marad, ami semlegesítheti vagy visszafordíthatja a gyorsulást.
Iparági felhasználói eredmények
Két ipari partner mérhető eredményt mutatott be:
- Kinaxis: egy globálisan korlátozott CPG ellátási és termelési tervezési LP modellen 3,3x gyorsulást értek el több mint 135 millió változóval, a cuOpt mPDLP‑t nyolc NVLink‑kapcsolatú NVIDIA H100 GPU‑n futtatva a Maestro platformon.
- PSR: egy stokasztikus energia‑kapacitás‑bővítési LP modellen több mint 5x gyorsulást jelentettek 185 millió változóval, nyolc NVLink‑kapcsolatú NVIDIA B200 GPU használatával.
Ezek a példák azt mutatják, hogy valós ipari problémákon is mérhető és hasznos lehet a több‑GPU PDLP alkalmazása.
Fejlesztési irányok
Az NVIDIA a következő fejlesztéseken dolgozik a cuOpt mPDLP kapcsán:
- Súly‑tudatos min‑cut és hipermátrix (hypergraph) partícionálás, amely figyelembe veszi az egyes GPU‑kra jutó számítási terhelést, csökkentve a terhelés‑egyensúlyhiányt és a kommunikációs költségeket.
- Kommunikáció elrejtése: a jelenlegi SpMV ciklus sorosan kommunikál és számol; a mátrix felbontása lokális és távoli komponensekre lehetővé teszi a lokális számítás és a távoli adatátvitel párhuzamosítását, ezáltal csökkentve a GPU‑k tétlenségi idejét.
- Fejletlen konvergencia (~feasibility polishing): a nagy LP‑k sokmillió PDLP iterációt igényelhetnek; a feasibility polishing gyorsan megvalósítható, de kevésbé optimális megoldásokat ad, ami növeli azon problémák körét, amelyeket mPDLP gyakorlati határidőn belül képes megoldani.
Hogyan lehet elkezdeni?
A mPDLP kipróbálásához az NVIDIA cuOpt tartalmaz bemutató jegyzetfüzetet (notebook), amely lépésről lépésre bemutatja a cuOpt telepítését, a solver konfigurálását és a megoldási idők összehasonlítását különböző GPU‑számok mellett. A cuOpt forráskódja elérhető az NVIDIA/cuopt GitHub repóban, ahol dokumentáció, API‑beállítások és telepítési tanácsok is találhatók. Fejlesztői közösség és támogatás érhető el a cuOpt GitHub Discussion Forumon és NVIDIA csatornákon.
Összefoglalás
A cuOpt mPDLP az LP‑megoldás több‑GPU‑sításával próbálja áthidalni az egy GPU memóriakorlátait és az órákig tartó megoldási időket, különösen nagyon nagy, ritka problémák esetén (nnz>10^7). A min‑cut partícionálás és az NVLink/NVSwitch + NCCL kombinációja lehetővé teszi, hogy sok iteráció lokálisan fusson, csökkentve a kereszt‑GPU kommunikációt. A módszer különösen nagy ipari modelleken bizonyult hasznosnak (például Kinaxis és PSR esetei), ugyanakkor a hatékonyság erősen függ a probléma méretétől és a sparsity mintázattól, így további algoritmikai és partícionálási fejlesztések folyamatban vannak.
