Multi-GPU Maximum Flow Using the Groute Framework

Abstract

Maks flyt problemet er et kjerneproblem innen grafteori og algoritmer for å løse problemet har utviklet seg siden Ford og Fulkerson publiserte sin løsning i 1956. Dette problemet dukker opp i forskjellige flytproblemer i en graf, kutting av en graf, planlegging med flere. Disse bruksområdene første til det som kalles preflow-push algoritmer. Disse har flere varianter med varierende kompleksitet, og kan parallelliseres. De tidlige parallelle algoritmene brukte låser for å unngå feil, men nyere forskning har ført til algoritmer som ikke trenger låser og er derfor mye raskere.

Systemer med flere GPU-er er blitt mer vanlig og kraftigere. Dette har ført til en økning i forskning som både bruker, og utforsker hvordan man kan bruke slike systemer. Vi presenterer det som etter vår kunnskap er den første implementeringen av en maks flyt algoritme på flere GPU-er, og identifiserer og diskuterer utfordringer ved en slik implementasjon.

Vår versjon er basert på en asynkron flertrådet algoritme publisert av Hong og He. Vi bruker Groute som er et asynkront rammeverk for programmering av flere GPU-er. Groute ble publisert av Ben-Nun, Sutton, Pai og Pingali. I vår implementasjon bruker vi distribuerte arbeidslister som følger med Groute, og CUDA sitt innbyde minnehåndtering for kommunikasjon mellom enheter. Vi testet implementasjonen på en NVIDIA DGX-2 med genrmf grafer som er ofte brukt til å teste maks flyt algoritmer.

Fler-GPU versjonen vår kan løse større problemer enn andre versjoner som kun bruker en GPU ved å utnytte den økte minnekapasiteten. Problemet med vår versjon er at den har dårligere ytelse enn en enkel implementasjon på en vanlig prosessor selv med økt minnekapasitet. Implementasjonen er også ikke feilfri og kan produsere feil resultat. Vi foreslår hvordan man kan optimalisere implementasjonen for å redusere kjøretiden, og hvordan man kan hindre at man får feil resultat.

Selv med disse problemene klarte vi å utvikle og implementere en maks flyt algoritme som kjører på flere GPU-er og gir korrekt resultat på de fleste testene våre. Resultatene våre viser hvor vanskelig det å implementere uregulære algoritmer effektivt på flere GPU-er.

The maximum flow problem is a core graph problem and algorithms for solving this problem has evolved since Ford and Fulkerson published their solution in 1956. It has applications in several graph flow problems, graph cuts, scheduling, and many more. These applications led to the development of preflow-push algorithms. These have several variations with different complexities, and are amenable to parallelization. Early efforts in parallelizing preflow-push algorithms needed locks to prevent errors, while recent research has led to lock-free algorithms that are much faster.

Multi-GPU systems are becoming more common and powerful. This has allowed the research into the usage and programming of such systems to increase. We introduce what is to our knowledge the first implementation of a maximum flow algorithm targeting multiple GPUs, and identify and discuss the suitability of implementing maximum flow on multiple GPUs.

Our implementation is based on the asynchronous multithreaded algorithm by Hong and He, and we use the asynchronous multi-GPU framework Groute by Ben-Nun, Sutton, Pai, and Pingali as a base. We use the distributed worklist supplied by Groute to manage our list of active items, and CUDA managed memory for host to device, and device to device communication. The implementation is benchmarked on an NVIDIA DGX-2 machine using genrmf graphs which are commonly used for benchmarking max-flow algorithms.

Our multi-GPU version may solve bigger problems compared to single GPU implementations due to the increased memory capacity. Even with this increase in memory capacity and the large amount of available threads it does not beat a simple single threaded CPU implementation. The implementation may also produce wrong results. We propose ways to combat both the run time issues, and the correctness issues.

We nevertheless managed to develop and implement a multi-GPU max flow algorithm which ran correctly on most of the benchmarks we tested. Our results illustrate how challenging implementing irregular algorithms efficiently on multiple GPUs.