aalto1 untyped-item.component.html
Computational performance assessment of the GPU- accelerated LP-solver cuPDLP-C
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Bachelor's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
SCI3029
Degree programme
Language
en
Pages
27
Series
Abstract
Linear programming (LP) is one of the most essential modeling and solution methods in applied mathematics. It is a method for finding the best possible decisions maximizing some objective function when constraints and objective function are linear. Since the development of the method in 1947, many solutions have been developed to the problem. One of these approaches is PDLP, which is a first-order method for LP-problems. It is the first linear programming algorithm to benefit from graphical processing units (GPU), enabling significant potential for parallelism compared to central processing unit (CPU) -based solvers. One such solver instance developed for GPUs is cuPDLP-C.
This thesis studies the computational performance of the GPU-accelerated LP-solver cuPDLP-C for a set of 23 different large-scale reference problems. Computational efficiency is compared to both the simplex method and the interior point method for the same problem. In addition, two different hardware options are used to evaluate the effect of hardware capabilities on computational efficiency.
The solvers used in the thesis have been developed by HiGHS and source for the reference problems is Mittelmann's benchmark set. Reference problems are large-scale linear, stochastic, or relaxed mixed-integer programming problems. Aalto Triton is used as a computational platform for computations. The thesis shows that most of the problems can be solved more efficiently using cuPDLP-C as a solver. However, deviation in the solution times differs significantly. Some of the problem instances requires only a few percent of the time CPU-based solvers are used, but for some problems, the solution time is tens of times greater.
Lineaarinen ohjelmointi (LP) on yksi soveltavan matematiikan tunnetuimmista ongelmista. Se on menetelmä löytää parhaat mahdolliset päätökset, jotka maksimoivat jonkin tavoitefunktion, kun rajoitteet ja tavoitefunktio ovat lineaarisia. Menetelmän kehittämisestä vuonna 1947 lähtien ongelmaan on kehitetty monia ratkaisuja. Yksi näistä lähestymistavoista on PDLP, joka on ensimmäisen asteen menetelmä LP-ongelmiin. Se on ensimmäinen lineaarinen ohjelmointialgoritmi, joka hyötyy grafiikkasuorittimista (GPU), mikä mahdollistaa merkittävän rinnakkaislaskentapotentiaalin verrattuna keskussuorittimeen (CPU) perustuviin ratkaisijoihin. Yksi tällainen GPU:ille kehitetty ratkaisija on cuPDLP-C.
Opinnäytetyössä tutkitaan grafiikkasuoritinta hyödyntävän ratkaisijan cuPDLP-C:n laskennallista tehokkuutta 23 erilaiselle laskennallisesti haastavalle ongelmalle. Jokaiselle ongelmalle cuPDLP-C:n laskennallista tehokkuutta verrataan sekä simplex-menetelmään että sisäpistemenetelmään. Lisäksi selvitetään kahden ominaisuuksiltaan eroavan grafiikkasuorittimen vaikutusta laskennalliseen tehokkuuteen.
Opinnäytetyössä käytetyt ratkaisijat ovat HiGHS:n kehittämiä ja referenssiongelmien lähteenä on aikaisemmissa tutkimuksissa käytetyt ongelmat. Referenssiongelmat ovat suuria ja laskennallisesti haastavia lineaarioptimointiongelmia. Opinnäytetyössä käytetään laskennallisena alustana Aalto Tritonia.
Tutkielman johtopäätös on, että suurin osa ongelmista voidaan ratkaista tehokkaammin käyttämällä cuPDLP-C:tä ratkaisijana. Ratkaisuaikojen poikkeama vaihtelee kuitenkin merkittävästi. Jotkut ongelmatilanteet vaativat vain muutaman prosentin CPU-pohjaisten ratkaisijoiden käyttöajasta, mutta joidenkin ongelmien ratkaisuaika on kymmeniä kertoja pitempi.